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 = A0PP.

Linked From

A0PP: 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:

Kuperberg ([Kup09]) showed that A0PP = SBQP.

More about...