Complexity Classification of Local Hamiltonian Problems

Toby Cubitt, Ashley Montanaro

Research output: Contribution to journalArticle (Academic Journal)peer-review

42 Citations (Scopus)
345 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)268-316
Number of pages49
JournalSIAM Journal on Computing
Issue number2
Early online date23 Mar 2016
Publication statusPublished - Jun 2016


  • quantum complexity
  • quantum computation
  • constraint satisfaction problems
  • local Hamiltonian problem


Dive into the research topics of 'Complexity Classification of Local Hamiltonian Problems'. Together they form a unique fingerprint.

Cite this