A Caltech Library Service

The Complexity of the Local Hamiltonian Problem

Kempe, Julia and Kitaev, Alexei and Regev, Oded (2006) The Complexity of the Local Hamiltonian Problem. SIAM Journal on Computing, 35 (5). pp. 1070-1097. ISSN 0097-5397. doi:10.1137/S0097539704445226.

PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The k-LOCAL Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analogue 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 only elementary linear algebra. Our second 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. Using our techniques we also show that adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemBook Chapter Paper
Additional Information:© 2006 SIAM Received by the editors July 20, 2004; accepted for publication (in revised form) June 23, 2005; published electronically March 3, 2006. A preliminary version of this paper appeared in Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2004. This author’s [JK] work was supported by ACI Sécurité Informatique, 2003-n24; projet “Réseaux Quantiques,” ACI-CR 2002-40 and EU 5th framework program RESQ IST-2001-37559; by DARPA and Air Force Laboratory, Air Force Materiel Command, USAF, under agreement F30602-01-2-0524; by DARPA and the Office of Naval Research under grant FDN-00014-01-1-0826; and during a visit supported in part by the National Science Foundation under grant EIA-0086038 through the Institute for Quantum Information at the California Institute of Technology. This author’s [AK] work was supported in part by the National Science Foundation under grant EIA-0086038. This author’s [OR] work was supported by an Alon Fellowship, the Binational Science Foundation, the Israel Science Foundation, and the Army Research Office grant DAAD19-03-1-0082 and partly supported by ACI Sécurité Informatique, 2003-n24, projet “Réseaux Quantiques.” Part of this author’s work was carried out during a visit at LRI, Université de Paris-Sud, and he thanks his hosts for their hospitality. Discussions with Sergey Bravyi and Frank Verstraete are gratefully acknowledged.
Subject Keywords:quantum computation, local Hamiltonian problem, complete problems, adiabatic computation
Issue or Number:5
Record Number:CaltechAUTHORS:KEMsiamjc06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3919
Deposited By: Archive Administrator
Deposited On:19 Jul 2006
Last Modified:08 Nov 2021 20:13

Repository Staff Only: item control page