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 (13)

• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Realization of quantum signal processing on a noisy quantum computer
• Identity check is QMA-complete
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Robustness of QMA against witness noise
• A quantum primality test with order finding
• Measuring 4-local n-qubit observables could probabilistically solve PSPACE
• Non-Identity Check Remains QMA-Complete for Short Circuits
• 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
• QMA with subset state witnesses
• A Lattice Problem in Quantum NP
• Two QCMA-complete problems