Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1810.01858 · Physical Review X

Undecidability of the Spectral Gap in One Dimension

Johannes Bausch, Toby S. Cubitt, Ángelo Lucia, David Pérez-García

Published Aug 17, 2020• 60 citations
arXivHTMLPDF

Abstract

A new analysis proves that it is not possible for numerical algorithms to determine if a 1D quantum system has a spectral gap, showing that basic properties of even simple systems are, in some instances, impossible to predict.
DOI
10.1103/physrevx.10.031038

Related papers

Instability of the undecidable behavior of the spectral gap in 1D

Laura Castilla-Castellano, Angelo Lucia

The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] or more dimensions [T. S. Cubitt et al., "Undecidability of the spectral gap", Nature 528 (2015) and Forum of Mathematics Pi, 10 (2022)]. In this work, we focus on the 1-dimensional result, showing that the constructed family with undecidable behavior is extremely sensitive to perturbations. In particular, for any $\varepsilon > 0$, there exists a 1-local, rank 1, perturbation with norm $O(\varepsilon)$, such that the spectral gap problem for the family in [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] now becomes decidable.

quant-pharXiv:2607.08686•Jul 10, 2026•0 citations

Why Some Physicists Are Excited About the Undecidability of the Spectral Gap Problem and Why Should We

Владик Крейнович

Since Turing's time, many problems have been proven undecidable. It is interesting though that, arguably, none of the working physicist problems had been ever proven undecidable -- until T. Cubitt, D. Perez-Garcia and M. M. Wolf proved recently that, for a physically reasonable class of systems, no algorithm can decide whether a given system has a spectral gap. We explain the spectral gap problem, its importance for physics and possible consequences of this exciting new result.

Bulletin of the European Association for Theoretical Computer Science•Jun 1, 2017•2 citations

Spectral gaps in quantum computing

David Pérez-García

How does the spectral gap of a quantum many-body system scale with the system size?This turns out to be a very relevant question both in condensed matter physics and in quantum computing.However, there are very few available techniques to give bounds on that scaling.In the first part of this paper, we will review recent results which explain why it is undecidable to know if the spectral gap will vanish or not with the system size.In the second part, we will review complementary results which show that, despite this general impossibility result, one can still prove spectral gap estimates in a rather wide family of systems.As a consequence, one obtains new bounds on the lifetime of quantum memories.

EMS Press eBooks•Oct 14, 2026•0 citations

Undecidability of the spectral gap

Johannes Bausch

What happens to undecidability in the quantum computing paradigm?

XRDS Crossroads The ACM Magazine for Students•Sep 20, 2016•51 citations

On the uncomputability of the spectral gap

Seth Lloyd

This paper reviews the 1994 proof that the spectral gap of Hamiltonian quantum systems capable of universal computation is uncomputable.

arXiv:1602.05924•Feb 18, 2016•7 citations

Undecidability of the Quantum Spectral Gap Limits Material Property Prediction — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability in quantum spectral gaps proves that the existence of a spectral gap in many-body systems is not algorithmically decidable, implying fundamental limits to predicting material properties. | MATH: The spectral gap problem reduces to the halting problem; no algorithm can determine if a Hamiltonian's ground state energy is separated from the excited states by a finite gap. Key constants: spectral gap Δ = E₁ - E₀, where Δ > 0 indicates an insulator, Δ = 0 a conductor. | CONNECTION: The undecidability result is tied to the structure of Projected Entangled Pair States (PEPS), which encode lattice symmetries and tensor network geometries. The spectral gap's undecidability mirrors the non-computability of certain geometric invariants in crystallographic root systems (e.g., Coxeter groups). | DEPTH: 9 — This is a profound link between computation theory and quantum many-body physics, showing that geometric order (e.g., lattice gaps) can be algorithmically inaccessible, ec Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 31, 2026•0 citations
The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] or more dimensions [T. S. Cubitt et al., "Undecidability of the spectral gap", Nature 528 (2015) and Forum of Mathematics Pi, 10 (2022)]. In this work, we focus on the 1-dimensional result, showing that the constructed family with undecidable behavior is extremely sensitive to perturbations. In particular, for any ε>0\varepsilon > 0ε>0, there exists a 1-local, rank 1, perturbation with norm O(ε)O(\varepsilon)O(ε), such that the spectral gap problem for the family in [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] now becomes decidable.
How does the spectral gap of a quantum many-body system scale with the system size?This turns out to be a very relevant question both in condensed matter physics and in quantum computing.However, there are very few available techniques to give bounds on that scaling.In the first part of this paper, we will review recent results which explain why it is undecidable to know if the spectral gap will vanish or not with the system size.In the second part, we will review complementary results which show that, despite this general impossibility result, one can still prove spectral gap estimates in a rather wide family of systems.As a consequence, one obtains new bounds on the lifetime of quantum memories.
FINDING: Undecidability in quantum spectral gaps proves that the existence of a spectral gap in many-body systems is not algorithmically decidable, implying fundamental limits to predicting material properties. | MATH: The spectral gap problem reduces to the halting problem; no algorithm can determine if a Hamiltonian's ground state energy is separated from the excited states by a finite gap. Key constants: spectral gap Δ = E₁ - E₀, where Δ > 0 indicates an insulator, Δ = 0 a conductor. | CONNECTION: The undecidability result is tied to the structure of Projected Entangled Pair States (PEPS), which encode lattice symmetries and tensor network geometries. The spectral gap's undecidability mirrors the non-computability of certain geometric invariants in crystallographic root systems (e.g., Coxeter groups). | DEPTH: 9 — This is a profound link between computation theory and quantum many-body physics, showing that geometric order (e.g., lattice gaps) can be algorithmically inaccessible, ec Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com