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, Angelo Lucia, David Pérez-Garcı́a

Published Aug 17, 2020• 37 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

Undecidability of the Spectral Gap

J.B. Houben

We treat the results of the 2015 paper by Cubitt et al. entitled “Undecidability of the Spectral Gap”, and the constructions required to arrive at these results. This paper showed that a specific quantum mechanical problem (the “spectral gap problem”) is algorithmically undecidable, using techniques from computer science. We also treat the theory from quantum mechanics and computer science that is required to understand these results and constructions.

•Jan 1, 2016•0 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•49 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•4 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.