CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06

[img]
Preview
PDF
See Usage Policy.

297Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06

Abstract

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
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
Record Number:CaltechAUTHORS:KEMsiamjc06
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:KEMsiamjc06
Alternative URL:http://dx.doi.org/10.1137/S0097539704445226
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3919
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:19 Jul 2006
Last Modified:26 Dec 2012 08:56

Repository Staff Only: item control page