Revision 1

Accepted · first revision · record

Title: Classical efficiency of 2D gapped ground-state energy estimation
Plain: For one-dimensional systems with an energy gap, a classical computer can provably find the ground energy quickly. Whether the same holds for two-dimensional gapped systems is unknown.
Precise: Is there a classical algorithm that, for every $2\mathrm{D}$ nearest-neighbour Hamiltonian on $n$ qudits with spectral gap $\Delta = \Omega(1)$, outputs the ground energy to additive error $1/\operatorname{poly}(n)$ in time $\operatorname{poly}(n)$? The $1\mathrm{D}$ case is in $\mathrm{P}$ (Landau, Vazirani and Vidick 2015); without the gap promise the $2\mathrm{D}$ problem is QMA-complete.
Settled by: A polynomial-time algorithm with proof, or a hardness result for the gapped 2D promise problem.
Kind: well-posed
Answer type: yes-no
References: (empty)
Literature status: open
Status note: (empty)
Posed since: 2015