Computational complexity of the ground state energy density problem

DOI10.1145/3519935.3520052arXiv2107.05060OpenAlexW3182797208WikidataQ130922060 ScholiaQ130922060MaRDI QIDQ6083532FDOQ6083532

Authors: Toby Cubitt

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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,

m a t h s f G S E D

, 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,

m a t h s f P^{m a t h s f N E E X P} s u b s e t e q m a t h s f {E X P}^{m a t h s f G S E D} s u b s e t e q m a t h s f {E X P}^{m a t h s f N E X P}

, and for quantum Hamiltonians

m a t h s f P^{m a t h s f N E E X P} s u b s e t e q m a t h s f {E X P}^{m a t h s f G S E D} s u b s e t e q m a t h s f {E X P}^{m a t h s f {Q M A}_{E X P}}

. With some technical caveats on the oracle definitions, the

m a t h s f E X P

in some of these results can be strengthened to

m a t h s f P S P A C E

. We also give analogous complexity bounds for the function version of

m a t h s f G S E D

.

Full work available at URL: https://arxiv.org/abs/2107.05060

zbMATH Keywords

energy complexity quantum condensed matter physics physics precision Hamiltonian complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (2)

This page was built for publication: Computational complexity of the ground state energy density problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083532)