COMPLEXITY CLASSIFICATION OF LOCAL HAMILTONIAN PROBLEMS

The calculation of ground-state energies of physical systems can be formalized as the k-LOCAL Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes has been shown to be StoqMA-complete by Bravyi and Hastings. The characterization holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.