Alexei Kitaev

2-local Hamiltonian is QMA-complete

I will present the results of my joint work with Julia Kempe and Oded Regev, quant-ph/0406180. The $k$-LOCAL HAMILTONIAN is a natural problem in the complexity class QMA, the quantum analogue of NP. It was known that the problem is QMA-complete for $k>2$. We show that it is also complete for $k=2$. We gave two different proofs, but in this talk I will focus on the one that uses third-order perturbation theory for a three-qubit gadget. This method is similar in spirit to the usual NP-reduction techniques.