The Complexity of the Local Hamiltonian Problem

By Julia Kempe, Alexei Y. Kitaev, Oded Regev. Foundations of Software Technology and Theoretical Computer Science, 2004

753 citations recorded by the source corpus.

The k-LOCAL HAMILTONIAN problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k > 2. It was known that the problem is QMA-complete for any k > 3. On the other hand 1-LOCAL HAMILTONIAN is in P, and hence not believed to be QMA-complete. The complexity of the 2-LOCAL HAMILTONIAN problem has long been outstanding. Here we settle the question and show that it is QMA-complete. We provide two independent proofs; our first proof uses a powerful technique for analyzing the sum of two Hamiltonians; this technique is based on perturbation theory and we believe that it might prove useful elsewhere. The second proof uses elementary linear algebra only. Using our techniques we also show that adiabatic computation with two-local interactions on qubits is equivalent to standard quantum computation.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/e66c2488db9cd957691e0f2e04f7673ba7fa88bb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Efficient Quantum Algorithms for Simulating Sparse Hamiltonians (2005, background): “This is distinct from another use of the term concerning finding the ground state of a Hamiltonian, for which evidence exists of intractability (QMA-hard) [ 3 ].”
Practical quantum advantage in quantum simulation (2022, background): “…a quantum simulator avoids exponential scaling for memory requirements, the runtime for producing the lowest-energy states adiabatically can still scale exponentially with the system size—in fact, finding a ground state is at least as difficult as running an arbitrary quantum computation 59 .”
Spin- 1 ∕ 2 particles moving on a two-dimensional lattice with nearest-neighbor interactions can realize an autonomous quantum computer (2005, methodology): “In order to use a perturbation theorem of [8] we first have to rephrase some notations used in [8, 32].”
Universal computation by quantum walk. (2008, methodology): “Feynman’s original quantum computer Hamiltonian [24] has been used to construct QMA-complete [27] and BQP-complete [28, 29] problems, in addition to showing the universality of adiabatic evolution [17, 18, 19].”
Simulating chemistry using quantum computers. (2010, background): “While the two are known to be computationally equivalent—any computation that can be performed in one model can performed in the other in a comparable amount of time (6,66,89)—different problems are solved more naturally in different models.”
Adiabatic quantum computation is equivalent to standard quantum computation (2004, methodology): “5 Related Work After the preliminary version of this paper appeared [2], the results regarding Quantum-NP completeness were tightened by [21] to show that the 2-local Hamiltonian problem is Quantum-NP complete.”
Adiabatic Quantum Computing (2016, methodology): “This was reduced to 3-local (Kempe and Regev, 2003; Nagaj and Mozes, 2007) and then to 2-local (Kempe et al., 2006).”
Training Variational Quantum Algorithms Is NP-Hard. (2021, background): “Prominently, finding the ground state energy of a local Hamiltonian is QMA-hard [15, 16].”
Digitized adiabatic quantum computing with a superconducting circuit (2015, background): “In addition, longrange multibody interactions can be assembled to aid in quantum tunneling [20] or to encode the non-local terms required for fermionic simulations [21, 22], which is otherwise hampered by limited connectivity.”
Quantum information processing with superconducting circuits: a review (2016, background): “There are many prob lems described by quantum Hamiltonians that are hard for quantum computers, residing in QMA, or worse (QMAhard, or NPhard) [83–94].”
Schrieffer-Wolff transformation for quantum many-body systems (2011, methodology): “Although in many important cases the z-dependence of Heff(z) can be neglected [18], there is no systematic way of getting rid of this dependence.”
Quantum Arthur–Merlin games (2004, background): “Quantum computational variants of interactive proof systems have previously been considered in several papers, including the general multiple-message case (Gutoski & Watrous 2005; Kitaev & Watrous 2000; Kobayashi & Matsumoto 2003; Rosgen & Watrous 2004; Watrous 2003) as well as the singlemessage cas”