The Complexity of the Local Hamiltonian Problem
The Complexity of the Local Hamiltonian Problem
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\geq 2$. It was known that the problem is $\QMA$-complete for any $k \geq 3$. On the other hand, 1-{\locHam} …