THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP

作者：Paweł Wocjan, Thomas Beth · 发表于：International Journal of Quantum Information · 年份：2003 · DOI：10.1142/s021974990300022x · 被引用次数：9 · 研究领域：Complexity and Algorithms in Graphs、Quantum Computing Algorithms and Architecture、semigroups and automata theory

We show that the NP-complete problems max cut and independent set can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. The 5-local Hamiltonian problem was the first problem to be shown to be complete for the quantum complexity class QMA — the quantum analog of NP. Subsequently, it was shown that 3-locality is already sufficient for QMA-completeness. It is still not known whether the 2-local Hamiltonian problem is QMA-complete. Therefore it is interesting to determine what problems can be reduced to the 2-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulated as a 3-local Hamiltonian problem. We extend his result by showing that 2-locality is sufficient in order to encompass NP.