The Class QMA

$\mathsf{QMA}$ — Quantum Merlin–Arthur — is the quantum analogue of $\mathsf{NP}$, or more precisely of its randomized cousin $\mathsf{MA}$. Where $\mathsf{NP}$ asks for a classical string that an efficient verifier can check, $\mathsf{QMA}$ allows the proof itself to be a quantum state, checked by a polynomial-time quantum verifier with bounded error. It is the natural home of the hardest problems in quantum complexity.

The Merlin–Arthur picture

Imagine an all-powerful but untrustworthy prover, Merlin, and a skeptical, computationally bounded Arthur. To convince Arthur that $x \in L$, Merlin sends a witness. In $\mathsf{NP}$ the witness is a classical bit string. In $\mathsf{QMA}$, Merlin may send a quantum state $\ket{\psi}$ on $\mathrm{poly}(|x|)$ qubits, and Arthur runs a polynomial-size quantum circuit $V_x$ on $\ket{\psi}\ket{0\cdots0}$ and measures an output qubit to accept or reject.

The definition

A language $L$ is in $\mathsf{QMA}$ if there is a uniform family of polynomial-size verifier circuits $V_x$ and a polynomial $p$ such that, with $m = p(|x|)$ proof qubits:

The completeness condition says a good witness exists when the answer is yes; soundness says that when the answer is no, no state can fool Arthur. Because $V_x$ is a quantum verifier with no witness, $\mathsf{BQP} \subseteq \mathsf{QMA}$; because a classical witness is a special (computational-basis) quantum state and a quantum verifier subsumes a classical randomized one, $\mathsf{MA} \subseteq \mathsf{QMA}$ and hence $\mathsf{NP} \subseteq \mathsf{QMA}$.

Why a quantum witness can help

A quantum proof is potentially more powerful than a classical one because it can encode information that has no short classical description — for instance, the ground state of a many-body Hamiltonian. Verifying "this Hamiltonian has a low-energy state" is natural if Merlin can simply hand Arthur a candidate low-energy state to measure. That is precisely the local Hamiltonian problem of the next lesson, the canonical $\mathsf{QMA}$-complete problem, and it is the reason $\mathsf{QMA}$ is the right complexity class for quantum physics, not just quantum computing.

Error amplification — and why it is subtle

As with $\mathsf{BQP}$, the constants $2/3$ and $1/3$ are arbitrary; the class is unchanged for any inverse-polynomial gap. But naive repetition is dangerous here: Arthur would need several copies of the witness, and a cheating Merlin might send an entangled state across the copies rather than $m$ honest independent ones. The Marriott–Watrous amplification theorem resolves this elegantly: Arthur can drive the error down to $2^{-\mathrm{poly}}$ using a single copy of the witness, by repeatedly applying the verifier and its inverse and measuring projectively — a quantum analogue of strong amplification that never consumes extra witness qubits. This robustness is what makes $\mathsf{QMA}$ a well-defined, stable class.

Where QMA sits

The known containments are

with $\mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QMA}$ as well. The upper bound $\mathsf{QMA} \subseteq \mathsf{PSPACE}$ follows from the same path-summation idea as for $\mathsf{BQP}$, maximizing over witnesses. As usual, none of these containments is known to be strict.

Variants worth naming

Several refinements appear in the literature. $\mathsf{QCMA}$ restricts Merlin to a classical witness while keeping Arthur quantum — whether $\mathsf{QCMA} = \mathsf{QMA}$ (does a quantum proof ever help?) is open. $\mathsf{QMA}(2)$ allows two unentangled Merlins, which is at least as powerful and possibly more. And $\mathsf{QMA}_1$ demands perfect completeness ($p = 1$ for yes-instances). These distinctions matter because the local Hamiltonian problem and its physical cousins are complete for $\mathsf{QMA}$ specifically, the subject we turn to next.

Sign in on the full site to ask questions and join the discussion.