![]() | 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.
![]() | 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.