Almost Wide Probabilistic Polynomial-Time

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style.

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.

[edit] References

• http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf Provides information on the connection between various complexity classes.
• http://eccc.hpi-web.de/eccc-reports/2002/TR02-036/index.html Definition of AWPP and connection to APP and PP.
• http://arxiv.org/abs/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.
• Complexity Zoo: Contains a list of complexity classes, including AWPP, and their relation to other classes.