Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2004 | Submitted
Book Section - Chapter Open

The Complexity of the Local Hamiltonian Problem

Abstract

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.

Additional Information

© 2004 Springer-Verlag Berlin Heidelberg. Discussions with Sergey Bravyi and Frank Verstraete are gratefully acknowledged. JK is 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, and by DARPA and Air Force Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-01-2-0524, and by DARPA and the Office of Naval Research under grant number 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. AK is supported in part by the National Science Foundation under grant EIA-0086038. OR is supported by an Alon Fellowship and the Army Research Office grant DAAD19-03-1-0082. Part of this work was carried out during a visit of OR at LRI, Université de Paris-Sud and he thanks his hosts for their hospitality and acknowledges partial support by ACI Sécurité Informatique, 2003-n24, projet "Réseaux Quantiques".

Attached Files

Submitted - 0406180.pdf

Files

0406180.pdf
Files (345.6 kB)
Name Size Download all
md5:be47874f6db003f5da36fcf136f5981b
345.6 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024