Almost Wide Probabilistic Polynomial-Time
- Almost Wide Probabilistic Polynomial-Time
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
* 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.
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo Complexity Zoo] : Contains a list of complexity classes, including AWPP, and their relation to other classes.
Wikimedia Foundation.
2010.
Look at other dictionaries:
AWPP — may refer to:* Adaptive Wireless Path Protocol * Almost Wide Probabilistic Polynomial Time … Wikipedia
Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity. Computer scientist Manindra Agrawal of the… … Universalium
Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… … Wikipedia
Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… … Wikipedia
Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… … Wikipedia
mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… … Universalium
