AWPP: Difference between revisions

Content deleted Content added

Inline

Revision as of 17:48, 8 June 2019

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.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

@@ Line 1: / Line 1: @@
 {{no footnotes|date=September 2018}}
-In [[theoretical computer science]], '''almost wide probabilistic polynomial-time''' ('''AWPP''') is a [[complexity class]] for problems in the context of [[quantum computing]].
+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 error, quantum, polynomial time) class, 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 best known classical upper bound for BQP. Furthermore, it is contained in the [[APP (complexity class)|APP]] class.
+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==