Class Description

QCMA: Quantum Classical MA

The class of decision problems for which a "yes" answer can be verified by a quantum computer with access to a classical proof. Also known as the subclass of of QMA with classical witnesses. Defined in [AN02].

Called MQA by Watrous [Wat09].

Contains MA, and is contained in QMA.

Given a black-box group G and a subgroup H, the problem of testing non-membership in H has polynomial QCMA query complexity [AK06].

See [AK06] for a "quantum oracle separation" between QCMA and QMA. No classical oracle separation between QCMA and QMA is currently known.

The problem GROUND STATE CONNECTIVITY, which intuitively asks whether a local Hamiltonian's ground space has an "energy barrier", is QCMA-complete [GS15]. Roughly: Given a local Hamiltonian H and ground states v and w, is there a polynomial-length sequence of local unitary operations mapping v to w, such that each intermediate state encountered remains in the ground space of H?

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