Complexity classification of local Hamiltonian problems
arXiv:1311.3161
Abstract
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.
arXiv comment50 pages; v5: essentially published version
References in corpus (24)
- Universal Quantum Computation with the Exchange Interaction
- Information-theoretic aspects of quantum inseparability of mixed states
- Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Entanglement capabilities of non-local Hamiltonians
- Topological Order at Non-zero Temperature
- Simple universal models capture all classical spin physics
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Optimal simulation of two-qubit Hamiltonians using general local operations
- Entanglement entropy in collective models
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- Interacting boson problems are QMA-hard
- Exact gate-sequences for universal quantum computation using the XY-interaction alone
- An intrinsic limit to quantum coherence due to spontaneous symmetry breaking
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- Merlin-Arthur Games and Stoquastic Complexity
- On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
- Monte Carlo simulation of stoquastic Hamiltonians
- The k-local Pauli Commuting Hamiltonians Problem is in P
- On complexity of the quantum Ising model
- Characterization of universal two-qubit Hamiltonians
- Perturbative gadgets without strong interactions
- XXX Spin Chain: from Bethe Solution to Open Problems