The Local Hamiltonian problem on a line with eight states is QMA-complete

Abstract

The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

an older paper that didn't appear on the arXiv before (28 pages)

References in corpus (2)

• The power of quantum systems on a line
• Quantum NP - A Survey

Cited by in corpus (5)

• Quantum Hamiltonian Complexity
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Local tests of global entanglement and a counterexample to the generalized area law
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• The 7 faces of quantum NP