Two-dimensional local Hamiltonian problem with area laws is QMA-complete

Yichen Huang

We show that the 2D local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete. We also prove similar results in 2D translation- invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Consequently, unless MA = QMA, not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. In the future, even if area laws are proved for ground states of 2D gapped systems, the computational complexity of these systems remains unclear.

Sandy Irani, Jiaqing Jiang

S. Narayanaswami

Sean Hallgren, Daniel Nagaj, S. Narayanaswami

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.

Sean Hallgren, Daniel Nagaj, S. Narayanaswami

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.

Julia Kempe, Alexei Kitaev, Oded Regev