⚛️ quantum physics

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

This paper demonstrates that the previously established undecidability of the spectral gap in one-dimensional quantum spin systems is unstable, as arbitrarily small local perturbations can render the problem decidable.

Original authors: Laura Castilla-Castellano, Angelo Lucia

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Laura Castilla-Castellano, Angelo Lucia

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, infinite Lego chain. In the world of quantum physics, this chain is made of tiny particles, and the way they snap together is governed by a set of rules called a "Hamiltonian." Physicists love to ask one big question about these chains: Is there a "spectral gap"?

Think of a spectral gap like a safety buffer or a moat. If the chain has a gap, it's like a sturdy fortress with a wide, dry moat; the ground state (the lowest energy, most relaxed position) is separated from all the excited, wiggly states by a clear, unbridgeable distance. If the chain is "gapless," the moat is gone, and the excited states are just a slippery slope right next to the ground state. Knowing which one you have tells you everything about how the material behaves, from how it conducts electricity to how it holds together.

For a long time, scientists thought that for a 1D chain (a single line of particles), figuring out if there was a gap was easy. But then, a team of researchers proved something shocking: for certain very specific, complex chains, the question of "Is there a gap?" is undecidable.

The Impossible Puzzle

To understand "undecidable," imagine a computer program that runs a game. Sometimes the game ends (the computer "halts"), and sometimes it runs forever. In 1936, Alan Turing proved that there is no general algorithm that can look at any program and tell you if it will stop or run forever. This is the "Halting Problem."

The previous research (referenced as [1] in the paper) built a quantum Lego chain where the question "Is there a spectral gap?" was secretly the same as asking "Will this specific computer program stop?"

If the program stops, the chain is gapless (no moat).
If the program runs forever, the chain is gapped (there is a moat).

Since we can't solve the Halting Problem with a general algorithm, we can't solve the spectral gap problem for these chains either. It's a mathematical dead end.

The "Fragile" Secret

Now, enter the authors of this new paper, Laura Castilla-Castellano and Angelo Lucia. They looked at that specific, undecidable Lego chain and asked a very physical question: "How sturdy is this construction?"

In the real world, nothing is perfect. There is always noise, manufacturing errors, or tiny vibrations. If a theoretical model collapses because of the tiniest speck of dust, is it really a good description of reality?

The authors discovered that the undecidable chain is extremely fragile. It's like a house of cards built on a tightrope.

Here is the magic trick they found: The original chain relied on a very delicate balance. It used a special "marker" particle (let's call it a "Stop Sign" or $|\blacksquare\rangle$ ) to divide the chain into segments. The energy of the chain depended on a perfect cancellation: a bonus of $-1/2$ energy for the inside of a segment was exactly canceled out by a penalty of $+1/2$ for the Stop Sign. This perfect balance allowed the chain to "amplify" the tiny energy differences of the computer program, making the undecidable behavior possible.

The authors showed that if you add a tiny, almost invisible perturbation—a single extra rule that gives the Stop Sign a tiny extra cost of $\varepsilon$ (where $\varepsilon$ can be any number greater than 0, no matter how small)—the whole trick falls apart.

The "Decidable" Rescue

By adding this tiny cost of $\varepsilon$ to the Stop Sign, the perfect cancellation is broken. The energy balance shifts. Suddenly, the chain stops acting like a secret code for the Halting Problem.

Instead of being undecidable, the spectral gap problem becomes decidable. This means there is an algorithm that can solve it.

How? The authors proved that with this tiny perturbation, you only need to check the chain's behavior up to a certain size, which they call $w_\varepsilon$ . This size depends only on your tiny perturbation $\varepsilon$ and some constants, but it does not depend on the infinite complexity of the computer program.

If you check the chain up to size $w_\varepsilon$ and the energy is always positive, you know for sure the infinite chain is gapped.
If you find a negative energy at any point up to $w_\varepsilon$ , you know the infinite chain is gapless.

Because $w_\varepsilon$ is a finite number, you can write a computer program to check it. The "undecidable" mystery vanishes, replaced by a simple, finite checklist.

What This Means (and What It Doesn't)

The paper explicitly rules out the idea that these undecidable results are robust. The authors of the original study had suggested that small changes to the "classical" parts of the chain wouldn't matter. This new paper says: "Actually, they matter a huge amount, even if the change is tiny."

However, the authors are careful to note that this fragility is specific to the 1D construction they analyzed. They do not claim that all undecidable quantum systems are this fragile. In fact, they suggest that the 2D version (which uses a different, more rigid structure called "Robinson tiling") might be much harder to break. They also don't claim to have solved the spectral gap problem for all quantum systems, only for this specific family once it's been perturbed.

The Takeaway

The paper proves that the "undecidable" spectral gap in 1D quantum chains is not a fundamental law of nature, but rather a result of extreme fine-tuning. It's like a magic trick that only works if the magician holds their breath perfectly. If you introduce even the tiniest bit of "noise" (a perturbation of norm $O(\varepsilon)$ ), the trick fails, and the answer becomes computable.

So, while the universe might still hold some mysteries, this specific "impossible" puzzle turns out to be incredibly sensitive to the real-world imperfections we all live with. If you tweak the rules just a little bit, the impossible becomes possible to solve.

Technical Summary: Instability of the Undecidable Behavior of the Spectral Gap in 1D

Problem Statement
The spectral gap—the energy difference between the ground state and the first excited state—is a fundamental property governing quantum phase transitions, correlation decay, and the efficiency of simulation algorithms. While the spectral gap problem was proven to be undecidable for quantum spin systems in two or more dimensions [2, 3], a follow-up result demonstrated that this undecidability persists even in one-dimensional (1D) systems [1]. The construction in [1] relies on encoding the Halting problem of a Universal Turing Machine (UTM) into the ground state of a local Hamiltonian.

A critical physical question remains regarding the robustness of these undecidability results: Are the constructed Hamiltonians stable against small perturbations of the local interaction terms? Stability is a foundational concept in physics, as theoretical predictions must hold under the inevitable imperfections of real-world settings (noise, manufacturing tolerances, etc.). The authors of [1] noted that while perturbations to the computational encoding (Feynman-Kitaev terms) are known to be non-robust, they argued that small perturbations to the classical diagonal coupling terms might leave the construction intact, as these only shift penalty and bonus terms by a proportionally small amount.

Methodology
This work analyzes the specific 1D construction from [1] to test its stability against a specific class of perturbations. The methodology involves:

Reviewing the Undecidable Construction: The original Hamiltonian $H_N(\eta)$ is composed of three main parts:
- A Computational Hamiltonian ( $H_{TM}$ ) that encodes the UTM evolution.
- A Marker Hamiltonian ( $H_f$ ) that partitions the chain into segments separated by a boundary state $|\blacksquare\rangle$ . This mechanism amplifies the energy difference between halting and non-halting instances by creating multiple copies of optimal-length segments.
- Penalty Terms ( $P'''$ ) that ensure correct input encoding and penalize non-halting behaviors.
  The undecidability arises because the energy of the system depends on whether the UTM halts: if it halts, the ground state energy can become negative (gapless); if it does not, the energy remains positive (gapped).
Introducing the Perturbation: The authors introduce a 1-local, rank-1, classical (diagonal) perturbation $p^{(1)}_\epsilon = \epsilon |\blacksquare\rangle\langle\blacksquare|$ with norm $O(\epsilon)$ , where $\epsilon > 0$ is arbitrarily small. This term is added to the local interaction $h^{(1)}$ .
Energy Analysis of the Perturbed System: The perturbation modifies the "Marker Hamiltonian" by altering the fine-tuned energy cancellation between the boundary penalty and the segment bonus. Specifically, the original construction relies on a precise cancellation of a $-1/2$ energy contribution from the segment interior with a $+1/2$ penalty from the boundary. The perturbation shifts this boundary penalty to $1/2 + \epsilon$ .
Deriving Decidability: The authors analyze the ground state energy of the perturbed Hamiltonian $H^\epsilon_N$ . They demonstrate that the perturbation introduces a critical size $w_\epsilon$ , which depends only on $\epsilon$ and system constants (independent of the input $\eta$ or the specific Turing Machine).
- For segment sizes $w \geq w_\epsilon$ , the perturbation term $\mu\epsilon$ dominates the exponentially decaying bonus term $\delta(w)$ , rendering the energy contribution positive regardless of whether the machine halts.
- Consequently, the distinction between halting and non-halting instances is lost for large system sizes. The spectral gap behavior is now determined entirely by the behavior of the system for sizes $N \leq w_\epsilon$ .

Key Contributions and Results
The paper establishes the following main result (Theorem 6):

Fragility of Undecidability: The family of 1D Hamiltonians with undecidable spectral gap behavior constructed in [1] is extremely fragile. For any $\epsilon > 0$ , adding the 1-local perturbation $p^{(1)}_\epsilon$ renders the spectral gap problem decidable.
Finite Computation: The spectral gap of the perturbed family $\{H^\epsilon_N(\eta)\}$ ${H_{N}^{ϵ} (η)}$ can be determined by a finite computation. Specifically, one only needs to check the ground state energy $\lambda^N_{\min}$ $λ_{m i n}^{N}$ for system sizes $N$ $N$ in the finite range $[1, \dots, w_\epsilon]$ $[1, \dots, w_{ϵ}]$ .
- If $\lambda^N_{\min} \geq 1$ for all $N \in [1, \dots, w_\epsilon]$ , the family is gapped.
- If $\lambda^N_{\min} < 0$ for some $N \in [1, \dots, w_\epsilon]$ , the family is gapless.
Mechanism of Breakdown: The perturbation disrupts the "energy amplification" step. In the original construction, the amplification relies on the delicate balance where the energy bonus from forming multiple segments outweighs the computational penalties. The perturbation breaks this balance by introducing a linear energy cost per segment ( $\epsilon$ ) that eventually overwhelms the exponentially small bonuses required for the undecidable behavior to manifest at large scales.

Significance and Claims
The paper claims that this result sharpens the discussion on the stability of undecidable behavior in quantum systems. While previous work suggested that classical diagonal perturbations might be safe, this work demonstrates that even a simple, classical, diagonal, 1-local perturbation can drastically alter the low-energy spectrum if it targets a specific fine-tuned energy scale (in this case, the boundary penalty).

The authors emphasize that:

The undecidable behavior is not robust against this class of perturbations; it simplifies to a decidable problem.
This finding is consistent with existing rigorous stability theorems (e.g., those requiring Local Topological Quantum Order or frustration-freeness), as the construction in [1] lacks these properties.
The result highlights that the physical robustness of undecidability depends heavily on the specific nature of the perturbation and the structural assumptions of the model.
The paper does not claim that all undecidable constructions are unstable, nor does it resolve the stability question for the 2D case (where amplification relies on the rigid Robinson tiling structure rather than a single boundary term).

In summary, the work provides a counter-example to the notion that undecidable spectral gap behavior is inherently stable, showing that in 1D, the specific mechanisms enabling undecidability can be destroyed by arbitrarily small, physically plausible perturbations.