  The calculation of ground-state energies of physical systems can be
formalised as the k-local Hamiltonian problem, which is the 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. Examples of such special cases are the
Heisenberg and Ising models from condensed-matter physics.
  In this work we characterise 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
characterisation 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 characterisation
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 Schaefer's dichotomy theorem for
boolean constraint satisfaction problems.
