Class Description

QMA/qpoly: QMA With Polynomial-Size Quantum Advice

Is contained in PSPACE/poly [Aar06b].

Linked From

PSPACE/poly: PSPACE With Polynomial-Size Advice

Contains QMA/qpoly [Aar06b].

More about...

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