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.
The class of decision problems such that a "yes" answer can be verified by a 1-message quantum interactive proof. That is, a BQP (i.e. quantum polynomial-time) verifier is given a quantum state (the "proof"). We require that
QMA = QIP(1).
Defined in [Wat00], where it is also shown that group non-membership is in QMA.
Based on this, [Wat00] gives an oracle relative to which MA is strictly contained in QMA.
Kitaev and Watrous (unpublished) showed QMA is contained in PP (see [MW05] for a proof). Combining that result with [Ver92], one can obtain an oracle relative to which AM is not in QMA.
Kitaev ([KSV02], see also [AN02]) showed that the 5-Local Hamiltonians Problem is QMA-complete. Subsequently, Kempe and Regev [KR03] showed that even 3-Local Hamiltonians is QMA-complete. A subsequent paper by Kempe, Kitaev, and Regev [KKR04], has hit rock bottom (assuming P does not equal QMA), by showing 2-local Hamiltonians QMA-complete.
Compare to NQP.
If QMA = PP then PP contains PH [Vya03]. This result uses the fact that QMA is contained in A0PP.
Approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete [AGK07].
See also: QCMA, QMA/qpoly, QSZK, QMA(2), QMA-plus.
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.