NP has a checkable-proof definition. What's the quantum version, and what problem is it actually about?
Topics 16–17 built VQE: a loop that always reports an energy honestly no lower than the truth, because the variational principle proves it. What that loop does not come with is a promise that it ever finds the true ground energy in reasonable time, on a general Hamiltonian. This section asks the question directly: exactly how hard is "find this Hamiltonian's ground energy," as a decision problem, and does the answer explain, rather than just describe, why every near-term algorithm on this page ships without a speed guarantee?
QMA (Quantum Merlin–Arthur) is what you get by taking NP's own definition: a claim is true if some short proof convinces a fast verifier, and false if no proof can, and making both the proof and the verifier quantum. NP already has a name for "make the verifier randomized instead of deterministic": that's MA. QMA takes the further step of letting the witness itself be a quantum state, not a bitstring, and letting the verifier be a quantum circuit acting on it.
QMA's own natural complete problem isn't a puzzle invented for the class: it's a direct generalisation of a physics question this page has already been building toward. Every Hamiltonian on this site (the transmon's, in circuits.html; the surface code's stabilizers, in qec.html; the illustrative H₂ Hamiltonian topic 16 ran VQE against) has a lowest eigenvalue. Its ground energy. The local Hamiltonian problem asks, as a decision problem: given a Hamiltonian built from many small pieces (each acting on only a handful of qubits, "k-local"), is its ground energy below one threshold or above another? That is the formal version of exactly what VQE is trying to estimate.
Formally: L ∈ QMA if there is a uniform family of poly-size quantum circuits V (the verifier) taking an input x and a witness register of poly(|x|) qubits, such that
x ∈ L ⟹ ∃|ψ⟩: Pr[V accepts (x,|ψ⟩)] ≥ 2/3 (completeness)
x ∉ L ⟹ ∀|ψ⟩: Pr[V accepts (x,|ψ⟩)] ≤ 1/3 (soundness)
The constants 2/3 and 1/3 look arbitrary, and classically (for MA) fixing them up by repeating the protocol and taking a majority vote is routine. For QMA it is not: repeating naively means feeding several independent copies of the witness through several verifier runs, and a dishonest Merlin could in principle correlate those copies in ways a classical repeated proof never can, since there is no way to "photocopy" a quantum witness to check it is being reused honestly (the no-cloning theorem, topic 04, again). Marriott & Watrous (Computational Complexity 14(2), 122 (2005)) proved the error can still be pushed exponentially close to 0 without lengthening the witness at all: a genuinely non-trivial theorem, not a formality, and the reason QMA's constants can safely be treated as "far apart enough" throughout this page.
The k-local Hamiltonian problem: given H = Σᵢ Hᵢ, each Hᵢ Hermitian, ‖Hᵢ‖≤1, acting on at most k of n qubits, and thresholds a < b with b−a ≥ 1/poly(n), decide whether the ground energy λmin(H) ≤ a or ≥ b (promised one holds). This is in QMA: the witness is a state close to the true ground state, and Arthur verifies it by estimating ⟨ψ|H|ψ⟩, which he can do using exactly the machinery this page already built, Trotterized Hamiltonian simulation (topic 17) inside phase estimation (topic 12), and accepting if the estimate lands below (a+b)/2. Membership in QMA (Kitaev, Shen & Vyalyi, Classical and Quantum Computation, AMS Graduate Studies in Mathematics vol. 47 (2002)); error-amplification without witness growth (Marriott & Watrous, Computational Complexity 14(2), 122 (2005), arXiv cs/0506068).
This extends the containment chain quantum-mechanics.html already built (P⊆BPP⊆BQP⊆PP⊆PSPACE): BQP⊆QMA trivially (a verifier that ignores the witness and just runs a BQP algorithm is a valid QMA protocol), and QMA⊆PP (Kitaev & Watrous first showed this, in an unpublished argument; Marriott & Watrous gave the first published proof, as a corollary of the same amplification result cited above). So the full chain is P⊆BPP⊆BQP⊆QMA⊆PP⊆PSPACE, and, exactly as before, none of these inclusions is known to be strict.
Why "no proof of speedup" isn't a gap waiting to be closed, for some problems it can't be This is the reason topics 16–17 stated plainly that nobody has proven QAOA or VQE beats its best classical rival: the general local Hamiltonian problem they're both heuristics for is (next topic) provably as hard as anything in QMA, which is believed to sit strictly above BQP, meaning even a perfect, error-corrected quantum computer running the exactly correct algorithm can't be expected to solve every instance quickly. And it's worth being precise about why this problem is the hard one while Shor's isn't: Grover's algorithm (play.html) gives only a quadratic speedup over unstructured search, and Bennett, Bernstein, Brassard & Vazirani (SIAM J. Comput. 26(5), 1510 (1997)) proved that quadratic is the most any quantum algorithm can do against a generic, unstructured problem, which is exactly the shape most NP-complete problems present in the worst case. Factoring is the outlier precisely because it isn't generic: Shor's algorithm exploits real algebraic structure (the period-finding machinery of topics 11–13) that most NP-complete problems simply don't have. "Why Grover isn't enough" and "why Shor is special" are the same fact stated twice. (For a more discursive, less formal tour of this same territory (BQP, QMA, and why complexity theorists find factoring special) see Aaronson, Quantum Computing Since Democritus, CUP, 2013.)
Check yourself
Why is shrinking QMA's 2/3 versus 1/3 gap not just "repeat and take a majority vote"?
Naive repetition feeds several copies of the witness through several verifier runs, and a quantum witness cannot be photocopied. Marriott and Watrous proved the error can still be pushed exponentially close to 0 without a longer witness.