2006/01/01 by Julia Kempe, Alexei Kitaev, Oded Regev · 3 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs #Polynomial and algebraic computation
paper · doi:10.1137/s0097539704445226
The k-\locHam problem is a natural complete problem for the complexity class \QMA, the quantum analogue of \NP. It is similar in spirit to \sc 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-\locHam is in \P and hence not believed to be \QMA-complete. The complexity of the 2-\locHam 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.