Class Description

SBQP: Small Bounded-Error Quantum Polynomial-Time

The class of decision problems for which there exists a polynomial-time quantum algorithm that accepts with probability at least 2^−p(n) if the answer is "yes", and with probability at most 2^−p(n)−1 if the answer is "no", for some polynomial p.

Defined by Kuperberg in [Kup09], where he showed that SBQP = A₀PP.

Linked From

A₀PP: One-Sided Analog of AWPP

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:

• A₀PP contains QMA, AWPP, and coC₌P.
• A₀PP is contained in PP.
• If A₀PP = PP then PH is contained in PP.

Kuperberg ([Kup09]) showed that A₀PP = SBQP.

More about...