Classical efficiency of 2D gapped ground-state energy estimation
In plain words
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 statement
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.
What would settle it
A polynomial-time algorithm with proof, or a hardness result for the gapped 2D promise problem.
Results
No results have been posted on this problem yet.
Post a result · how results are checked
Sign in to follow or save this problem
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.