AWPP: Difference between revisions
Appearance
Content deleted Content added
{{comp-sci-theory-stub}} |
→top: Added more details |
||
Line 1: | Line 1: | ||
{{no footnotes|date=September 2018}} |
{{no footnotes|date=September 2018}} |
||
In [[theoretical computer science]], '''almost wide probabilistic polynomial-time''' ('''AWPP''') is a [[complexity class]] |
In [[theoretical computer science]], '''almost wide probabilistic polynomial-time''' ('''AWPP''') is a [[complexity class]] contained in [[PP_(complexity)|PP]] defined via [[GapP]] functions. The class often arises in the context of [[quantum computing]]. |
||
AWPP contains the [[BQP]] (bounded |
AWPP contains the complexity class [[BQP]] (bounded-error quantum polynomial time), which contains the [[decision problem]]s 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 (complexity class)|APP]] class. |
||
==References== |
==References== |
Revision as of 17:48, 8 June 2019
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (September 2018) |
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. "Complexity Limitations on Quantum Computation" (PDF).
{{cite journal}}
: Cite journal requires|journal=
(help) 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.
{{cite journal}}
: Cite journal requires|journal=
(help) 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.