Journal
SIAM JOURNAL ON COMPUTING
Volume 35, Issue 5, Pages 1070-1097Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539704445226
Keywords
quantum computation; local Hamiltonian problem; complete problems; adiabatic computation
Ask authors/readers for more resources
The center dot-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-center dot-SAT, which is NP-complete for center dot >= 2. It was known that the problem is QMA-complete for any center dot >= 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available