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 http://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06
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.
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||19 Jul 2006|
|Last Modified:||26 Dec 2012 08:56|
Repository Staff Only: item control page