In short
QMA — Quantum Merlin-Arthur — is the quantum analogue of NP. A problem is in QMA if for every yes-instance there exists a quantum state |\psi\rangle on polynomially many qubits (the "quantum witness") such that a polynomial-time quantum verifier accepts with probability \geq 2/3, while for every no-instance, every quantum state is rejected with probability \geq 2/3. Think of it as NP with a quantum proof.
Classical NP has a famous complete problem: SAT (Cook-Levin, 1971). QMA has a famous complete problem too: the k-local Hamiltonian problem — given a Hermitian operator H = \sum_j H_j that is a sum of terms each acting on at most k qubits, decide whether the ground-state energy is below a or above b (with a promise gap b - a \geq 1/\mathrm{poly}(n)). Kitaev (1999) proved this is QMA-complete for k \geq 5, later tightened to k = 2. His proof — the history-state construction — is the quantum Cook-Levin theorem: given any quantum verification circuit, build a local Hamiltonian whose ground state encodes the entire time-history of the circuit.
Containments: \mathrm{NP} \subseteq \mathrm{QMA} \subseteq \mathrm{PP} \subseteq \mathrm{PSPACE}. The first inclusion is easy (a classical witness is a trivial quantum one). The second, \mathrm{QMA} \subseteq \mathrm{PP}, is a theorem of Marriott-Watrous (2004). \mathrm{BQP} \subseteq \mathrm{QMA} (a BQP algorithm ignores the witness). Whether \mathrm{QMA} = \mathrm{NP} is open, almost certainly no.
Why it matters beyond complexity theory: QMA-hardness of local Hamiltonian is a hard ceiling on quantum algorithms for chemistry. If you could efficiently compute ground-state energies of arbitrary k-local Hamiltonians, you would collapse QMA into BQP — conjecturally false. Every practical quantum chemistry algorithm (VQE, phase estimation, imaginary-time evolution) is navigating around this ceiling.
NP has a canonical complete problem: SAT. If you can solve 3-SAT in polynomial time, you can solve every problem in NP in polynomial time — that is the content of the Cook-Levin theorem (Stephen Cook, 1971; Leonid Levin, independently, 1973). It is one of the most important theorems in all of computer science, because it reduces an entire universe of verification problems to a single concrete combinatorial one.
Quantum complexity theory has its own version of this story. The class of problems with short quantum witnesses verifiable by a polynomial-time quantum machine is called QMA. And there is a canonical QMA-complete problem: the k-local Hamiltonian problem — physically, "given a sum of k-body quantum interactions, is the lowest possible energy of the system below a threshold?" Alexei Kitaev proved this problem QMA-complete in 1999, using a construction so elegant that it is now known as the quantum Cook-Levin theorem. It was one of the first structural results linking quantum computation to condensed-matter physics, and it remains the single cleanest reason physicists and complexity theorists have to talk to each other.
This chapter defines QMA carefully, introduces the k-local Hamiltonian problem, sketches Kitaev's proof via the history-state construction, and draws the containment diagram placing QMA between BQP and PP. By the end, you should see why "find the ground state" is not a simulation-engineering challenge but a complexity-theoretic wall.
From NP to QMA — one change, large consequences
NP is defined by a verification game. Arthur, a polynomial-time classical verifier, receives an input x and a witness w from Merlin, a possibly-malicious prover. Arthur decides yes or no based on (x, w). For yes-instances, there is a witness Arthur accepts; for no-instances, no witness fools him. This is the Merlin-Arthur protocol, and NP is the class of problems solvable in polynomial time with one-shot, error-free verification (technically a special case; NP has perfect completeness and perfect soundness).
QMA keeps the structure but changes two details. First, Arthur's verifier is a polynomial-time quantum circuit. Second, Merlin's witness is a quantum state |\psi\rangle on polynomially many qubits, not a classical bit-string. Arthur runs his circuit on the combined input |x\rangle \otimes |\psi\rangle and measures a designated output qubit. The protocol allows bounded error: on yes-instances, the best witness makes Arthur accept with probability \geq 2/3; on no-instances, every witness is rejected with probability \geq 2/3.
The single change from "classical witness, classical verifier" to "quantum witness, quantum verifier" has two immediate consequences:
- The witness can carry quantum information — entanglement, superposition, phase — that no classical witness could.
- The verifier can perform quantum measurements on the witness, extracting information that no classical verifier could extract.
QMA — Quantum Merlin-Arthur
A promise problem L = (L_{\text{yes}}, L_{\text{no}}) is in QMA if there exists a polynomial p and a polynomial-time uniform family of quantum circuits \{V_n\} (the verifier) such that for every input x of length n:
- Completeness. If x \in L_{\text{yes}}, there exists a quantum state |\psi\rangle on p(n) qubits such that V_n applied to |x\rangle \otimes |\psi\rangle \otimes |0^{\otimes m}\rangle (with m ancilla qubits) accepts with probability \geq 2/3.
- Soundness. If x \in L_{\text{no}}, then for every quantum state |\psi\rangle on p(n) qubits, V_n accepts with probability \leq 1/3.
The 2/3 and 1/3 are a convention — any constants with a positive gap define the same class by amplification (Marriott-Watrous, 2004, showed amplification works for QMA with minimal extra witnesses).
Every phrase does work. "Promise problem" because QMA is most naturally stated with promise gaps — some inputs are yes, some are no, and on everything else the algorithm's behaviour is unspecified. "Verifier" because Arthur checks; he does not discover. "Quantum state" because the witness is now a full quantum state, not just a list of bits — in principle, a complex vector in 2^{p(n)}-dimensional Hilbert space. "Ancilla qubits" because Arthur, like any quantum circuit, needs scratch space.
Why "quantum witness" is the key ingredient
A classical witness is a finite string of bits. If Merlin can construct it, Arthur can store it, re-read it, photocopy it, or challenge Merlin to commit to it before seeing Arthur's challenge. A classical witness is an object.
A quantum witness is a state — a vector in Hilbert space. Merlin cannot photocopy it (no-cloning). Arthur cannot re-read it after measuring (collapse). Arthur can only apply a unitary to it, measure once, and get a bounded-error answer. A quantum witness is an event that happens once.
This is why QMA is strictly more subtle than NP. A classical verifier could record a classical witness and verify forever; a quantum verifier must commit to one protocol, run it, and accept the outcome. The proof rules are different, and some of the most natural classical protocol techniques (like the Fiat-Shamir heuristic, or naive replay attacks) do not apply quantumly.
There is also an upside. A quantum witness can encode coherent superpositions that no classical bit-string can match. The ground state of a Hamiltonian — the lowest-energy quantum state of a physical system — is typically a complicated entangled superposition. Describing it classically might require exponentially many bits. Sending it as a quantum state takes polynomially many qubits. This is the mechanism that makes the local Hamiltonian problem naturally QMA.
The k-local Hamiltonian problem
Now the protagonist.
A Hermitian operator on n qubits is a 2^n \times 2^n matrix H with H = H^\dagger. Its eigenvalues are real. By the spectral theorem, H = \sum_i E_i |\phi_i\rangle\langle\phi_i| where E_0 \leq E_1 \leq \ldots are the eigenvalues and |\phi_i\rangle are the corresponding orthonormal eigenstates. E_0 is the ground-state energy; |\phi_0\rangle is the ground state.
The operator H is k-local if it can be written as
where each H_j is a Hermitian operator acting nontrivially on at most k qubits (and as the identity on all others). The number of terms m must be polynomial in n. Each H_j is a small matrix — a 2^k \times 2^k matrix that can be described with a constant number of entries (since k is a constant).
The $k$-local Hamiltonian problem ($k$-LH)
Given:
- A description of a k-local Hamiltonian H = \sum_j H_j on n qubits (each H_j specified as a 2^k \times 2^k matrix with polynomial-bit entries).
- Real numbers a < b with b - a \geq 1/\mathrm{poly}(n) (the promise gap).
Decide:
- Yes: the ground-state energy E_0(H) \leq a.
- No: the ground-state energy E_0(H) \geq b.
The promise: you are told E_0(H) \leq a or E_0(H) \geq b; inputs in between are not in the language.
The physical reading: H is the Hamiltonian of an imagined quantum system — a list of local interaction terms, one per pair of nearby spins or particles. The ground state is the quantum state the system occupies at zero temperature. The problem asks: is the lowest possible energy of this system below a threshold, or above another? In physics language: "is the ground state gapped below a or gapped above b?"
The Hilbert space has dimension 2^n, exponential in the number of qubits. Describing an arbitrary state in it takes 2^n complex numbers. Computing the lowest eigenvalue of an arbitrary 2^n \times 2^n matrix is, in principle, a 2^n-dimensional eigenvalue problem — infeasible classically for large n. But the k-local structure gives a compact description of H itself. The question is: does the locality save us?
Why k-LH is in QMA
k-LH being in QMA is the easy direction. Here is the verification protocol.
The honest Merlin prepares the quantum ground state |\phi_0\rangle of H — a state on n qubits — and sends it to Arthur. Arthur's verification job is to estimate \langle\phi_0|H|\phi_0\rangle, the ground-state energy, and check whether it is below a or above b.
Estimating \langle\psi|H|\psi\rangle for a k-local H is efficient. Write H = \sum_j H_j. Then \langle\psi|H|\psi\rangle = \sum_j \langle\psi|H_j|\psi\rangle. Each \langle\psi|H_j|\psi\rangle is the expectation of a k-qubit operator — which Arthur can estimate using a few measurements of the qubits H_j acts on.
Arthur's protocol (sketch).
- Pick a random term H_j uniformly from the m terms.
- Use the k-qubit structure of H_j to measure the expectation \langle\psi|H_j|\psi\rangle via a standard POVM. (Technically this requires expanding H_j in a Pauli basis and measuring each Pauli term.)
- Scale up: \langle\psi|H|\psi\rangle \approx m \cdot \mathbb{E}_j[\langle\psi|H_j|\psi\rangle].
- Repeat polynomially many times to get an additive 1/\mathrm{poly}(n) estimate.
- If the estimate is below \frac{a+b}{2}, accept; otherwise reject.
If Merlin sent the true ground state, the estimate is close to E_0 \leq a, so Arthur accepts. If we are in a no-instance (E_0 \geq b), then every state |\psi\rangle satisfies \langle\psi|H|\psi\rangle \geq E_0 \geq b (since the expectation of any state in H is at least the lowest eigenvalue), so no witness makes Arthur accept. Why the soundness argument: the lowest eigenvalue of H is exactly \min_{|\psi\rangle} \langle\psi|H|\psi\rangle by the variational principle. If E_0 \geq b, every \psi gives expectation \geq b, so Arthur's estimate is above b and he rejects.
So k-LH is in QMA, with the quantum witness being the ground state and the verifier being "sample a random term, estimate its expectation."
Kitaev's theorem — the quantum Cook-Levin
Kitaev's theorem (Quantum Cook-Levin, 1999)
The k-local Hamiltonian problem is QMA-complete for k \geq 5. Subsequent work improved this:
- Kempe and Regev (2003): QMA-complete for k = 3.
- Kempe, Kitaev, and Regev (2006): QMA-complete for k = 2.
Consequence: 2-local Hamiltonian is to QMA what 3-SAT is to NP. If you could solve 2-LH in BQP, you would collapse QMA into BQP — which is considered very unlikely.
The completeness direction — "every QMA problem reduces to k-LH" — is Kitaev's main contribution. The proof is the history-state construction, and it is the quantum analogue of Cook's tableau proof for SAT.
The idea — encode the entire verification history as a ground state
Fix a QMA problem L with verifier circuit V_n on input x. V_n is a sequence of T = \mathrm{poly}(n) gates U_1, U_2, \ldots, U_T acting on the witness + ancillas. Merlin's job (in the QMA protocol) is to provide a witness |\psi\rangle such that V_n on |\psi\rangle accepts with high probability.
Kitaev builds a Hamiltonian H_V on the circuit's qubits plus a clock register tracking which time step the computation is at. The Hamiltonian has three parts:
- H_{\text{init}} penalises histories that do not start with ancillas in |0\rangle at clock time 0.
- H_{\text{prop}} penalises pairs (|\phi_t\rangle, |\phi_{t+1}\rangle) where |\phi_{t+1}\rangle \neq U_t |\phi_t\rangle — i.e., transitions that don't follow the actual gate sequence.
- H_{\text{out}} penalises histories that end in the "reject" state at the final clock time.
The crucial trick: each term is k-local for small k. H_{\text{prop}}, for instance, checks one gate at a time, and since each gate U_t acts on O(1) qubits, the term penalising a bad transition only needs to see those qubits plus the clock register. With a clever unary encoding of the clock, this works out to 5-local in Kitaev's original proof.
The ground state. If there exists a witness |\psi\rangle that V_n accepts, the ground state of H_V is the history state
where |\phi_t\rangle = U_t U_{t-1} \cdots U_1 (|\psi\rangle \otimes |0\rangle^{\otimes m}) is the state of the circuit at time t, starting from the good witness. The history state has zero (or near-zero) energy: it satisfies all three penalty terms simultaneously, because it starts correctly, follows the gates correctly, and ends in the accept state.
No witness ⇒ high ground-state energy. Conversely, if no witness causes V_n to accept with high probability, every state has a significant energy cost for at least one of the penalty terms — and a careful analysis (using a Clairaut-type lemma and a quantum Jordan-like decomposition) shows the ground-state energy is at least b for some b > a with b - a = 1/\mathrm{poly}(n). This gives the promise gap.
The construction is the cleanest known way to turn a quantum circuit into a Hamiltonian ground-state problem. It is the quantum counterpart of Cook's tableau: Cook's tableau encoded a classical Turing machine's space-time trace; Kitaev's history state encodes a quantum circuit's space-time trace as a coherent superposition.
Containments — where QMA sits
The known relations:
\mathrm{NP} \subseteq \mathrm{QMA}. A classical witness is a special case of a quantum one — set the qubits to the classical bit-string. The verifier ignores the quantumness and runs the classical check. The reduction is immediate.
\mathrm{BQP} \subseteq \mathrm{QMA}. A BQP algorithm is a QMA verifier that ignores the witness: whatever Merlin sends, Arthur runs his circuit on the input alone and outputs the answer. The witness is redundant, but its existence satisfies the QMA definition vacuously.
\mathrm{QMA} \subseteq \mathrm{PP}. Marriott and Watrous (2004). The proof uses a simulation of the QMA verifier that integrates over all possible quantum witnesses and all measurement outcomes, showing that the maximum acceptance probability is computable by a probabilistic Turing machine with unbounded error.
\mathrm{QMA} \subseteq \mathrm{PSPACE}. Follows from \mathrm{QMA} \subseteq \mathrm{PP} \subseteq \mathrm{PSPACE}. A direct simulation is also possible.
What is not known:
- Whether \mathrm{QMA} = \mathrm{NP} (almost certainly no — the quantum witness adds genuine power).
- Whether \mathrm{QMA} \subseteq \mathrm{BQP} (very unlikely — this would mean local Hamiltonian is efficiently solvable).
- Whether \mathrm{QMA} = \mathrm{QCMA}, where QCMA is "classical witness, quantum verifier" (a nonstandard middle ground; believed to be strict \mathrm{QCMA} \subsetneq \mathrm{QMA}).
Example 1: A toy 2-local Hamiltonian encoding a simple decision
To see the flavour, build a tiny 2-local Hamiltonian on n = 2 qubits whose ground state answers a trivial decision.
The problem. You are told a single bit b \in \{0, 1\}, and you want the ground state to be |b, b\rangle (both qubits agree with b).
The Hamiltonian. Define
where P_{bb} = |b\rangle\langle b|_1 \otimes |b\rangle\langle b|_2 is the projector onto |bb\rangle, and Z_1 Z_2 is the product of Pauli-Z operators on qubits 1 and 2.
Step 1. The second term (I - Z_1 Z_2)/2 evaluates to 0 on |00\rangle and |11\rangle (aligned states) and to 1 on |01\rangle and |10\rangle (anti-aligned). Why: Z|0\rangle = |0\rangle and Z|1\rangle = -|1\rangle, so Z_1 Z_2 has eigenvalue +1 on |00\rangle, |11\rangle and -1 on |01\rangle, |10\rangle. The combination (I - Z_1 Z_2)/2 maps these to 0 and 1 respectively.
Step 2. The first term (I - P_{bb}) is 0 on |bb\rangle and 1 on every other basis state (its range is the orthogonal complement of |bb\rangle).
Step 3. Summing, the energy of each basis state:
| State | Term 1 | Term 2 | Total (if b = 0) |
|---|---|---|---|
| |00\rangle | 0 | 0 | 0 |
| |01\rangle | 1 | 1 | 2 |
| |10\rangle | 1 | 1 | 2 |
| |11\rangle | 1 | 0 | 1 |
Step 4. The ground state (for b = 0) is |00\rangle with energy 0. The first excited state is |11\rangle with energy 1. The gap is 1. Setting a = 0.4 and b = 0.6 gives a valid promise: the ground state energy is either \leq 0.4 (yes, Hamiltonian has ground energy 0) or \geq 0.6 (no, would be an artificial modification where we force the ground energy up).
Step 5. Arthur's QMA verifier receives this Hamiltonian and accepts a witness by measuring both Pauli terms. If Merlin sends the true ground state |00\rangle, Arthur measures 0 on both, accepts. If Merlin sends anything else, at least one term returns nonzero energy on average, and Arthur rejects.
Result. The QMA witness for "the ground state energy is \leq 0.4" is the state |00\rangle itself. Arthur measures both Pauli terms, gets eigenvalues +1 on each (so 0 energy contribution), and accepts. This toy example shows the mechanism: a local Hamiltonian encodes a decision, and the ground state is the answer. Real QMA-complete instances are much more intricate, but the template is the same.
Example 2: SAT (NP-complete) versus 2-LH (QMA-complete)
A comparison, side by side, of the two canonical complete problems.
| Aspect | 3-SAT (NP-complete) | 2-Local Hamiltonian (QMA-complete) |
|---|---|---|
| Instance | Boolean formula \phi = C_1 \wedge C_2 \wedge \ldots \wedge C_m, each C_i a clause over 3 variables | Hermitian operator H = \sum_j H_j, each H_j a 4\times 4 matrix on 2 qubits |
| Variables | n Boolean variables x_1, \ldots, x_n \in \{0,1\} | n qubits, each a vector in \mathbb{C}^2 |
| Witness | Assignment (a_1, \ldots, a_n) \in \{0,1\}^n | Quantum state |\psi\rangle \in (\mathbb{C}^2)^{\otimes n} |
| Witness size | n bits | 2^n complex amplitudes (but sent as n qubits) |
| Verification | Evaluate \phi on assignment, check clauses | Sample a term H_j, estimate \langle\psi|H_j|\psi\rangle |
| Yes-instance | \exists assignment satisfying all clauses | Ground-state energy E_0 \leq a |
| No-instance | No assignment satisfies all clauses | Ground-state energy E_0 \geq b |
| Cook-Levin reduction | Every NP problem reduces to 3-SAT (classical tableau) | Every QMA problem reduces to 2-LH (Kitaev's history state) |
Why this parallel matters. The classical Cook-Levin theorem created the intellectual backbone of computational complexity — it gave you one problem whose hardness implied the hardness of thousands of others. Kitaev's theorem does the same thing for quantum complexity. If you could efficiently find the ground state of an arbitrary 2-local Hamiltonian, you could solve every QMA problem — including, conjecturally, problems harder than anything BQP or NP can handle alone. The analogy is not decorative; it is the structural reason quantum chemistry has a complexity-theoretic ceiling.
Result. 2-LH plays for QMA the role 3-SAT plays for NP. An efficient algorithm for either would collapse the corresponding complexity class onto the base (P for SAT, BQP for 2-LH). Neither collapse is believed to happen.
Common confusions
-
"QMA is quantum NP." Structurally, yes — the Merlin-Arthur game with a quantum witness and quantum verifier. But "quantum NP" could mean other things too: NP with a quantum verifier but classical witness (QCMA), or NP with classical verifier but quantum witness (not a useful class — a verifier cannot verify what it cannot measure). Precise language: QMA = quantum witness, quantum verifier.
-
"Factoring is QMA-complete." No. Factoring is in BQP, which is contained in QMA, so factoring is in QMA. But it is not QMA-complete: there is no known reduction from every QMA problem to factoring. BQP problems are "too easy" for QMA-completeness; QMA-complete problems are believed to sit strictly above BQP.
-
"k-local means k-body interactions in a physical Hamiltonian." Yes — this is exactly what "local" means in physics. A term that couples at most k particles directly. The identical concept appears in condensed-matter Hamiltonians (Heisenberg model, Hubbard model, Ising model), which are all k-local. This is why QMA-hardness is a physical statement, not just a complexity-theoretic curiosity.
-
"The ground state of a local Hamiltonian is easy to compute because the Hamiltonian is sparse." The Hamiltonian is sparse (poly-many terms), yes, but the ground state itself can be arbitrarily entangled. Finding the minimum eigenvalue of a 2^n \times 2^n matrix is 2^n-dimensional regardless of how few non-zero entries the matrix has.
-
"QMA-hard means no algorithm exists." No — QMA-hard means "at least as hard as every problem in QMA." If QMA ⊆ BQP (unlikely), then QMA-hard problems would be efficiently solvable on quantum computers. "Hard" always means "hard relative to some class"; it is not an absolute.
-
"QMA verifiers can use the witness indefinitely." They cannot. The witness is a quantum state, and quantum states are destroyed on measurement. The verifier runs once. Marriott-Watrous amplification shows how to amplify with only a constant-qubit extra witness, but the basic protocol is one-shot.
-
"Perfect completeness (QMA₁) is the same as QMA." Open question. QMA₁ requires the verifier to accept yes-instances with probability exactly 1 (not just \geq 2/3). It is not known whether QMA₁ = QMA — Aaronson conjectured they might differ, but the question remains open as of 2026.
Going deeper
You have the definition of QMA, the k-local Hamiltonian problem, Kitaev's history-state construction in sketch, and the containments. This section collects the technical depth: the full Cook-Levin proof structure, QMA_1 (perfect completeness), QCMA (classical witness with quantum verifier), the locality hierarchy for k-LH, and the connection to variational quantum eigensolvers (VQE).
The full Cook-Levin proof via history states
The proof that k-LH is QMA-hard, in more technical terms. Let L be any QMA problem with verifier V = U_T U_{T-1} \cdots U_1 on n_w witness qubits and n_a ancilla qubits (total n = n_w + n_a circuit qubits). Kitaev encodes the clock in a unary register of T qubits (state |t\rangle_{\text{clock}} = |1^t 0^{T-t}\rangle).
H_{\text{init}} is the sum of projectors |1\rangle\langle 1|_a \otimes |0\rangle\langle 0|_{\text{clock}_1} for each ancilla qubit a — penalises ancillas that are |1\rangle at clock time 0.
H_{\text{prop}} is \sum_{t=1}^T H_{\text{prop},t}, where
Why this structure: the two "diagonal" terms penalise the clock register and the computation if the clock transitions from t to t+1. The off-diagonal terms are the hopping amplitude: the Hamiltonian's null space (zero-energy states) is exactly the span of |\phi_t\rangle \otimes |t\rangle_{\text{clock}} for |\phi_{t+1}\rangle = U_t |\phi_t\rangle. Putting this in a single matrix element is how the quantum structure emerges from what would be a classical tableau constraint.
H_{\text{out}} is |0\rangle\langle 0|_{\text{out qubit}} \otimes |1\rangle\langle 1|_{\text{clock}_T} — penalises the "reject" output at the final clock step.
Each term is O(1)-local — specifically, the clock-register coupling makes H_{\text{prop},t} act on a constant number of clock qubits plus the O(1) circuit qubits U_t acts on. With careful analysis, this comes out to 5-local in Kitaev's original version. Kempe-Kitaev-Regev's later techniques (perturbation gadgets and projection lemmas) reduce the locality to 2, at the cost of introducing auxiliary qubits that mediate the originally-higher-locality interactions.
QMA_1 — perfect completeness
\mathrm{QMA}_1 is QMA with completeness 1 instead of 2/3: yes-instances must be accepted with probability exactly 1. For classical complexity, \mathrm{MA}_1 = \mathrm{MA} (completeness can be amplified). For quantum, this is open — the randomness of measurement makes achieving exactly 1 harder. Aaronson (2008) pointed out this is surprisingly subtle; no unconditional proof that \mathrm{QMA}_1 = \mathrm{QMA} is known.
QCMA — classical witness, quantum verifier
\mathrm{QCMA} is the variant where Merlin sends a classical bit-string, but Arthur is a polynomial-time quantum verifier. This is a strict middle ground: \mathrm{NP} \subseteq \mathrm{QCMA} \subseteq \mathrm{QMA}. Whether \mathrm{QCMA} = \mathrm{QMA} is open — most researchers believe they differ (oracle separations suggest so). A specific conjectured-QCMA-but-not-QMA problem: "is there a classical circuit computing a given function to within \epsilon?" — classical witness suffices.
Locality hierarchy for k-LH
The QMA-completeness of k-LH depends on k:
- k = 1 (1-local): in BQP (each term acts on one qubit; diagonalise independently). Not QMA-complete.
- k = 2: QMA-complete (Kempe-Kitaev-Regev 2006).
- k = 3, 4, \ldots: QMA-complete (trivially, since 2-local is).
- k \geq 2 on specific lattice geometries (2D, 3D, nearest-neighbour): still QMA-complete (Oliveira-Terhal 2008; subsequent refinements).
- k = 2 with physical restrictions (e.g., real-valued, translationally invariant, ferromagnetic): various results, some QMA-complete, some polynomial.
This is the locality hierarchy — the QMA-completeness threshold is k = 2, and the interesting variants ask what happens with additional physical or geometric constraints.
Connection to VQE
The Variational Quantum Eigensolver (VQE) is a near-term quantum algorithm: parametrise a quantum state |\psi(\theta)\rangle by classical parameters \theta, minimise \langle\psi(\theta)|H|\psi(\theta)\rangle over \theta using a classical optimiser that queries a quantum computer for expectation values. VQE is popular because it runs on NISQ hardware — no need for full fault tolerance.
But VQE's target — finding the ground state — is a QMA-complete problem in worst case. So VQE cannot work on every input; it relies on the ansatz (choice of parametrisation) being expressive enough for the specific H of interest (molecule, material), and on the classical optimiser avoiding local minima. VQE is a heuristic whose theoretical foundation is brittle, precisely because QMA-hardness says the general problem cannot have an efficient quantum algorithm.
Indian context
Indian quantum information groups — at TIFR Mumbai, IIT Madras, IIT Bombay, IISc Bangalore — contribute actively to QMA-related questions. Work on approximate QMA, state-tomography-based verification, and quantum chemistry ground-state algorithms connects directly to the complexity themes above. The National Quantum Mission's applied-chemistry thrust (drug discovery, materials) is philosophically a bet that real Hamiltonians of interest — specific molecules, specific materials — are easier than worst-case local Hamiltonians, and that heuristics like VQE can find their ground states. QMA-completeness is the backdrop against which this bet is placed.
Where this leads next
- BQP defined — the quantum analogue of P, inside QMA.
- BQP vs NP — the relationship between quantum computation and classical verification, the base case of the QMA-NP extension.
- Complexity classes recap — the classical base: P, NP, BPP, PSPACE, PP.
- Local Hamiltonian problem — deeper into the QMA-complete problem itself.
- VQE — the near-term quantum algorithm for approximating ground states.
- Quantum chemistry introduction — where the physical version of k-LH lives.
References
- Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi, Classical and Quantum Computation (AMS, 2002) — the textbook containing Kitaev's original proof that 5-local Hamiltonian is QMA-complete, with the full history-state construction. AMS page.
- Dorit Aharonov and Tomer Naveh, Quantum NP — A Survey (2002) — survey of QMA, definitions, and early results. arXiv:quant-ph/0210077.
- Julia Kempe, Alexei Kitaev, and Oded Regev, The Complexity of the Local Hamiltonian Problem (2005) — the proof that 2-local Hamiltonian is QMA-complete using perturbation gadgets. arXiv:quant-ph/0406180.
- Wikipedia, QMA — the standard encyclopaedic treatment of QMA.
- Wikipedia, Local Hamiltonian problem — survey-style overview of the QMA-complete problem.
- John Preskill, Lecture Notes on Quantum Computation, Ch. 7 — theory.caltech.edu/~preskill/ph229.