arXiv:1602.05924

On the uncomputability of the spectral gap

Seth Lloyd

Published Feb 18, 2016• 4 citations

Abstract

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

DOI: 10.48550/arxiv.1602.05924

Related papers

Comment on "On the uncomputability of the spectral gap"

Toby S. Cubitt, David Pérez-Garcı́a, Michael M. Wolf

The aim of this short note is to clarify some of the claims made in the comparison made in [S. Lloyd, On the uncomputability of the spectral gap, arXiv:1602.05924] between our recent result [T.S. Cubitt, D. Perez-Garcia, M.M. Wolf, Undecidability of the spectral gap, Nature 528, 207-211 (2015), arXiv:1502.04573] and his 1994 paper [S. Lloyd, Necessary and sufficient conditions for quantum computation, J. Mod. Opt. 41(12), 2503-2520 (1994)].

arXiv:1603.00825Mar 2, 20163 citations

A Note on the Complexity of the Spectral Gap Problem

Justin Yirka

arXiv:2503.02747Mar 4, 20250 citations

Spectral Gap Undecidability Proves Insulator-Conductor Distinction Uncomputable — E8 Intelligence Research

Andrew Stewart Caldin

Jul 20, 20260 citations

The bulk spectral gap is certifiable from above but uncomputable from below

Xiangling Xu, Matthias Schötz, Jie Wang +4 more

quant-pharXiv:2606.03836Jun 3, 20260 citations

Undecidability of the spectral gap

Johannes Bausch

What happens to undecidability in the quantum computing paradigm?

XRDS Crossroads The ACM Magazine for StudentsSep 20, 201649 citations

Spectral Gap Undecidability Reveals Fundamental Limits to Quantum Knowledge — E8 Intelligence Research

Andrew Stewart Caldin

Jul 20, 20260 citations

arXiv:1602.05924

On the uncomputability of the spectral gap

Seth Lloyd

Published Feb 18, 2016• 4 citations

arXiv HTML PDF

Abstract

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

DOI: 10.48550/arxiv.1602.05924

Related papers

Comment on "On the uncomputability of the spectral gap"

Toby S. Cubitt, David Pérez-Garcı́a, Michael M. Wolf

arXiv:1603.00825Mar 2, 20163 citations

A Note on the Complexity of the Spectral Gap Problem

Justin Yirka

The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$ : polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[log]}$ , a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is $P^{QMA[log]}$ -complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of $P^{QMA[log]}$ .The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[log]}$, a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is $P^{QMA[log]}$-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of $P^{QMA[log]}$.

arXiv:2503.02747Mar 4, 20250 citations

Spectral Gap Undecidability Proves Insulator-Conductor Distinction Uncomputable — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Spectral gap undecidability in quantum many-body systems proves that determining whether a material is an insulator or conductor is mathematically uncomputable in general. | MATH: The spectral gap is the difference between ground state energy $E_0$ and first excited state $E_1$ : $\Delta = E_1 - E_0$ . Undecidability arises via encoding Turing machine halting into Hamiltonian parameters (e.g., for 2D translation-invariant spin systems). Key result: There exists a family of Hamiltonians $H(\lambda)$ such that the set of $\lambda$ for which $\Delta > 0$ is non-recursive. | CONNECTION: No direct geometric ratios (0.382, 0.618, etc.) appear. However, the proof uses lattice structures (square/cubic) and translation invariance—crystallographic symmetry groups (e.g., wallpaper groups) are implicit. The undecidability relies on encoding into a periodic tiling, linking to Penrose tilings and aperiodic order. | DEPTH: 9 — This is a foundational result linking computation theor Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.comFINDING: Spectral gap undecidability in quantum many-body systems proves that determining whether a material is an insulator or conductor is mathematically uncomputable in general. | MATH: The spectral gap is the difference between ground state energy $E_0$ and first excited state $E_1$: $\Delta = E_1 - E_0$. Undecidability arises via encoding Turing machine halting into Hamiltonian parameters (e.g., for 2D translation-invariant spin systems). Key result: There exists a family of Hamiltonians $H(\lambda)$ such that the set of $\lambda$ for which $\Delta > 0$ is non-recursive. | CONNECTION: No direct geometric ratios (0.382, 0.618, etc.) appear. However, the proof uses lattice structures (square/cubic) and translation invariance—crystallographic symmetry groups (e.g., wallpaper groups) are implicit. The undecidability relies on encoding into a periodic tiling, linking to Penrose tilings and aperiodic order. | DEPTH: 9 — This is a foundational result linking computation theor Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

Jul 20, 20260 citations

The bulk spectral gap is certifiable from above but uncomputable from below

Xiangling Xu, Matthias Schötz, Jie Wang +4 more

Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. When a fixed boundary condition is imposed, this problem is undecidable: no algorithm, even with unlimited resources, can decide for every Hamiltonian whether it is gapped. Yet the thermodynamic limit is meant to capture the intrinsic properties of very large systems, which should not depend on how their boundaries are chosen. We therefore consider the bulk spectral gap, which concerns only the intrinsic excitations of the infinite system, and ask what can and cannot be computed about it. First, we give a general algorithm producing a hierarchy of certified upper bounds on the bulk gap, arbitrarily tight at the cost of more computation. Second, we prove that the spectral gap problem remains undecidable in the bulk, already for translationally invariant nearest-neighbour chains of fixed local dimension. Hence no general algorithm produces convergent lower bounds, and no convergent upper-bounding algorithm, ours included, admits a computable convergence rate. The bulk spectral gap is thus certifiable from above but uncomputable from below; more precisely, the bulk-gaplessness promise problem is RE-complete, exactly as hard as the halting problem. The same construction shows that no general algorithm can decide whether a given product state is a ground state, and that convergent bounds on ground-state expectation values admit no computable convergence rate in general. Finally, we obtain the first nontrivial certified upper bounds on the bulk gap of the spin-1/2 kagome Heisenberg antiferromagnet.Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. When a fixed boundary condition is imposed, this problem is undecidable: no algorithm, even with unlimited resources, can decide for every Hamiltonian whether it is gapped. Yet the thermodynamic limit is meant to capture the intrinsic properties of very large systems, which should not depend on how their boundaries are chosen. We therefore consider the bulk spectral gap, which concerns only the intrinsic excitations of the infinite system, and ask what can and cannot be computed about it. First, we give a general algorithm producing a hierarchy of certified upper bounds on the bulk gap, arbitrarily tight at the cost of more computation. Second, we prove that the spectral gap problem remains undecidable in the bulk, already for translationally invariant nearest-neighbour chains of fixed local dimension. Hence no general algorithm produces convergent lower bounds, and no convergent upper-bounding algorithm, ours included, admits a computable convergence rate. The bulk spectral gap is thus certifiable from above but uncomputable from below; more precisely, the bulk-gaplessness promise problem is RE-complete, exactly as hard as the halting problem. The same construction shows that no general algorithm can decide whether a given product state is a ground state, and that convergent bounds on ground-state expectation values admit no computable convergence rate in general. Finally, we obtain the first nontrivial certified upper bounds on the bulk gap of the spin-1/2 kagome Heisenberg antiferromagnet.

quant-pharXiv:2606.03836Jun 3, 20260 citations

Undecidability of the spectral gap

Johannes Bausch

What happens to undecidability in the quantum computing paradigm?

XRDS Crossroads The ACM Magazine for StudentsSep 20, 201649 citations

Spectral Gap Undecidability Reveals Fundamental Limits to Quantum Knowledge — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability of the spectral gap in quantum many-body systems proves that certain physical properties cannot be algorithmically determined, revealing fundamental limits to computation and knowledge. | MATH: The spectral gap problem is equivalent to the halting problem; no algorithm exists to decide if a Hamiltonian has a gap (Δ > 0) or is gapless (Δ = 0). Key constants: spectral gap Δ, Hamiltonian H, ground state energy E₀, first excited state energy E₁, Δ = E₁ - E₀. | CONNECTION: The spectral gap problem is linked to the geometry of the parameter space of Hamiltonians; the undecidability arises from the ability to encode Turing machines into the lattice structure of quantum spin systems, reflecting a deep symmetry between computation and physical law. The ratio Δ/||H|| is not computable in general. | DEPTH: 9 — This finding bridges computability theory, quantum mechanics, and geometry, showing that the mathematical structure of the universe includes inherently uncomputable Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.comFINDING: Undecidability of the spectral gap in quantum many-body systems proves that certain physical properties cannot be algorithmically determined, revealing fundamental limits to computation and knowledge. | MATH: The spectral gap problem is equivalent to the halting problem; no algorithm exists to decide if a Hamiltonian has a gap (Δ > 0) or is gapless (Δ = 0). Key constants: spectral gap Δ, Hamiltonian H, ground state energy E₀, first excited state energy E₁, Δ = E₁ - E₀. | CONNECTION: The spectral gap problem is linked to the geometry of the parameter space of Hamiltonians; the undecidability arises from the ability to encode Turing machines into the lattice structure of quantum spin systems, reflecting a deep symmetry between computation and physical law. The ratio Δ/||H|| is not computable in general. | DEPTH: 9 — This finding bridges computability theory, quantum mechanics, and geometry, showing that the mathematical structure of the universe includes inherently uncomputable Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

Jul 20, 20260 citations

The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class

P^{QMA[log]}

: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for

P^{UQMA[log]}

, a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is

P^{QMA[log]}

-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of

P^{QMA[log]}

E_0

and first excited state

E_1

\Delta = E_1 - E_0

. Undecidability arises via encoding Turing machine halting into Hamiltonian parameters (e.g., for 2D translation-invariant spin systems). Key result: There exists a family of Hamiltonians

H(\lambda)

such that the set of

\lambda

for which

\Delta > 0

is non-recursive. | CONNECTION: No direct geometric ratios (0.382, 0.618, etc.) appear. However, the proof uses lattice structures (square/cubic) and translation invariance—crystallographic symmetry groups (e.g., wallpaper groups) are implicit. The undecidability relies on encoding into a periodic tiling, linking to Penrose tilings and aperiodic order. | DEPTH: 9 — This is a foundational result linking computation theor Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com