The Complexity of the Local Hamiltonian Problem

Details The Complexity of the Local Hamiltonian Problem The Complexity of the Local Hamiltonian Problem

2004-06-24

arxiv.org/abs/quant-ph/0406180v2

SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006), conference version in Proc. 24th FSTTCS, p. 372-383 (2004)

Physics

Quantum Physics

30 pages, 3 figures, replaced with revised version, numerous improvements to readability and expanded adiabatic section

Scientific paper

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 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 two-local interactions on qubits is equivalent to standard quantum computation.

Affiliated with

Also associated with

No associations

Rating

The Complexity of the Local Hamiltonian Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of the Local Hamiltonian Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of the Local Hamiltonian Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-102150