AWPP

Uses your system voice; voice and rate in settings.

Q4655144Snapshot

≈ 2 min read

Names in other languages

  • caAWPP (complexitat)
  • EnglishAWPP
  • slAWPP

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

General

Provides information on the connection between various complexity classes. Proof of BPQ in AWPP. Definition of AWPP and connection to APP and PP. Contains definitions. Contains definitions.

"Complexity Zoo" : Contains a list of complexity classes, including AWPP, and their relation to other classes.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1221311104 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.