Quantum computing and quadratically signed weight enumerators

We prove that quantum computing is polynomially equivalent to classical pro babilistic computing with an oracle for estimating the value of simple sums , quadratically signed weight enumerators (QWGTs). The problem of estimatin g these sums is cast in terms of promise problems and has two interesting v ariants. An oracle for the unconstrained variant may be more powerful than quantum computing, while an oracle for a more constrained variant is effici ently solvable in the one-bit model of quantum computing. Thus, problems in volving QWGTs yield new problems in BQPP (BQP promise problems) and a natur al BQPP complete problem. They can be used to define and study complexity c lasses and their relationships to quantum computing. (C) 2001 Elsevier Scie nce B.V. All rights reserved.