QMA Variants and Related Classes

Quantum Merlin–Arthur is the quantum face of NP: a YES-instance carries a quantum witness $|\psi\rangle$ that a polynomial-time quantum verifier accepts with high probability, while for NO-instances nothing is accepted with more than low probability. But this definition quietly bundles four independent design choices — the witness is quantum, the verifier is quantum, the error is two-sided, and there is one prover. The variants of QMA are what you get by changing exactly one of those choices at a time. Turn the witness classical and you have QCMA; give the verifier two witnesses promised unentangled and you have QMA(2); demand acceptance with probability exactly one and you have QMA $_1$ ; restrict the Hamiltonian to the sign-problem-free case and you have StoqMA. Each turn is a physics experiment on the proof system: which features of a quantum proof are load-bearing, and which are free? The answers are mostly open. Whether a classical certificate can always replace a quantum one (QCMA vs QMA) is unknown; whether two unentangled provers are strictly stronger than one (QMA(2) vs QMA) is unknown, with no tight ceiling below NEXP. What is known is that these are not idle taxonomy: each class is the exact complexity of a natural family of physical ground-state problems, and the boundaries between them — the sign problem, perfect completeness, the unentanglement promise — mark what a quantum computer must certify versus what a classical shadow of it can. This article maps that landscape with the Local Hamiltonian problem as its compass.

Key takeaways

Standard QMA fixes four choices — quantum witness, quantum verifier, two-sided error, one prover; each variant turns exactly one and asks whether the power moves.
QCMA makes the witness a classical string while Arthur stays quantum; $\mathrm{QCMA}\subseteq\mathrm{QMA}$ is trivial, equality is open with oracle separations known.
QMA(2) gives two witnesses promised unentangled; it buys sublinear proofs for NP problems, and $\mathrm{QMA}\subseteq\mathrm{QMA}(2)=\mathrm{QMA}(k)\subseteq\mathrm{NEXP}$ with no tighter ceiling proven.
QMA $_1$ demands perfect completeness (accept the truth with probability exactly $1$ ); amplification reaches $1-2^{-\mathrm{poly}}$ but a finite gate set generically cannot reach $1$ , so it is separate, complete for quantum-SAT.
StoqMA captures stoquastic (sign-problem-free) local Hamiltonians, sits between MA and QMA, and is complete for the stoquastic local Hamiltonian problem (whose frustration-free case drops to MA-complete).
Key idea: every QMA variant turns exactly one knob — witness type (quantum/classical/multipartite), error profile (bounded/perfect), or Hamiltonian structure (general/stoquastic/frustration-free) — and its complete problem tracks that knob: general local Hamiltonian for QMA, quantum-SAT for QMA $_1$ , product-checkable Hamiltonians for QMA(2), stoquastic local Hamiltonian for StoqMA.

The core insight

Every QMA variant is obtained by turning exactly one knob — witness type (quantum/classical/multipartite), error profile (bounded/perfect), or Hamiltonian structure (general/stoquastic/frustration-free) — and asking whether the verification power changes; the complete problems track the knobs, from general local Hamiltonian for QMA to stoquastic local Hamiltonian for StoqMA.

Where this lives today

The variant map is the working reference for quantum Hamiltonian complexity, and its knobs are live research fronts. The QCMA-versus-QMA question drives the search for oracle separations proving quantum witnesses are sometimes irreplaceable — Aaronson–Kuperberg gave a quantum-oracle separation in 2007, with later work sharpening toward classical oracles — because a collapse $\mathrm{QCMA}=\mathrm{QMA}$ would give every quantumly verifiable claim a short classical certificate, reshaping delegated computation and proof-of-quantumness protocols. QMA(2) is the most tantalizing gap: its only ceiling is NEXP, and closing it would settle whether unentanglement is a genuine resource, a question tied to the separability problem, product tests, and quantum de Finetti theorems. StoqMA is the complexity-theoretic diagnosis of the sign problem in quantum Monte Carlo: recent work on "curing" the sign problem by basis changes maps directly onto whether a Hamiltonian can be made stoquastic, hence onto the StoqMA-versus-QMA boundary. And QMA $_1$ sharpened when Gosset and Nagaj proved quantum 3-SAT QMA $_1$ -complete, pinning perfect completeness to a clean 3-local problem. Each is a physicist's question — how hard is it to certify this material's ground energy — in a complexity-theoretic uniform.

The physical picture

Picture a control panel with three knobs — WITNESS, ERROR, HAMILTONIAN — and one factory preset called QMA: one quantum witness, two-sided error $c=2/3,\ s=1/3$ , a general local Hamiltonian. Every variant here is a single knob moved off that preset, and the whole programme is figuring out which turns change the music. Turn WITNESS to "one classical string" and QMA becomes QCMA, or to "two states promised unentangled" and it becomes QMA(2). Turn ERROR to "accept the truth with probability exactly one" and it becomes QMA $_1$ . Turn HAMILTONIAN to "every off-diagonal element $\le 0$ " and it becomes StoqMA. The first figure is that panel.

Figure

One control panel with three knobs — WITNESS turns QMA into QCMA or QMA(2), ERROR turns it into QMA₁ with acceptance probability exactly 1, and HAMILTONIAN turns it into StoqMA where every off-diagonal Hamiltonian term is non-positive; each variant moves exactly one knob off the QMA factory preset c = 2/3, s = 1/3

The unentanglement knob is the most counterintuitive. Two provers who cannot coordinate are, paradoxically, more useful to Arthur than one: he can cross-check them with a product test that exploits the promise their state factorizes — a separability guarantee no single register could give him. Stoquasticity is the complexity-theoretic name for "no sign problem": in a fixed basis the ground-state amplitudes can be taken real and non-negative, which is why StoqMA hugs classical MA from above. And perfect completeness, cosmetic as it looks, needs the accepting projector to have an eigenvector of eigenvalue exactly one — which a discrete gate set need not provide. The second figure places every variant in the containment landscape, the preset gap $c=2/3,\ s=1/3$ marked at QMA.

Figure

The complexity landscape of QMA and its variants: every arrow reads as set inclusion ⊆, so MA ⊆ QCMA ⊆ QMA ⊆ PP ⊆ PSPACE along the spine, with MA ⊆ StoqMA ⊆ QMA above and QMA₁ ⊆ QMA below, while two unentangled witnesses push QMA ⊆ QMA(2) = QMA(k) ⊆ NEXP; the dashed link is the open question QCMA = QMA and QMA carries the preset gap c = 2/3, s = 1/3

The core equations

The engine of every variant is one object: the verifier's accepting projector and the largest expectation it takes over the allowed witnesses. Start from the definition. A language $L$ is in QMA if a uniform family of polynomial-size quantum verifiers $V_x$ separates YES from NO by a $1/\mathrm{poly}$ gap.

x\in L_{\mathrm{yes}}\Rightarrow\exists|\psi\rangle:\ \Pr[V_x\text{ accepts }|\psi\rangle]\ge c,\qquad x\in L_{\mathrm{no}}\Rightarrow\forall|\psi\rangle:\ \Pr[V_x\text{ accepts }|\psi\rangle]\le s \qquad (1)

where: $V_x$ — polynomial-size quantum verifier circuit depending on input $x$ ; $|\psi\rangle$ — quantum witness on $\mathrm{poly}(|x|)$ qubits; $c,s$ — completeness and soundness with $c-s\ge 1/\mathrm{poly}$ , canonically $c=2/3,\ s=1/3$ . Reading: a YES-instance has some accepted witness; a NO-instance has none, and the promise gap is what an algorithm gets to detect. The acceptance probability is a quadratic form set by the verifier run backwards on the accepting subspace — the hinge that turns a proof system into a spectral problem.

\Pr[V_x\text{ accepts }|\psi\rangle]=\langle\psi|\,\Pi_{\mathrm{acc}}^{(x)}\,|\psi\rangle,\qquad \Pi_{\mathrm{acc}}^{(x)}=V_x^{\dagger}\big(|1\rangle\langle1|_{\mathrm{out}}\otimes I\big)V_x \qquad (2)

where: $\Pi_{\mathrm{acc}}^{(x)}$ — projector encoding "the output qubit reads 1 after $V_x$ "; $|1\rangle\langle1|_{\mathrm{out}}$ — projector onto its accepting value. Reading: the best witness is the top eigenvector of $\Pi_{\mathrm{acc}}$ , so maximum acceptance is $\lambda_{\max}$ and deciding $L$ becomes estimating $\lambda_{\max}$ to within the gap. Complementing the projector gives the penalty Hamiltonian whose ground energy the verifier really measures — the dictionary that makes QMA the complexity class of physical ground states.

H_{\mathrm{out}}=I-\Pi_{\mathrm{acc}}^{(x)},\qquad \lambda_{\min}(H_{\mathrm{out}})\le 1-c\ \text{(yes)}\quad\text{or}\quad \ge 1-s\ \text{(no)} \qquad (3)

where: $H_{\mathrm{out}}$ — penalty operator, low energy = accepted; $\lambda_{\min}$ — ground-state energy within the promise gap. Reading: Kitaev's construction makes $H_{\mathrm{out}}$ genuinely $k$ -local, so general local Hamiltonian is QMA-complete and every variant is a structural restriction on this $H$ . Knob one. QCMA replaces the quantum witness by a classical string while keeping Arthur quantum, so the maximization in (2) runs only over computational-basis states.

x\in L_{\mathrm{yes}}^{\mathrm{QCMA}}\Rightarrow\exists\, y\in\{0,1\}^{\mathrm{poly}}:\Pr[V_x(y)=1]\ge c,\qquad x\in L_{\mathrm{no}}\Rightarrow\forall y:\Pr[V_x(y)=1]\le s \qquad (4)

where: $y$ — classical certificate handed to the quantum verifier. Reading: since $|y\rangle=\bigotimes_i|y_i\rangle$ is a legal witness, $\mathrm{QCMA}\subseteq\mathrm{QMA}$ is immediate; whether a short classical string can always replace an entangled witness is open. Knob two. QMA(2) hands Arthur two registers with the promise that the joint witness factorizes, so the feasible set is the separable states, not all of them.

\mathrm{QMA}(2):\ \ |\psi\rangle=|\phi_1\rangle\otimes|\phi_2\rangle,\qquad \Pr[V_x\text{ accepts}]=\max_{|\phi_1\rangle,|\phi_2\rangle}\langle\phi_1\phi_2|\,\Pi_{\mathrm{acc}}\,|\phi_1\phi_2\rangle \qquad (5)

where: $|\phi_1\rangle,|\phi_2\rangle$ — witnesses on disjoint registers, promised unentangled. Reading: this maximum is the support function of $\Pi_{\mathrm{acc}}$ over product states — the NP-hard separable optimization — and the promise lets Arthur run a product test no single register can imitate. Knob three. QMA $_1$ tightens completeness to exactly one — not a limit of (1) but a different demand on the spectrum of $\Pi_{\mathrm{acc}}$ .

\mathrm{QMA}_1:\quad x\in L_{\mathrm{yes}}\Rightarrow\exists|\psi\rangle:\Pr[V_x\text{ accepts}]=1,\qquad x\in L_{\mathrm{no}}\Rightarrow\forall|\psi\rangle:\Pr[V_x\text{ accepts}]\le s \qquad (6)

where: the " $=1$ " — exact acceptance, requiring $\Pi_{\mathrm{acc}}$ to have an eigenvector of eigenvalue exactly $1$ . Reading: this is the home of quantum-SAT (does a frustration-free local Hamiltonian have a zero-energy ground state), and it is not known to equal QMA. Knob four restricts the Hamiltonian. A stoquastic Hamiltonian has no sign problem: every off-diagonal local element is non-positive in a fixed basis.

H=\sum_a H_a,\qquad \langle x|H_a|y\rangle\le 0\ \ \text{for all }x\ne y\ \text{in the computational basis} \qquad (7)

where: $H_a$ — local term on $O(1)$ qubits; $\langle x|H_a|y\rangle$ — off-diagonal element in the standard basis. Reading: shifting $M=cI-H$ makes it entrywise non-negative, so by Perron–Frobenius the ground state has all non-negative amplitudes — the object StoqMA verifies. Finally, the shared ceiling. However the knobs are set, single-prover quantum verification stays within probabilistic polynomial time with unbounded error.

\mathrm{MA}\subseteq\mathrm{QCMA}\subseteq\mathrm{QMA}\subseteq\mathrm{PP}\subseteq\mathrm{PSPACE},\qquad \mathrm{MA}\subseteq\mathrm{StoqMA}\subseteq\mathrm{QMA} \qquad (8)

where: $\mathrm{PP}$ — probabilistic polynomial time, the standard QMA ceiling (Vyalyi, via $\mathrm{QMA}\subseteq\mathrm{A_0PP}$ ). Reading: only QMA(2) escapes this spine, with no proven ceiling below NEXP — the price of the unentanglement promise.

Derivation AError amplification and why it stops short of perfect completeness

The goal is to show that the QMA promise gap is astonishingly robust — a mere $1/\mathrm{poly}$ separation between $c$ and $s$ can be pushed to exponentially small error on both sides — yet that the same machinery provably cannot drive completeness to exactly one, which is the entire reason QMA $_1$ is a class of its own rather than a corner of QMA. We run the verifier on independent copies, bound the majority vote by Chernoff, then examine what the accepting projector's spectrum can be under a finite gate set.

Step 1. Ask Merlin for $k$ copies, $|\Psi\rangle=|\psi\rangle^{\otimes k}$ , run $V_x$ on each and accept on a majority. In the YES case the honest state makes each run accept with probability $\ge c$ ; in the NO case a convexity argument shows no state — even one entangled across copies — raises any single run above $s$ . Why: soundness must survive a Merlin who correlates the copies, and the projector's structure guarantees it does.

Step 2. Let $X$ be the fraction accepting: $\mathbb{E}[X]\ge c>1/2$ (yes) or $\le s<1/2$ (no), so Chernoff gives $\Pr[\text{wrong}]\le e^{-2k(c-1/2)^2}$ , which at $c=2/3$ is $e^{-2k(1/6)^2}=e^{-k/18}$ . Why: independent repetitions concentrate the mean, so a wrong majority needs a large deviation, exponentially unlikely in $k$ .

Step 3. For error $2^{-r}$ set $e^{-k/18}\le 2^{-r}$ , i.e. $k\ge 18\,r\ln 2\approx 12.5\,r$ — still polynomial. The gap $(2/3,1/3)$ becomes $(1-2^{-\mathrm{poly}},2^{-\mathrm{poly}})$ , and Marriott–Watrous achieve this in place, without enlarging the witness. Why: the constants in (1) are immaterial — any $1/\mathrm{poly}$ gap defines the same class.

Step 4. But completeness landed at $1-2^{-\mathrm{poly}}$ , never $1$ : reaching $c=1$ needs $\lambda_{\max}(\Pi_{\mathrm{acc}})=1$ exactly, and over a fixed gate set the entries of $V_x$ are fixed algebraic numbers whose top eigenvalue is generically $1-2^{-\mathrm{poly}}\ne 1$ . Why: amplification reaches $1$ only in the limit, so perfect completeness is separate and gate-set-sensitive — hence QMA $_1$ .

Go deeper · Derivation B · 1 minWhy two unentangled witnesses can only help and cannot obviously be simulated

Derivation BWhy two unentangled witnesses can only help and cannot obviously be simulated

The goal is to pin down why $\mathrm{QMA}\subseteq\mathrm{QMA}(2)$ is a one-line triviality while its converse is one of the most stubborn open problems in quantum complexity, and to see how the many-prover hierarchy collapses to two but not to one. We embed a QMA protocol into the two-prover setting, then run the simulation backwards and watch where the unentanglement promise blocks it — the same place the product test draws its power.

Step 1. Given a QMA verifier $V_x$ , build a QMA(2) verifier that ignores the second register: $V^{(2)}_x(|\phi_1\rangle\otimes|\phi_2\rangle)=V_x(|\phi_1\rangle)$ . It accepts exactly when $V_x$ does, so $\mathrm{QMA}\subseteq\mathrm{QMA}(2)$ . Why: extra provers are optional resources Arthur can decline, so more witnesses never weaken him.

Step 2. Reverse it: to simulate QMA(2) inside QMA, Arthur gets one register and must reproduce the product maximization of (5). But a single register can hold an entangled $|\Phi\rangle_{12}$ , which can score higher on $\Pi_{\mathrm{acc}}$ than any product state, spuriously passing a test meant for separable inputs. Why: "the witness factorizes" is information Arthur cannot verify from within one register — QMA(2)'s power is that this promise comes for free.

Step 3. More provers add nothing beyond two: Harrow–Montanaro's product test certifies a state on $k$ registers is close to fully product, reducing $\mathrm{QMA}(k)$ to $\mathrm{QMA}(2)$ for every polynomial $k$ . Why: one separability test collapses the hierarchy to level two, but none collapses level two to level one.

Step 4. The only known ceiling is $\mathrm{QMA}(2)\subseteq\mathrm{NEXP}$ , by guessing exponentially precise descriptions of both witnesses; no proof of $\mathrm{QMA}(2)\subseteq\mathrm{PSPACE}$ or $\mathrm{QMA}(2)=\mathrm{QMA}$ exists. Why: without an entanglement-free single-register simulation, the $\mathrm{QMA}\subseteq\mathrm{PP}$ ceiling does not transfer, leaving an exponential gap.

Go deeper · Derivation C · 1 minStoqMA verification from Perron-Frobenius ground states

Derivation CStoqMA verification from Perron-Frobenius ground states

The goal is to explain why the sign-problem-free restriction is exactly what lets a nearly classical Merlin–Arthur protocol certify a Hamiltonian's ground energy, placing the stoquastic local Hamiltonian problem in StoqMA between MA and QMA. We turn the stoquastic condition into an entrywise-non-negative matrix, invoke Perron–Frobenius to make the ground state probability-like, and describe the weak sign-definite measurement a StoqMA verifier is allowed — weaker than a full QMA measurement, which is why the class sits lower.

Step 1. Take $H=\sum_a H_a$ stoquastic and shift: $M=cI-H$ with $c$ large enough that every entry $\langle x|M|y\rangle\ge 0$ . The ground state of $H$ is the top eigenvector of the non-negative $M$ . Why: an energy shift changes nothing physical but turns "lowest energy of $H$ " into "largest eigenvalue of a non-negative matrix," where Perron–Frobenius applies.

Step 2. For irreducible non-negative $M$ , Perron–Frobenius forces the top eigenvector to have positive entries, so $|\psi_0\rangle=\sum_x\psi_0(x)|x\rangle$ with $\psi_0(x)\ge 0$ — a real, non-negative amplitude vector, formally a (sub-)stochastic distribution. Why: this is the precise sense in which "no sign problem" means "the ground state looks classical," making Monte Carlo sampling feasible.

Step 3. In the frustration-free case $H\succeq 0$ with $H_a|\psi_0\rangle=0$ for every $a$ : the ground state minimizes each local term at once, the stoquastic analogue of a satisfying assignment. Arthur verifies a term with a single sign-definite measurement, acceptance $\Pr[\text{accept}]=\tfrac12+\tfrac12\langle\psi|M_a|\psi\rangle$ , using Hadamard readout plus coin flips. Why: one $|+\rangle$ -type measurement plus randomness suffices — strictly less than QMA's full projective power.

Step 4. These bracket the class: a classical MA protocol with sampling captures YES-instances ( $\mathrm{MA}\subseteq\mathrm{StoqMA}$ ), while a StoqMA verifier is a restricted QMA verifier ( $\mathrm{StoqMA}\subseteq\mathrm{QMA}$ ), and the stoquastic local Hamiltonian problem is StoqMA-complete. Why: the acceptance form is more than classical yet less than quantum, so StoqMA lands genuinely between MA and QMA. *The refined containment $\mathrm{StoqMA}\subseteq\mathrm{SBP}\subseteq\mathrm{AM}$ gives a tighter ceiling than QMA alone, and the stoquastic local Hamiltonian problem is StoqMA-complete, while its frustration-free case is only MA-complete.*

Limiting cases

Known and conjectured relations among the variants, with a two-sided gap $\ge 1/\mathrm{poly}$ unless noted.

Case	Result	Meaning
QCMA vs QMA	$\mathrm{MA}\subseteq\mathrm{QCMA}\subseteq\mathrm{QMA}\subseteq\mathrm{PP}$	Both inclusions hold; $\mathrm{QCMA}=\mathrm{QMA}$ is open, with quantum and classical oracle separations known
QMA(k) collapse	$\mathrm{QMA}(2)=\mathrm{QMA}(k),\ k\ge 2$	Any constant or polynomial number of unentangled provers collapses to two (Harrow–Montanaro); $\mathrm{QMA}\subseteq\mathrm{QMA}(2)\subseteq\mathrm{NEXP}$
QMA $_1$ vs QMA	$\mathrm{QMA}_1\subseteq\mathrm{QMA}$	Perfect completeness contained in QMA; equality open, but over gate sets allowing exact amplitude analysis the gap can close
StoqMA placement	$\mathrm{MA}\subseteq\mathrm{StoqMA}\subseteq\mathrm{QMA}$	Sandwiched; stoquastic local Hamiltonian is StoqMA-complete, with ceiling $\mathrm{StoqMA}\subseteq\mathrm{AM}$
Amplification limit	$c\to 1-2^{-\mathrm{poly}},\ s\to 2^{-\mathrm{poly}}$	Error shrinks exponentially close to, but never equal to, the perfect values within QMA — hence QMA $_1$ is separate

Common trapTwo traps: amplifying to perfect completeness, and folding two provers into one

Trap one: assuming QMA error can be driven to exactly perfect completeness as easily as it is amplified. It cannot — amplification pushes completeness to $1-2^{-\mathrm{poly}}$ , but reaching $1$ needs the accepting projector to have eigenvalue exactly $1$ on some witness, which a generic finite gate set (fixed algebraic amplitudes) cannot guarantee. That is precisely why QMA $_1$ is separate and not known to equal QMA. Trap two: treating QMA(2) as "obviously QMA" because two witnesses concatenate into one register. The catch is that a single combined witness can be entangled across the registers, so $\mathrm{QMA}\subseteq\mathrm{QMA}(2)$ is trivial but the reverse is not; the unentanglement promise, free to Arthur and otherwise uncertifiable, is the whole source of the power.

Worked examples

1 · How many witness copies does amplification cost? (fully worked)

A QMA verifier has the preset gap $c=2/3,\ s=1/3$ . Merlin supplies independent witness copies and Arthur takes a majority. How many copies $k$ drive both error probabilities below $2^{-100}$ , and what does it cost?

Step 1. The majority is wrong only if the accepting fraction crosses $1/2$ the wrong way, a deviation of $c-1/2=1/6$ (yes) or $1/2-s=1/6$ (no), so Chernoff gives $\Pr[\text{wrong}]\le e^{-2k(1/6)^2}=e^{-k/18}$ on both sides.

Step 2. Demand $e^{-k/18}\le 2^{-100}$ : then $k/18\ge 100\ln 2=69.31$ , so $k\ge 1247.7$ and $\mathbf{k=1248}$ copies suffice for error $\le 2^{-100}$ each side.

Step 3. The witness is now $|\psi\rangle^{\otimes 1248}$ , so a $q$ -qubit witness grows to $1248\,q$ qubits — still polynomial, confirming QMA is unchanged by the constants. But completeness reached $1-2^{-100}$ , not $1$ : no finite count makes it exact. In practice one uses Marriott–Watrous in-place amplification, attaining the same $2^{-\mathrm{poly}}$ error while keeping the witness at $q$ qubits. Result: k = 1248 copies (or zero extra qubits via Marriott–Watrous), completeness 1 − 2⁻¹⁰⁰ < 1.

2 · A stoquastic Hamiltonian has a non-negative ground state (fully worked)

Take the single-qubit transverse field $H=-X$ . Verify it is stoquastic, find its ground energy and ground state, and confirm the ground-state amplitudes are non-negative — then contrast with a sign-problem Hamiltonian.

Step 1. Write the matrix in the computational basis: $H=-X=\begin{pmatrix}0&-1\\-1&0\end{pmatrix}$ . The only off-diagonal element is $\langle 0|H|1\rangle=-1\le 0$ , so $H$ is stoquastic — no sign problem.

Step 2. Diagonalize: $\det(H-\lambda I)=\lambda^2-1=0$ , so eigenvalues are $\lambda=\pm 1$ and the ground energy is $\mathbf{E_0=-1}$ . Solving $(H-(-1)I)v=0$ gives $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}v=0$ , so $v\propto(1,1)$ , i.e. the ground state is $|+\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$ .

Step 3. The amplitudes $\psi_0(0)=\psi_0(1)=+\tfrac{1}{\sqrt2}\ge 0$ are entrywise non-negative, exactly as Perron–Frobenius predicts for $M=cI-H$ . Flip the sign: $H'=+X$ is not stoquastic (off-diagonal $+1$ ), and its ground state $|-\rangle=\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ carries a negative amplitude — the seed of a many-body sign problem. Result: E₀ = −1, ground state |+⟩ with amplitudes (+1/√2, +1/√2) ≥ 0; the non-stoquastic +X forces a negative amplitude.

Physics of the portrait

The variant landscape is not the work of one person but of a generation of quantum-complexity theorists; if any single figure sits at the crossroads of three of its four knobs, it is Sergey Bravyi.

Origins · 1 minSergey Bravyi and how this was discovered

Sergey Bravyi

quantum information theorist, IBM Research · stoquastic complexity, quantum-SAT, and the sign problem

Sergey Bravyi is a quantum information theorist at IBM Research whose work threads through more of the QMA variant map than almost anyone else's. Where Alexei Kitaev built the frame — introducing QMA around 1999 and proving, in the 2002 Kitaev–Shen–Vyalyi book, that local Hamiltonian is QMA-complete via the quantum Cook–Levin theorem — Bravyi supplied its most physical corners. In 2006 he gave an efficient algorithm for quantum 2-SAT, the frustration-free zero-energy problem that anchors QMA $_1$ , showing the "easy" boundary of perfect-completeness verification is genuinely 2-local just as classical 2-SAT is easy while 3-SAT is hard. That same year, with Bessen and Terhal, he introduced StoqMA and identified stoquasticity — every off-diagonal term non-positive — as the exact complexity-theoretic shadow of the sign problem that blesses or dooms quantum Monte Carlo; the 2008 Bravyi–DiVincenzo–Oliveira–Terhal paper made the stoquastic local Hamiltonian problem StoqMA-complete, while Bravyi and Terhal showed its frustration-free case is MA-complete. The rest of the map filled in around these: Aharonov–Naveh named QCMA and QMA $_1$ ; Aaronson, Beigi, Drucker, Fefferman, and Shor's "power of unentanglement" gave QMA(2) proofs of NP statements with $\tilde O(\sqrt n)$ -qubit witnesses; Harrow–Montanaro's product test collapsed the many-prover hierarchy to two. Bravyi's throughline is the physicist's question underneath the complexity: what structure in a Hamiltonian makes its ground state easy or hard to certify — and the variants are the catalogue of answers.

History

1999

— Kitaev introduces QMA and proves the local Hamiltonian problem is QMA-complete

2002

— Kitaev, Shen, Vyalyi codify QMA, error amplification, and the verifier-to-Hamiltonian dictionary; Aharonov and Naveh survey Quantum NP and name QCMA and QMA₁

2006

— Bravyi solves quantum 2-SAT, and Bravyi, Bessen, Terhal define StoqMA

2008

— Aaronson, Beigi, Drucker, Fefferman, Shor establish the power of unentanglement for QMA(2); Bravyi, DiVincenzo, Oliveira, Terhal prove stoquastic local Hamiltonian is StoqMA-complete

2013

— Harrow and Montanaro collapse QMA(k) to QMA(2) with the product test

Going further

Texts. Kitaev, Shen, Vyalyi, Classical and Quantum Computation (2002), Ch. 14 — QMA, local Hamiltonian, amplification · Watrous, The Theory of Quantum Information (2018), Ch. on quantum proofs · Aharonov & Naveh, Quantum NP — A Survey, arXiv:quant-ph/0210077 — QCMA and QMA $_1$ · Bravyi, Bessen, Terhal / Bravyi, DiVincenzo, Oliveira, Terhal, The Complexity of Stoquastic Local Hamiltonian Problems (2008) — StoqMA · Aaronson, Beigi, Drucker, Fefferman, Shor, The Power of Unentanglement (CCC 2008) — QMA(2) · Harrow & Montanaro, Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization (JACM 2013) · Bravyi, Efficient Algorithm for a Quantum Analogue of 2-SAT (2006) — quantum-SAT · Gharibian, Huang, Landau, Shin, Quantum Hamiltonian Complexity (survey, 2015). Key anchor results: the amplification bound is $\Pr[\text{wrong}]\le e^{-k/18}$ at the preset gap, so $k=1248$ copies reach error $2^{-100}$ while completeness stays $<1$ ; the best witness is always the top eigenvector of $\Pi_{\mathrm{acc}}$ , giving $\max_\psi\langle\psi|\Pi_{\mathrm{acc}}|\psi\rangle=\lambda_{\max}$ ; Perron–Frobenius non-negativity is confirmed on $H=-X$ , which yields $E_0=-1$ and ground state $|+\rangle$ with amplitudes $+1/\sqrt{2}$ ; the full containment chain is $\mathrm{MA}\subseteq\mathrm{QCMA}\subseteq\mathrm{QMA}\subseteq\mathrm{PP}\subseteq\mathrm{PSPACE}$ , $\mathrm{MA}\subseteq\mathrm{StoqMA}\subseteq\mathrm{QMA}$ , and $\mathrm{QMA}\subseteq\mathrm{QMA}(2)=\mathrm{QMA}(k)\subseteq\mathrm{NEXP}$ . The constants $c=2/3,\ s=1/3$ are standard, interchangeable with any $1/\mathrm{poly}$ gap.

Prerequisites. Quantum Merlin-Arthur (QMA) · The Local Hamiltonian Problem · The Quantum Cook-Levin Theorem · The Complexity Class BQP. Leads to. Quantum Interactive Proofs (QIP) · QIP = PSPACE · MIP* = RE · BQP is Contained in PP and PSPACE.

Ask the tutor: Ask me to walk through why any single QMA variant — QCMA, QMA(2), QMA $_1$ , or StoqMA — is or is not known to equal QMA, and I will trace the exact knob and the obstruction step by step.

Are QCMA and QMA really different, or is that just unproven?

Nobody has proven them different in the standard unrelativized world — $\mathrm{QCMA}=\mathrm{QMA}$ remains open. The evidence is circumstantial but strong: relative to a quantum oracle Aaronson and Kuperberg (2007) separated them, and later work pushed toward classical-oracle separations, which means any proof of equality must be non-relativizing — the fingerprint of a hard question. The intuition is that a general quantum witness is an entangled state with no short classical description, so it is hard to see how a polynomial classical string could always stand in for it. But "hard to see" is not a proof, and this is one of the central open problems in quantum complexity.

Why is QMA(2) so much harder to bound than QMA?

Because the unentanglement promise is information Arthur cannot check from inside a single register, so the tricks that give $\mathrm{QMA}\subseteq\mathrm{PP}$ do not transfer. That proof averages over all witnesses, but for QMA(2) the maximization runs only over product states — a non-convex set — and no one knows how to simulate that optimization in polynomial space. The only proven ceiling is NEXP, from nondeterministically guessing exponentially precise descriptions of both witnesses. Closing the QMA-to-NEXP gap for QMA(2) would resolve whether unentanglement is a real computational resource.

What exactly is the sign problem, and how does StoqMA capture it?

The sign problem is what makes quantum Monte Carlo fail: when off-diagonal matrix elements are positive, the path-integral weights can be negative, and averaging over signed weights blows up statistically. A stoquastic Hamiltonian has all off-diagonal elements non-positive in a fixed basis — exactly the condition that removes the negative weights. StoqMA is the verification class when the Hamiltonian is stoquastic, so the StoqMA-versus-QMA boundary is the boundary between sign-problem-free systems (efficiently sampleable, MA-like) and general ones. "Curing the sign problem" by a basis change is the same as asking whether a Hamiltonian can be made stoquastic.

Why does perfect completeness deserve its own class, QMA₁?

Because you cannot get it by amplification. Repetition drives completeness to $1-2^{-\mathrm{poly}}$ , arbitrarily close to one, but reaching exactly one needs the accepting projector to have an eigenvector of eigenvalue exactly $1$ — a witness accepted with literal certainty. Over a fixed finite gate set the amplitudes are specific algebraic numbers and that top eigenvalue is generically just below $1$ . So perfect completeness is a structural property of the gate set, not something you dial in, and QMA $_1$ may be strictly smaller than QMA. Its complete problem is quantum-SAT: does a frustration-free local Hamiltonian have a zero-energy ground state?

Is StoqMA a quantum class or a classical one?

Genuinely in between, which is the point. A StoqMA verifier is a restricted quantum verifier — it uses Hadamards and quantum ancillas — but decides on a single sign-definite measurement plus classical coin flips, weaker than the arbitrary projective measurement QMA allows. Its completeness and soundness both sit near $1/2$ , separated by only $1/\mathrm{poly}$ , unlike QMA's $2/3$ versus $1/3$ . The result is $\mathrm{MA}\subseteq\mathrm{StoqMA}\subseteq\mathrm{QMA}$ with the sharper ceiling $\mathrm{StoqMA}\subseteq\mathrm{AM}$ — quantum machinery, classical-flavoured power, exactly what sign-problem-free physics should have.

If QMA(k) collapses to QMA(2), why not to QMA(1)?

The collapse comes from Harrow–Montanaro's product test: given a state on $k$ registers it certifies closeness to a fully product state, letting Arthur simulate $k$ unentangled provers with two. But no test certifies that a single register is unentangled across an internal cut — a single register is just a register, with no promise about its structure. So the hierarchy flattens at level two, where the promise between two distinct provers survives, but not to level one, where it vanishes. The gap between $\mathrm{QMA}(1)=\mathrm{QMA}$ and $\mathrm{QMA}(2)$ is exactly one bit of separability promise.

How do all the variants connect to one master problem?

Through the Local Hamiltonian problem, QMA-complete via Kitaev's circuit-to-Hamiltonian construction. Each variant is a structural restriction on that Hamiltonian or its verifier. General local Hamiltonian gives QMA; frustration-free zero-energy gives quantum-SAT, complete for QMA $_1$ ; sign-problem-free terms give the stoquastic local Hamiltonian, complete for StoqMA; a product witness gives product-checkable Hamiltonians for QMA(2). So the whole map is one question — estimate a ground-state energy — asked of Hamiltonians of increasingly special structure, and the complexity class measures how much that structure helps.