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
References
General
- Fortnow, Lance; Rogers, John D. (1999). "Complexity Limitations on Quantum Computation". Journal of Computer and System Sciences. 59 (2): 240–252. arXiv:cs/9811023. doi:10.1006/JCSS.1999.1651. Provides information on the connection between various complexity classes. Proof of BPQ in AWPP.
- Fenner, Stephen A. (2003). "PP-lowness and a simple definition of AWPP". Theory of Computing Systems. 36 (2): 199–212. doi:10.1007/s00224-002-1089-8. MR 1950277. ECCC TR02-036. Definition of AWPP and connection to APP and PP.
- Fenner, Stephen A.; Fortnow, Lance J.; Kurtz, Stuart A. (1994). "Gap-definable counting classes". Journal of Computer and System Sciences. 48 (1): 116–148. doi:10.1016/S0022-0000(05)80024-8. MR 1259653. Contains definitions.
- Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide (2003). "An oracle builder's toolkit". Information and Computation. 182 (2): 95–136. doi:10.1016/S0890-5401(03)00018-X. MR 1971487. Contains definitions.
External links
External links
- "Complexity Zoo" Archived 2018-12-01 at the Wayback Machine: Contains a list of complexity classes, including AWPP, and their relation to other classes.