QMA (Quantum Merlin-Arthur)

QMA (Quantum Merlin-Arthur) is the quantum generalization of the classical complexity class NP. In the classical setting, NP contains problems for which a short certificate (a “witness”) can be verified in polynomial time. QMA extends this by allowing the witness to be a quantum state and the verifier to be a polynomial-time quantum algorithm (a BQP machine). Formally, a problem is in QMA if there exists a polynomial-time quantum verifier V such that: when the answer is “yes,” there exists a quantum state (the witness) that V accepts with probability at least 2/3; and when the answer is “no,” V rejects every possible quantum state with probability at least 2/3. The gap between completeness and soundness can be amplified by repeating the verification, just as in BQP. QMA sits above both NP and BQP in the complexity hierarchy, though proving these separations unconditionally remains an open problem.

The canonical QMA-complete problem is the Local Hamiltonian problem, established by Alexei Kitaev in 2002 via a quantum analogue of the Cook-Levin theorem. The Local Hamiltonian problem asks: given a Hamiltonian H that is a sum of terms each acting on at most k qubits, is the ground state energy of H below some threshold a, or above some threshold b (with b - a inverse-polynomial in the system size)? Kitaev showed that this problem is QMA-complete, meaning every problem in QMA reduces to it in polynomial time. The proof constructs a “clock Hamiltonian” (now called the Feynman-Kitaev circuit Hamiltonian) whose ground state encodes the history of a quantum computation, so verifying the ground state energy is equivalent to verifying whether a quantum computation accepts. This result established the Local Hamiltonian problem as the quantum analogue of SAT, making it the central hard problem of quantum complexity theory.

The QMA-completeness of the Local Hamiltonian problem has direct practical implications for quantum chemistry and materials science. Computing the ground state energy of a molecular or solid-state Hamiltonian is, in general, a QMA-hard problem, which explains why classical computers struggle with strongly correlated electron systems. Variational algorithms like the Variational Quantum Eigensolver (VQE) approach this problem heuristically: they parametrize a quantum circuit ansatz and minimize the expected energy via classical optimization. VQE does not solve QMA-hard instances in polynomial time (no known algorithm does), but it can find good approximate energies for systems of physical interest, where the Hamiltonian has structure that makes heuristic approaches effective. Understanding QMA gives learners a principled reason why quantum chemistry is hard and why variational quantum algorithms are heuristic rather than guaranteed.