QMA & the Local Hamiltonian Problem
The quantum Cook–Levin theorem.
Cook and Levin showed that satisfiability of Boolean formulas captures all of NP. Kitaev proved the quantum analogue: estimating the ground-state energy of a local Hamiltonian captures every problem with an efficiently checkable quantum proof. The bridge between computation and physics is a superposition over the history of a computation.
What you’ll learn
- Define QMA, QCMA and MA, and explain parallel and in-place (Marriott–Watrous) error reduction.
- Prove using strong error reduction.
- Show that the -local Hamiltonian problem is in QMA.
- Construct the Feynman–Kitaev history-state Hamiltonian, compute the spectrum of its propagation term, and explain why it is 5-local.
- Describe the reductions to 2-local and lattice Hamiltonians via perturbative gadgets, and their consequences for physics and chemistry.
Quantum proofs
Immediately, and (ignore the witness). Mixed witnesses never help a cheating prover, because acceptance probability is linear in the density matrix and is maximized at a pure state.
The acceptance operator on the -dimensional witness space, with .
In-place amplification pushes soundness below without enlarging the witness, so even the trace, a sum of eigenvalues, stays small.
A maximally mixed witness is a uniformly random basis string: a quantum computation with no prover at all.
Deciding whether this acceptance probability is or is a threshold question about a GapP quantity, exactly as in the proof of . Hence , a containment first shown by Kitaev and Watrous.
The local Hamiltonian problem
Shift and rescale each term (and the thresholds accordingly).
acts on qubits, so this two-outcome measurement is a small circuit: diagonalize , then rotate an ancilla by an eigenvalue-dependent angle.
With a ground state as witness, at least in yes-instances; no witness exceeds in no-instances.
The gap is amplified by error reduction.
Kitaev's theorem: the Feynman–Kitaev clock
Cook–Levin writes down the whole tableau of a computation and checks each step locally. Quantumly, the intermediate states are entangled -qubit states that cannot be copied side by side. Feynman's idea (1985), turned into a proof by Kitaev, is to superpose them instead, labeled by a clock.
Each term penalizes one kind of inconsistency with an accepting history.
At time the ancillas must be ; at time the output qubit should read .
Penalizes any mismatch between the state at time and applied to the state at time .
In the frame of the computation the gates disappear: what remains is half the Laplacian of a path graph on the clock states.
The null space consists of history states, one for each witness; the spectral gap is .
In yes-instances only contributes. In no-instances (every witness accepted with probability ), Kitaev's geometric lemma gives the lower bound for a constant . After amplification, the promise gap is .
Encode the clock in unary, on clock qubits, and use two-qubit gates . On how many qubits does one propagation term act (for )?
Show the answer
5 qubits
only needs to check clock qubits and and flip qubit : it is on clock qubits . With the two qubits of that makes 5. Illegal clock strings are penalized by the 2-local , and , are 2-local. Hence "5-local".
Down to two-local, and what it means
| Result | Setting | Reference |
|---|---|---|
| QMA-complete | 5-local | Kitaev 1999; Kitaev, Shen & Vyalyi 2002 |
| QMA-complete | 3-local | Kempe & Regev 2003 |
| QMA-complete | 2-local qubit Hamiltonians | Kempe, Kitaev & Regev 2006 |
| QMA-complete | 2-local, qubits on a 2D square lattice | Oliveira & Terhal 2008 |
| QMA-complete | nearest-neighbor chain of constant-dimensional qudits | Aharonov, Gottesman, Irani & Kempe 2009 |
| P, NP-, StoqMA- or QMA-complete | classification of 2-local qubit interaction types | Cubitt & Montanaro 2016 |
| in NP | commuting 2-local Hamiltonians | Bravyi & Vyalyi 2005 |
| in P | ground states of gapped 1D Hamiltonians | Landau, Vazirani & Vidick 2015 |
A mediator qubit pays energy for being in . and act on disjoint sets of qubits, so , and each coupling is only one qubit more local than or .
Second-order perturbation theory (Schrieffer–Wolff) in the low-energy subspace . The first-order term vanishes because flips the mediator.
The product acts on the union of the two supports: a higher-locality interaction emerges from lower-locality couplings. The , terms are less local and can be compensated. Iterating such subdivision gadgets, with a third-order gadget for 3-body terms, reduces 5-local to 2-local at the price of polynomially large .
Two consequences:
- Nature does not always cool efficiently. A physical system that always relaxed quickly to its ground state would solve QMA-hard problems. Frustrated systems and spin glasses get stuck instead.
- Quantum chemistry needs good initial states. Phase estimation finds a ground energy efficiently only when given a trial state with non-negligible overlap with the ground state. With such a guiding state, ground-energy estimation to inverse-polynomial precision becomes BQP-complete (Gharibian & Le Gall 2022). The hardness lives in finding the state.
Which local Hamiltonian problem is not believed to be QMA-complete?
- 2-local qubit Hamiltonians on a 2D square lattice
- 3-local qubit Hamiltonians
- Commuting 2-local Hamiltonians
- Nearest-neighbor Hamiltonians on a chain of constant-dimensional qudits
Show the answer
C. Commuting 2-local Hamiltonians
Bravyi and Vyalyi showed that the commuting 2-local Hamiltonian problem is in NP: the structure of commuting terms lets a classical certificate describe a ground state. If it were QMA-complete, QMA would collapse to NP.
Key takeaways
- QMA = efficiently verifiable quantum proofs; , the last via in-place amplification and a trace argument.
- The -local Hamiltonian problem with an inverse-polynomial promise gap is in QMA: measure a random term on the claimed ground state.
- Kitaev's history-state Hamiltonian makes QMA verification a ground-energy question; is a path Laplacian with gap , and a unary clock makes it 5-local.
- Perturbative gadgets reduce hardness to 2-local qubit, 2D lattice and even 1D qudit Hamiltonians.
- Worst-case ground-state problems are hard even for quantum computers; quantum chemistry speedups hinge on good initial states.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why does the Feynman–Kitaev construction superpose the computation over a clock instead of writing out every intermediate state, as the Cook–Levin tableau does?
- To make the Hamiltonian stoquastic
- Intermediate states are entangled -qubit states that cannot be copied into a tableau; superposing them over a clock turns "step follows from step " into a local hopping term
- A clock register uses fewer qubits than the witness
- Measuring intermediate states would collapse the witness
Show the answer
B. Intermediate states are entangled -qubit states that cannot be copied into a tableau; superposing them over a clock turns "step follows from step " into a local hopping term
In the history state, compares consecutive time slices coherently with terms like , which are local once the clock is unary.
Why must the promise gap be at least inverse-polynomial?
- Otherwise the problem would not be in NP
- Otherwise 1-local Hamiltonians would suffice
- Kitaev's construction produces exponentially large gaps
- The verifier's acceptance gap is and must be amplified with polynomially many repetitions; with exponentially small gaps the problem becomes PSPACE-complete
Show the answer
D. The verifier's acceptance gap is and must be amplified with polynomially many repetitions; with exponentially small gaps the problem becomes PSPACE-complete
Bounded-error verification needs an inverse-polynomial gap to amplify. Precise (exponentially small gap) local-Hamiltonian estimation is PSPACE-complete.
How does the spectral gap of scale with the number of gates ?
Show the answer
A.
is unitarily equivalent to half the Laplacian of a path on vertices, with gap .
In the proof of , why is in-place (Marriott–Watrous) amplification used rather than parallel repetition?
- Parallel repetition is unsound against entangled witnesses
- PP machines cannot repeat computations
- Parallel repetition multiplies the witness length, so the soundness error never drops below the inverse dimension; in-place amplification keeps fixed while
- It is not needed: plain QMA soundness already gives
Show the answer
C. Parallel repetition multiplies the witness length, so the soundness error never drops below the inverse dimension; in-place amplification keeps fixed while
The argument needs soundness smaller than so that stays small. With copies, the witness space has dimension while soundness only falls like , so the trace bound never improves.
Further reading
- A. Yu. Kitaev, A. H. Shen & M. N. Vyalyi, Classical and Quantum Computation, Ch. 14 (AMS, 2002).
- J. Kempe, A. Kitaev & O. Regev, "The complexity of the local Hamiltonian problem", SIAM Journal on Computing 35, 1070 (2006).
- C. Marriott & J. Watrous, "Quantum Arthur–Merlin games", Computational Complexity 14, 122 (2005).
- S. Gharibian, Y. Huang, Z. Landau & S. W. Shin, "Quantum Hamiltonian complexity", Foundations and Trends in Theoretical Computer Science 10, 159 (2015).
- R. P. Feynman, "Quantum mechanical computers", Optics News 11, 11 (1985).