The class of decision problems solvable by an NP machine such that for some polynomial-time computable (i.e. FP) function f,
Defined in [FFK94].
Contains BQP [FR98], WAPP [BGM02], LWPP, and WPP.
Same as SBP, except that f is a nonnegative-valued GapP function rather than a #P function.
Defined in [Vya03], where the following was also shown:
Kuperberg ([Kup09]) showed that A0PP = SBQP.
Roughly, the class of decision problems for which the following holds. For all polynomials p(n), there exist GapP functions f and g such that for all inputs x with n=|x|,
Defined in [Li93], where the following was also shown:
The abbreviation APP is also used for Approximable in Probabilistic Polynomial Time, see AxPP.
Contains FewP [Li93] and contains YQP*, YMA*, and YP* [Yir24].
The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.
One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).
BQP is often identified as the class of feasible problems for quantum computers.
Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.
Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.
BQPBQP = BQP [BV97].
[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.
There exist oracles relative to which:
If P=BQP relative to a random oracle then BQP=BPP [FR98].
The class of decision problems solvable by an NP machine such that
Defined in [FFK94], where it was also shown that LWPP is low for PP and C=P. (I.e. adding LWPP as an oracle does not increase the power of these classes.)
Contains SPP.
Also, contains the graph isomorphism problem [KST92].
Contains a whole litter of problems for solvable black-box groups: group intersection, group factorization, coset intersection, and double-coset membership [Vin04].
The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,
Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.
The class of decision problems solvable by an NP machine such that
Defined in [FFK94].
Contained in C=P ∩ coC=P, as well as AWPP.