AWPP (complexity)

In theoretical computer science, almost wide probabilistic polynomial-time (AWPP) is a complexity class contained in PP defined via GapP functions. The class often arises in the context of quantum computing.

AWPP contains the complexity class BQP (bounded-error quantum polynomial time), 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 smallest classical complexity class that upper bounds BQP. Furthermore, it is contained in the APP class.

References

General

• Lance Fortnow; John Rogers (1998). Complexity Limitations on Quantum Computation. Bibcode: 1998cs.......11023F. http://people.cs.uchicago.edu/~fortnow/papers/quantum.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. http://eccc.hpi-web.de/eccc-reports/2002/TR02-036/index.html.  Definition of AWPP and connection to APP and PP.
• Lance Fortnow; John D. Rogers (November 12, 1998). "Complexity limitations on quantum computation". arXiv:cs/9811023. 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.

External links

• "Complexity Zoo" : Contains a list of complexity classes, including AWPP, and their relation to other classes.