UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Undecidability of the Spectral Gap in One Dimension

Bausch, J; Cubitt, TS; Lucia, A; Perez-Garcia, D; (2020) Undecidability of the Spectral Gap in One Dimension. Physical Review X , 10 (3) , Article 031038. 10.1103/PhysRevX.10.031038. Green open access

[thumbnail of PhysRevX.10.031038.pdf]
PhysRevX.10.031038.pdf - Published Version

Download (767kB) | Preview


The spectral gap problem—determining whether the energy spectrum of a system has an energy gap above ground state, or if there is a continuous range of low-energy excitations—pervades quantum many-body physics. Recently, this important problem was shown to be undecidable for quantum-spin systems in two (or more) spatial dimensions: There exists no algorithm that determines in general whether a system is gapped or gapless, a result which has many unexpected consequences for the physics of such systems. However, there are many indications that one-dimensional spin systems are simpler than their higher-dimensional counterparts: For example, they cannot have thermal phase transitions or topological order, and there exist highly effective numerical algorithms such as the density matrix renormalization group—and even provably polynomial-time ones—for gapped 1D systems, exploiting the fact that such systems obey an entropy area law. Furthermore, the spectral gap undecidability construction crucially relied on aperiodic tilings, which are not possible in 1D. So does the spectral gap problem become decidable in 1D? In this paper, we prove this is not the case by constructing a family of 1D spin chains with translationally invariant nearest-neighbor interactions for which no algorithm can determine the presence of a spectral gap. This not only proves that the spectral gap of 1D systems is just as intractable as in higher dimensions, but it also predicts the existence of qualitatively new types of complex physics in 1D spin chains. In particular, it implies there are 1D systems with a constant spectral gap and nondegenerate classical ground state for all systems sizes up to an uncomputably large size, whereupon they switch to a gapless behavior with dense spectrum.

Type: Article
Title: Undecidability of the Spectral Gap in One Dimension
Open access status: An open access version is available from UCL Discovery
DOI: 10.1103/PhysRevX.10.031038
Publisher version: https://doi.org/10.1103/PhysRevX.10.031038
Language: English
Additional information: © 2020 American Physical Society. Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license (https://creativecommons.org/licenses/by/4.0/).
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
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
URI: https://discovery.ucl.ac.uk/id/eprint/10109133
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item