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:2211.13532 · SciPost Physics

Many bounded versions of undecidable problems are NP-hard

Andreas Klingler, Mirte van der Eyden, Sebastian Stengele, Tobias Reinhart, Gemma De las Cuevas

Published Jun 29, 2023• 7 citations
arXivHTMLPDF

Abstract

Several physically inspired problems have been proven undecidable; examples are the spectral gap problem and the membership problem for quantum correlations. Most of these results rely on reductions from a handful of undecidable problems, such as the halting problem, the tiling problem, the Post correspondence problem or the matrix mortality problem. All these problems have a common property: they have an NP-hard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NP-hard versions. Specifically, we show that NP-hardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NP-hardness of bounded version of the Post correspondence problem, the matrix mortality problem, the positivity of matrix product operators, the reachability problem, the tiling problem, and the ground state energy problem. This work sheds light on the intractability of problems in theoretical physics and on the computational consequences of bounding a parameter.

DOI
10.21468/scipostphys.14.6.173

Related papers

Matrix-Product Operators and States: NP-Hardness and Undecidability

Martin Kliesch, D. Gross, Jens Eisert

Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.

arXiv:1404.4466•Physical Review Letters•Oct 16, 2014•80 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 via Halting Problem Reduction — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The halting problem is provably undecidable; reductions show many other problems inherit this undecidability, including the spectral gap problem via Penrose tiling encoding. MATH: - Halting problem: No Turing machine \( H \) exists such that \( H(P, I) \) decides if program \( P \) halts on input \( I \). - Reduction: If problem \( A \) can be encoded as a halting problem instance, then \( A \) is undecidable. - Cubitt et al. (2015): The spectral gap problem (determining if a quantum system has a gap between ground and first excited state) is undecidable. Encoding uses aperiodic tilings (Penrose-like) to simulate a Turing machine's tape and state. - Key constants/ratios: None directly from these findings; the undecidability proof relies on combinatorial tiling rules, not numeric constants. CONNECTION: - Penrose tilings exhibit 5-fold rotational symmetry (crystallographically forbidden in periodic lattices) and use golden ratio \(\phi = (1+\sqrt{5})/2 \approx 1.618\ Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 27, 2026•0 citations

Undecidability as Structural Physics: From Turing to Quantum Spectral Gaps — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability is not a computational artifact but a structural feature of formal systems — it propagates into physics (quantum many-body problems, spectral gaps) via reduction, revealing a hierarchy of unknowability. | MATH: Halting problem (Turing, 1936): no computable function H(p,i) decides if program p halts on input i. Gödel's incompleteness: for any consistent formal system F containing arithmetic, ∃ statement G_F such that F⊬G_F and F⊬¬G_F. Reduction: Problem A ≤_T Problem B means an oracle for B solves A; undecidability transfers A ≤ B ⇒ B undecidable. Quantum analog: spectral gap problem (Cubitt, Perez-Garcia, Wolf, 2015) — determining if a 2D spin-lattice Hamiltonian has a gap above ground state is undecidable (reduction from halting problem to Hamiltonian construction). | CONNECTION: The reduction lattice forms a partial order with a maximal undecidable class (Σ₁⁰-complete) — structurally analogous to root system hierarchies (e.g., E₈ has 240 roots; the undecidabil Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 21, 2026•0 citations

Undecidability as a Structural Invariant from Computability to Quantum Physics — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability is not a peripheral paradox but a structural invariant of formal systems, extending from classical computability (halting problem) into quantum many-body physics, where spectral gaps and ground-state properties become provably non-computable. | MATH: Halting problem: no Turing machine H exists s.t. H(P,I) halts iff P(I) halts — diagonalization proof yields contradiction via self-reference. Gödel: for any consistent, recursively axiomatizable system S containing arithmetic, ∃ sentence G with S⊬G and S⊬¬G. Quantum extension: the spectral gap problem (given a translation-invariant local Hamiltonian on a lattice, does the gap between ground and first excited state vanish in the thermodynamic limit?) is undecidable — reduction from the halting problem to 2D spin-lattice Hamiltonians (Cubitt, Perez-Garcia, Wolf, 2015). | CONNECTION: The undecidability proofs rely on encoding computation into lattice structures — the 2D square lattice (crystallographic symmetry p4m) se Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 6, 2026•0 citations

Undecidability as Structural Physics: From Halting to Spectral Gaps — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability is not a computational artifact but a structural feature of formal systems, now extending into quantum many-body physics — where the halting problem maps onto spectral gap questions. | MATH: Halting problem (Turing, 1936): no computable function H(P,I) decides if program P halts on input I. Gödel incompleteness: for any consistent, recursively axiomatizable theory T ⊇ Robinson arithmetic, ∃ sentence G with T⊬G and T⊬¬G. Reducibility: A ≤_T B via Turing reduction — solving B solves A. Quantum extension: the spectral gap problem (given a translationally invariant local Hamiltonian, does the gap vanish in the thermodynamic limit?) is undecidable (Cubitt, Perez-Garcia, Wolf, 2015) — proof uses a lattice of spins encoding a Turing machine's halting behavior into the gap's existence. | CONNECTION: The undecidability proofs rely on encoding computation into discrete lattices — the quantum result uses a 2D spin lattice with local interactions, echoing crystallographic l Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 22, 2026•0 citations
Several physically inspired problems have been proven undecidable; examples are the spectral gap problem and the membership problem for quantum correlations. Most of these results rely on reductions from a handful of undecidable problems, such as the halting problem, the tiling problem, the Post correspondence problem or the matrix mortality problem. All these problems have a common property: they have an NP-hard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NP-hard versions. Specifically, we show that NP-hardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NP-hardness of bounded version of the Post correspondence problem, the matrix mortality problem, the positivity of matrix product operators, the reachability problem, the tiling problem, and the ground state energy problem. This work sheds light on the intractability of problems in theoretical physics and on the computational consequences of bounding a parameter.
Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.
FINDING: The halting problem is provably undecidable; reductions show many other problems inherit this undecidability, including the spectral gap problem via Penrose tiling encoding. MATH: - Halting problem: No Turing machine H H H exists such that H(P,I) H(P, I) H(P,I) decides if program P P P halts on input I I I. - Reduction: If problem A A A can be encoded as a halting problem instance, then A A A is undecidable. - Cubitt et al. (2015): The spectral gap problem (determining if a quantum system has a gap between ground and first excited state) is undecidable. Encoding uses aperiodic tilings (Penrose-like) to simulate a Turing machine's tape and state. - Key constants/ratios: None directly from these findings; the undecidability proof relies on combinatorial tiling rules, not numeric constants. CONNECTION: - Penrose tilings exhibit 5-fold rotational symmetry (crystallographically forbidden in periodic lattices) and use golden ratio \(\phi = (1+\sqrt{5})/2 \approx 1.618\ Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: Undecidability is not a computational artifact but a structural feature of formal systems — it propagates into physics (quantum many-body problems, spectral gaps) via reduction, revealing a hierarchy of unknowability. | MATH: Halting problem (Turing, 1936): no computable function H(p,i) decides if program p halts on input i. Gödel's incompleteness: for any consistent formal system F containing arithmetic, ∃ statement G_F such that F⊬G_F and F⊬¬G_F. Reduction: Problem A ≤_T Problem B means an oracle for B solves A; undecidability transfers A ≤ B ⇒ B undecidable. Quantum analog: spectral gap problem (Cubitt, Perez-Garcia, Wolf, 2015) — determining if a 2D spin-lattice Hamiltonian has a gap above ground state is undecidable (reduction from halting problem to Hamiltonian construction). | CONNECTION: The reduction lattice forms a partial order with a maximal undecidable class (Σ₁⁰-complete) — structurally analogous to root system hierarchies (e.g., E₈ has 240 roots; the undecidabil Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: Undecidability is not a peripheral paradox but a structural invariant of formal systems, extending from classical computability (halting problem) into quantum many-body physics, where spectral gaps and ground-state properties become provably non-computable. | MATH: Halting problem: no Turing machine H exists s.t. H(P,I) halts iff P(I) halts — diagonalization proof yields contradiction via self-reference. Gödel: for any consistent, recursively axiomatizable system S containing arithmetic, ∃ sentence G with S⊬G and S⊬¬G. Quantum extension: the spectral gap problem (given a translation-invariant local Hamiltonian on a lattice, does the gap between ground and first excited state vanish in the thermodynamic limit?) is undecidable — reduction from the halting problem to 2D spin-lattice Hamiltonians (Cubitt, Perez-Garcia, Wolf, 2015). | CONNECTION: The undecidability proofs rely on encoding computation into lattice structures — the 2D square lattice (crystallographic symmetry p4m) se Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: Undecidability is not a computational artifact but a structural feature of formal systems, now extending into quantum many-body physics — where the halting problem maps onto spectral gap questions. | MATH: Halting problem (Turing, 1936): no computable function H(P,I) decides if program P halts on input I. Gödel incompleteness: for any consistent, recursively axiomatizable theory T ⊇ Robinson arithmetic, ∃ sentence G with T⊬G and T⊬¬G. Reducibility: A ≤_T B via Turing reduction — solving B solves A. Quantum extension: the spectral gap problem (given a translationally invariant local Hamiltonian, does the gap vanish in the thermodynamic limit?) is undecidable (Cubitt, Perez-Garcia, Wolf, 2015) — proof uses a lattice of spins encoding a Turing machine's halting behavior into the gap's existence. | CONNECTION: The undecidability proofs rely on encoding computation into discrete lattices — the quantum result uses a 2D spin lattice with local interactions, echoing crystallographic l Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com