Class Description

QMA-plus: QMA With Super-Verifier

Same as QMA, except now the verifier can directly obtain the probability that a given observable of the certificate state, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.)

Defined in [AR03], where it was also shown that QMA-plus = QMA. Sometimes referred to as SuperQMA.

Linked From

PureSuperQMA: A pure-state analog of SuperQMA

Same as QMA, except now the witness is a pure state, and the verifier can directly obtain the probability that any one of a polynomial number of observables of the witness, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.) Without the pure state restriction, this class is SuperQMA.

Defined in [KR24] whose complete problem is the pure state marginal problem. It is known to be QMA-hard but contained in PSPACE and QMA(2). Surprisingly, it is unknown whether this class equals SuperQMA = QMA.

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