Class Description

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.

Linked From

QMA: Quantum MA

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

  1. If the answer is "yes," then there exists a state such that verifier accepts with probability at least 2/3.
  2. If the answer is "no," then for all states the verifier rejects with probability at least 2/3.

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.

More about...


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.

More about...