Watson, JD;
Cubitt, TS;
(2022)
Computational complexity of the ground state energy density problem.
In: Leonardi, S and Gupta, A, (eds.)
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
(pp. pp. 764-775).
Association for Computing Machinery (ACM): New York, NY, USA.
Preview |
Text
GSED_STOC.pdf - Accepted Version Download (920kB) | Preview |
Abstract
We study the complexity of finding the ground state energy density of a local Hamiltonian on a lattice in the thermodynamic limit of infinite lattice size. We formulate this rigorously as a function problem, in which we request an estimate of the ground state energy density to some specified precision; and as an equivalent promise problem, GSED, in which we ask whether the ground state energy density is above or below specified thresholds. The ground state energy density problem is unusual, in that it concerns a single, fixed Hamiltonian in the thermodynamic limit, whose ground state energy density is just some fixed, real number. The only input to the computational problem is the precision to which to estimate this fixed real number, corresponding to the ground state energy density. Hardness of this problem for a complexity class therefore implies that the solutions to all problems in the class are encoded in this single number (analogous to Chaitin's constant in computability theory). This captures computationally the type of question most commonly encountered in condensed matter physics, which is typically concerned with the physical properties of a single Hamiltonian in the thermodynamic limit. We show that for classical, translationally invariant, nearest neighbour Hamiltonians on a 2D square lattice, PNEEXP†EXPGSED† EXPNEXP, and for quantum Hamiltonians PNEEXP†EXPGSED† EXPQMAEXP. With some technical caveats on the oracle definitions, the EXP in some of these results can be strengthened to PSPACE. We also give analogous complexity bounds for the function version of GSED.
| Type: | Proceedings paper |
|---|---|
| Title: | Computational complexity of the ground state energy density problem |
| Event: | 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) |
| ISBN-13: | 9781450392648 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3519935.3520052 |
| Publisher version: | http://doi.org/10.1145/3519935.3520052 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | complexity, Hamiltonian complexity, physics, energy, quantum, precision, condensed matter physics |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10152722 |
Archive Staff Only
 |
View Item |
