3-Local Hamiltonian is QMA-complete

Abstract

It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.

7 pages, minor changes and corrections, published version

References in corpus (2)

• Quantum NP - A Survey
• The 2-local Hamiltonian problem encompasses NP

Cited by in corpus (5)

• Measuring 4-local n-qubit observables could probabilistically solve PSPACE
• Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
• Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard
• A Lattice Problem in Quantum NP
• Two QCMA-complete problems