AWPP (complexity)

In theoretical computer science, Almost Wide Probabilistic Polynomial-Time (AWPP) is a complexity class for problems in the context of quantum computing.

AWPP contains the BQP (Bounded error, Quantum, Polynomial time) class, which contains the decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In fact, it is the best known classical upper bound for BQP. Furthermore, it is contained in the APP class.

References

• Lance Fortnow; John Rogers. "Complexity Limitations on Quantum Computation" (PDF).  Provides information on the connection between various complexity classes.
• Stephen A. Fenner (June 19, 2002). "PP-lowness and a simple definition of AWPP". Electronic Colloquium on Computational Complexity.  Definition of AWPP and connection to APP and PP.
• Lance Fortnow; John D. Rogers (November 12, 1998). "Complexity limitations on quantum computation".  Proof of BPQ in AWPP.
• "Gap-definable counting classes" by S. Fenner, L. Fortnow, and S. Kurtz from the Journal of Computer and System Sciences. Pages 116–148, 1994, issue 48. Contains definitions.
• "An oracle builder's toolkit" by S. Fenner, L. Fortnow, S. Kurtz, and L. Li. in 8th IEEE Structure in Complexity Theory Conference Proceedings. Pages 120–131, 1993. Contains definitions.
• "Complexity Zoo": Contains a list of complexity classes, including AWPP, and their relation to other classes.