A Caltech Library Service

Undecidability of the Spectral Gap in One Dimension

Bausch, Johannes and Cubitt, Toby S. and Lucia, Angelo and Pérez-García, David (2020) Undecidability of the Spectral Gap in One Dimension. Physical Review X, 10 (3). Art. No. 031038. ISSN 2160-3308. doi:10.1103/physrevx.10.031038.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Bausch, Johannes0000-0003-3189-9162
Cubitt, Toby S.0000-0002-5087-9346
Lucia, Angelo0000-0003-1709-1220
Pérez-García, David0000-0003-2990-791X
Additional Information:© 2020 The Author(s). Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI. (Received 22 October 2019; revised 24 April 2020; accepted 27 May 2020; published 17 August 2020) J. B. acknowledges support from the German National Academic Foundation, the EPSRC (Grant No. 1600123), and the Draper’s Research Fellowship at Pembroke College. T. S. C. is supported by the Royal Society. A. L. acknowledges support from the European Research Council (Grant Agreement No. 337603) and VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059), the Walter Burke Institute for Theoretical Physics in the form of the Sherman Fairchild Fellowship, as well as support from the Institute for Quantum Information and Matter, a NSF Physics Frontiers Center (NFS Grant No. PHY-1733907). D. P. G. acknowledges financial support from Spanish MINECO (Grants No. MTM2014-54240-P and No. MTM2017-88385-P and Severo Ochoa Project No. SEV-2015-556), Comunidad de Madrid (QUITEMAD + CM Grant No. S2013/ICE-2801), and the European Research Council under the European Union’s Horizon 2020 research and innovation program (Grant Agreement No. 648913).
Group:Walter Burke Institute for Theoretical Physics, Institute for Quantum Information and Matter
Funding AgencyGrant Number
Studienstiftung des Deutschen VolkesUNSPECIFIED
Engineering and Physical Sciences Research Council (EPSRC)1600123
Pembroke College, University of CambridgeUNSPECIFIED
European Research Council (ERC)337603
Villum Fonden10059
Walter Burke Institute for Theoretical Physics, CaltechUNSPECIFIED
Sherman Fairchild FoundationUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Ministerio de Economía y Competitividad (MINECO)MTM2014-54240-P
Ministerio de Economía y Competitividad (MINECO)MTM2017-88385-P
Severo OchoaSEV-2015-556
Comunidad de MadridS2013/ICE-2801
European Research Council (ERC)648913
Issue or Number:3
Record Number:CaltechAUTHORS:20200818-151254755
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105009
Deposited By: George Porter
Deposited On:19 Aug 2020 14:02
Last Modified:16 Nov 2021 18:38

Repository Staff Only: item control page