Quantum computing and quadratically signed weight enumerators

We prove that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating the value of simple sums, quadratically signed weight enumerators (QWGTs). The problem of estimating these sums is cast in terms of promise problems and has two interesting variants. An oracle for the unconstrained variant may be more powerful than quantum computing, while an oracle for a more constrained variant is efficiently solvable in the one-bit model of quantum computing. Thus, problems involving QWGTs yield new problems in BQPP (BQP promise problems) and a natural BQPP complete problem. They can be used to define and study complexity classes and their relationships to quantum computing. (C) 2001 Elsevier Science B.V. All rights reserved.