Almost Wide Probabilistic Polynomial-Time
Encyclopedia
In theoretical computer science, Almost Wide Probabilistic Polynomial-Time (AWPP) is a complexity class
for problems 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 class.
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
for problems in the context of quantum computing.
AWPP contains the BQP
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
(Bounded error, Quantum, Polynomial time) class, which contains the decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a 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 class.