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

arXiv:2606.03836 · quant-ph, cond-mat.stat-mech, math-ph, math.MP · Submitted 2026-06-02 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "The bulk spectral gap is certifiable from above but uncomputable from below".

Mira: Determining spectral gaps in quantum many-body physics is a central challenge, as existing rigorous methods are largely limited to special settings,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, Mira, we're diving into this paper today which is called "The bulk spectral gap is certifiable from above but uncomputable from below." It sounds like they’ve cracked a way to get rigorous upper bounds on the spectral gap in quantum many-body physics.

Mira: Exactly, Kai; it tackles a really big problem because most methods we use right now only give us estimates, not certified guarantees about whether a system has a gap. This paper suggests that for the bulk spectral gap, we can get a family of certified upper bounds that become tighter as we use more computational power.

Lev: From my side, I'm thinking about what this means for actual implementation; if these bounds are derived from semidefinite programs, how feasible is it to actually run these computations on real quantum hardware?

Kai: That’s the million-dollar question, Lev. The authors build their method on SDPs—semidefinite programs—which are powerful tools in quantum information theory and many-body physics because they provide certified results in those areas

NPA08; PNA10: .

Mira: But the paper points out a critical hurdle: standard SDP constraints are linear in the state, whereas many important properties like spectral gaps are naturally described by nonlinear constraints, which is why they couldn't use standard SDP methods directly for this problem

Ara+twenty-six; Ara25; FFS24; Mor+twenty-five; Wan+twenty-six; Wan+twenty-four: .

Lev: So they had to develop a new translation method to turn the nonlinear formulation of the spectral gap into these certified SDP relaxations, which is a big technical leap. How does that translate to actual error correction protocols on hardware?

Kai: Well, the paper shows this translation yields a complete characterization of the bulk spectral gap problem in the thermodynamic limit, which is what they're aiming for. They use an operator algebra approach where local observables are elements of an approximately finite-dimensional C*algebra A, and they define dynamical systems based on local Hamiltonian families F = "HΛ(L)" where L controls the size of the finite region.

Mira: The paper then introduces a specific dynamical criterion to define a locally non-degenerate bulk gap on states, which essentially means finding a constant gamma greater than zero such that the bulk Hamiltonian Hω: one. is locally non-degenerate in the sense that ker(Hω) = Span omegaω⟩; and two. satisfies the bulk spectral gap condition Spec (Hω) ∩ (zero γ) = ∅.

Lev: That criterion involves a specific mathematical inequality, -iω(a∗δF (a)) at least gamma(omega(a∗a) − ω(a)two), which sounds like it’s testing stability against certain local perturbations. Does this level of rigor make it viable for practical error-correction schemes?

Title and authors: Kai: It makes the theoretical underpinning very strong, Lev, because they’ve shown that the resulting algorithm, implemented through SDPs indexed by (L, d), is not just a sequence of necessary tests but a complete certification procedure. Feasibility at every level is equivalent to the existence of such a KMS ground state with a locally non-degenerate bulk spectral gap of at least gamma.

Mira: The paper gives us concrete results, like applying this to the spin-one/two kagome lattice Heisenberg antiferromagnet where they got a fully general certified upper bound 2 point 18J, and then a sharper one at 1 point 15J in a physically motivated symmetry sector. These bounds are significant because they are far above existing numerical estimates, which were only around order ten-two to ten-1J or possibly gapless scenarios

DMS12; He+seventeen; YHW11: .

Lev: A bound of 2 point 18J is substantial, but I wonder if running these SDPs for the required size L and degree d would be computationally prohibitive for current quantum computers, especially when we need to iterate this many times to tighten the bound.

Kai: That’s where the computational cost comes in; they admit that these bounds become arbitrarily tight at the cost of more computational resources. They also showed that for 2D lattice models like the kagome lattice, these bounds provide rigorous information: if a bound lies below the energy of a proposed excitation, then that excitation is rigorously excluded from being the lowest bulk excitation.

Mira: This exclusion criterion is powerful because it gives us a way to rigorously rule out potential excitations based on these certified upper bounds. It’s a formal way to say something isn't the lowest excitation without having to find the exact state.

Lev: That formal exclusion capability would be extremely useful when designing error correction codes, as it tells us precisely which modes we can safely ignore or treat with more complexity. But what about those alternative notions of spectral gaps based on finite systems with prescribed boundary conditions that they mentioned?

Kai: The paper addresses those undecidability results for alternative notions of spectral gaps by showing their method, formulated directly in the bulk, is compatible because it addresses a different notion of spectral gaps. They conclude that the bulk spectral gap problem itself is undecidable, or whether it admits a complementary certification method for lower bounds.

Mira: So the paper establishes a clear boundary between what we can rigorously bound from above and what remains uncomputable from below, which is a very important distinction in many physical problems. It sets expectations for the limits of current mathematical tools.

Lev: For my work on quantum error correction, this means we can trust these upper bounds to verify that our error-correcting code structure has a gap large enough to be stable against those specific local excitations we're worried about. It provides a rigorous benchmark for hardware design.

Title and authors: Kai: And the results on the kagome lattice, specifically that 2 point 18J is the fully general bound and 1 point 15J is the sharper one in a symmetry sector, are really tangible numbers we can use to guide our experimental choices.

Mira: Indeed, those specific values give us concrete targets for what we expect to see in real materials or simulated systems when we look for these bulk properties. This paper provides a rigorous foundation that numerical estimates alone cannot offer.

Lev: If we can't compute the lower bounds, then our focus shifts entirely to using these rigorous upper bounds to design systems that are demonstrably stable up to a certain energy scale. It’s a shift in how we approach stability problems.

Kai: So, to wrap up on "The bulk spectral gap is certifiable from above but uncomputable from below," this work gives us the first rigorous certification of upper bounds using SDPs, showing how these tools can handle nonlinear constraints.

Mira: It really shows that for problems like the bulk spectral gap, we can have a complete family of certified upper bounds that get arbitrarily tight with more computation.

Lev: The implication for hardware is that we can use these bounds to verify stability against proposed excitations, which is a step toward designing truly robust quantum systems.

Kai: It’s a lot of work, but it gives us a rigorous yardstick for stability in the thermodynamic limit.

Mira: We have to remember that this method is limited by the computational resources required to reach those tighter bounds, which is a practical constraint we can’t ignore.

Lev: I think the main point for us is that we now have a formal way to state what stability looks like in terms of these certified bounds, which is something I can actually work with.

Kai: So, "The bulk spectral gap is certifiable from above but uncomputable from below" gives us a powerful new tool for rigorously bounding stability in many-body systems.

Mira: It's a paper that defines the limits of what we can prove about spectral properties and shows how SDPs can provide certification where other methods fall short.

Lev: We have to keep an eye on how this framework matures, because if we can integrate these certified upper bounds into our actual quantum simulation platforms, it could really help us move beyond just guessing stability in complex models.

Kai: That’s what we'll be watching next as we look at how this framework applies to other challenging physical systems.

The paper's summary: Kai: So, to recap, this paper is about showing that while we can rigorously prove an upper limit on the bulk spectral gap using semidefinite programs, we can't actually prove a lower limit from below in a complete way.

Mira: Exactly; they’ve established that for many-body systems, especially in the thermodynamic limit, we have a complete family of certified upper bounds derived from these SDPs, but those bounds get tighter and tighter as you use more computing power.

Lev: That means for error correction researchers like myself, it gives us a way to set a hard ceiling on the stability of our quantum models; if the certified gap is positive, we have a formal guarantee that those local perturbations won't cause an immediate collapse.

Kai: That’s right; it moves us from just having numerical guesses about stability to actually proving that something *cannot* happen below a certain energy threshold. It’s like getting a certified safety limit on how much stress a system can take before it breaks.

Mira: From my perspective, this is crucial because it separates what we can definitively prove from what remains computationally elusive; they show that the bulk spectral gap problem itself isn't fully computable in the way we might hope.

Lev: I see why that’s important; if we can't get a certified lower bound, then trying to prove a specific system is gapless becomes an impossible task because there’s no formal certificate to rule it out definitively.

Kai: It really sets the stage for how we need to think about stability in these complex many-body models; instead of just hoping our simulation is accurate, we can now use these SDP bounds as a formal tool to verify its robustness.

Mira: And those concrete results they got on the kagome lattice, like the two point 18J bound and the sharper one point 15J in symmetry sectors, show that this isn't just some abstract math; it’s giving us real numbers to compare against existing numerical estimates.

Lev: Those numbers are exactly what we need when designing hardware; knowing the actual energy scale of stability we can expect from a specific material or model is much better than having a vague estimate.

Kai: So, this work gives us a formal yardstick for stability in the thermodynamic limit using SDPs, and that’s something I can actually use to guide what we build and how we test it.

Mira: And the limitation they point out is that these bounds demand more computational resources to get tighter, which means we have to balance the desire for absolute certainty against practical limits on what current hardware can handle.

Lev: I agree; it’s a trade-off between rigor and feasibility, but at least now we know exactly what kind of computational cost we are incurring to get that level of certification.

Kai: That's the core tension here—getting the most rigorous proof possible versus what's actually practical for experimentalists and engineers in the quantum world.

Mira: So, this paper really clarifies where our current theoretical tools stop providing definitive answers and where we need to rely on these certified upper bounds instead.

Lev: It means our focus shifts to using these rigorous upper bounds to verify that our error-correcting code structure has a gap large enough to be stable against those specific local excitations we're worried about.

Kai: That’s the practical application we’ve been hoping for—a formal way to state what stability looks like in terms of these certified bounds, which is something I can actually work with.

The paper's improvements: Kai: So, to summarize the improvements discussed in this paper, they aren't just stopping at showing the upper bounds; they suggest a way to use them more practically for analyzing complex models.

Mira: Right, they propose using this hierarchy of SDPs not just as a single test but as a systematic way to check stability across different levels of computational complexity indexed by parameters like the system size and relaxation degree.

Lev: That systematic approach is what I’m interested in; if we can track how these certified bounds converge, it gives us a rigorous way to quantify exactly how much computational effort we need to put in before our estimate becomes reliable enough for practical error correction protocols.

Kai: So, instead of just getting one number for the gap, the framework lets us map out a whole path showing when our current approximation is good enough versus when we absolutely need more resources.

Mira: That’s interesting because it means we get a measure of the cost of certainty; we can see exactly where the computational wall starts to hit if we want higher confidence in the stability of a system.

Lev: For my work, that’s useful because it helps us determine whether investing more resources into an SDP calculation is actually going to yield a meaningful increase in our understanding or just push us into intractable territory.

Kai: It’s like having a roadmap for computational feasibility, showing us exactly where the limits of what we can measure rigorously lie.

Mira: And they also highlight how this approach handles symmetry restrictions effectively; by restricting the SDP hierarchy to specific symmetry sectors, you can determine if a model is stable under known physical constraints.

Lev: If we’re looking at AI architectures, for instance, that could be valuable because it allows us to test if a design is robust against symmetries we already know are important in physics.

Kai: So they're suggesting that the way we approach these models should evolve from just hoping for an accurate result to systematically tracking how the certified bounds improve as our computational power scales up.

Mira: It’s about moving from a single answer to a complete picture of the certainty we can achieve at any given point in our computation.

Lev: I think that formal characterization of complexity is exactly what we need when trying to design fault-tolerant systems that operate within realistic computational budgets, not just theoretical ideals.

Kai: It really gives us a clearer idea of the practical trade-off between how much certainty we need and how much time and compute we’re willing to spend chasing it.

Mira: So, they are essentially offering a method for systematic complexity analysis when studying many-body physics properties that have a spectral gap.

Lev: The main thing I'm taking away is that this framework helps us design better verification pipelines where we can formally prove the absence of certain instabilities in complex models within finite time.

Kai: And this formal proof capability, combined with those tight upper bounds, is what makes the whole approach so compelling for experimentalist-minded researchers who need hard evidence.

Mira: It really pushes us to consider that every physical property we measure needs to be backed by a rigorous mathematical framework if we want it to truly count in condensed matter theory.

Lev: So, this points toward a future where AI systems analyzing physical models can use these certified bounds not just for estimation, but for genuine verification of stability and complexity.

Conclusion: Kai: So we’ve gone through the paper on "The bulk spectral gap is certifiable from above but uncomputable from below," and basically, they’ve shown us a rigorous way to get certified upper bounds on stability using SDPs, but they admit that proving a lower bound remains out of reach.

Mira: That's right; the core result is that we have a complete hierarchy of these upper bounds that become arbitrarily tight as we increase our computational resources, which is significant because it gives us formal proof about stability in the thermodynamic limit.

Lev: For me, this means we can use these rigorous upper bounds to set hard ceilings on the stability of our quantum models; if the certified gap is positive, it’s a formal guarantee against catastrophic phase transitions.

Kai: Exactly; it moves us from just having numerical guesses about stability to actually proving that something *cannot* happen below a certain energy threshold, which is much stronger evidence.

Mira: And those specific results they got on the kagome lattice, like the two point 18J bound and the sharper one point 15J in symmetry sectors, show that this isn't just some abstract math; it’s giving us real numbers to compare against existing numerical estimates.

Kai: So, this work gives us a formal yardstick for stability in the thermodynamic limit using SDPs, and that’s something I can actually use to guide what we build and how we test it.

Lev: I agree; it’s a trade-off between rigor and feasibility, but at least now we know exactly what kind of computational cost we are incurring to get that level of certification.

Kai: That's the core tension here—getting the most rigorous proof possible versus what's actually practical for experimentalists and engineers in the quantum world.

Mira: So, this paper really clarifies where our current theoretical tools stop providing definitive answers and where we need to rely on these certified upper bounds instead.

Kai: That’s the practical application we’ve been hoping for—a formal way to state what stability looks like in terms of these certified bounds, which is something I can actually work with.

Mira: It really shows that for problems like the bulk spectral gap, we can have a complete family of certified upper bounds that get arbitrarily tight with more computation.

Lev: I think the main thing I'm taking away is that this framework helps us design better verification pipelines where we can formally prove the absence of certain instabilities in complex models within finite time.

Kai: And this formal proof capability, combined with those tight upper bounds, is what makes the whole approach so compelling for experimentalist-minded researchers who need hard evidence.

Mira: It's a paper that defines the limits of what we can prove about spectral properties and shows how SDPs can provide certification where other methods fall short.

Kai: That’s what we'll be watching next as we look at how this framework applies to other challenging physical systems.

inria · Universität Würzburg, Institute of Mathematics · State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences · Université de Toulouse; LAAS-CNRS · University of Ljubljana, Faculty of Mathematics and Physics · University of Primorska

quant-ph, cond-mat.stat-mech, math-ph, math.MP

Submitted: 2026-06-02

Updated: 2026-09-28

Comments: 44 pages, 5 figures; Supplementary Information (35 pages) included. Comments welcome! v3: New main result, uncomputability of the bulk spectral gap from below and RE-completeness of the bulk-gaplessness promise problem; main text restructured; improved kagome bounds; title updated (previously: The bulk spectral gap is semi-decidable: a convergent family of certified upper bounds)

Code: https://github.com/wangjie212/SpectralGap

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: Determining spectral gaps in quantum many-body physics is a central challenge, as existing rigorous methods are largely limited to special settings, while variational numerical approaches typically

Key concepts

Bulk Spectral Gap: This refers to the minimum energy difference between the ground state and the first excited state in a large system (the thermodynamic limit). Finding this gap is a central challenge because existing methods often only provide estimates, not certified guarantees.
Semidefinite Programs (SDPs): SDPs are mathematical optimization problems used here to find certified upper bounds on the spectral gap. They are powerful tools in quantum information and many-body physics that allow for rigorous certification of results, though solving them requires significant computational resources.
Dynamical Criterion: This is a specific mathematical condition used to define a locally non-degenerate bulk gap. It checks if the bulk Hamiltonian's spectrum avoids zero up to some positive threshold $\gamma$, which is equivalent to ensuring the system behaves well in terms of energy differences.

Terminology

Spectral Gap — 150× in this paper · explained in 5 episodes
Degeneracy — 14× in this paper · explained in 3 episodes
Core — 8× in this paper · explained in 2 episodes
Frustration — 4× in this paper · explained in 2 episodes
Verification — 3× in this paper · explained in 2 episodes
Consistency — 2× in this paper · explained in 3 episodes
Hilbert Space — 2× in this paper · explained in 2 episodes
Phase Transitions — 2× in this paper · explained in 2 episodes
Antiferromagnetism — 1× in this paper · explained in 1 episode
Area Law — 1× in this paper · explained in 1 episode
Benchmark — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Noncommutative Polynomial Optimization — 1× in this paper · explained in 2 episodes
Physical Constraints — 1× in this paper · explained in 7 episodes
Robustness — 1× in this paper · explained in 5 episodes
Sparsity — 1× in this paper · explained in 4 episodes
Structural Constraints — 1× in this paper · explained in 2 episodes

Summary

Determining spectral gaps in quantum many-body physics is a central challenge, as existing rigorous methods are largely limited to special settings, while variational numerical approaches typically provide estimates rather than certified bounds. The bulk spectral gap is semi-decidable: a convergent family of certified upper bounds. These upper bounds are obtained by solving a series of semidefinite programs (SDPs) and they become arbitrarily tight at the cost of more computational resources. This demonstrates that the bulk spectral gap is semi-decidable, in contrast to undecidability results for alternative notions of spectral gap based on sequences of finite systems with prescribed boundary conditions.

The paper introduces a complete family of certified upper bounds on the bulk spectral gap. These upper bounds are obtained by solving a series of semidefinite programs and they become arbitrarily tight at the cost of more computational resources. A proof-of-principle application to the spin-1/2 kagome lattice Heisenberg antiferromagnet yields a fully general certified upper bound 2.18J, and a sharper bound 1.15J in a physically motivated symmetry sector. These bounds are "far above existing numerical estimates—from gaps of order 10−2 to 10−1J to possibly gapless scenarios [DMS12; He+17; YHW11]—they are, to our knowledge, the first rigorously certified upper bounds on this bulk spectral gap."

The algorithm is built upon SDPs, which are powerful for certified results in quantum information theory and many-body physics. The authors develop a new method to translate a nonlinear formulation of the spectral gap into certified SDP relaxations, proving that this translation yield[s] a complete characterization of the bulk spectral gap problem in the thermodynamic limit.

The framework is rooted in operator algebra, defining local observables as elements of an approximately finite-dimensional C∗-algebra A, and dynamical systems induced by local Hamiltonian families F = HΛ(L), where L controls the size of the finite region. The notion of a locally non-degenerate bulk gap on states is defined via a dynamical criterion: "the system (A, τF, δF) with the state ω is locally non-degenerate bulk-gapped if there exists a constant γ > 0 such that 'the bulk Hamiltonian Hω: 1. is locally non-degenerate in the sense that ker(Hω) = Span omegaω⟩; 2. satisfies the bulk spectral gap condition Spec (Hω) ∩ (0, γ) = ∅.' This dynamical criterion is equivalent to −iω(a∗δF (a)) ≥ γ(ω(a∗a) − ω(a)2)" for all local observables a in the domain of δF.

The central result is the complete SDP hierarchy, which tests whether there exists a KMS ground state satisfying this criterion for a fixed threshold γ. The resulting algorithm, implemented through SDPs indexed by (L, d), is not merely a sequence of necessary tests, but a complete certification procedure; see Supplementary Information Theorem 2.5. Feasibility at every level is equivalent to the existence of such a KMS ground state with a locally non-degenerate bulk spectral gap of at least γ.

The algorithm estimates expectation values in the sense that α min n,d and α max n,d converge monotonically to the extremal expectation values from Eq. (S20): α min n,d ↗ ⟨O⟩min and α max n,d ↘ ⟨O⟩max (S35) as n, d → ∞.

The paper addresses the undecidability results for alternative notions of spectral gaps based on sequences of finite systems with prescribed boundary conditions. The authors show that our method, formulated directly in the bulk, is compatible with those constructions because it addresses a different notion of spectral gaps. They conclude that the bulk spectral gap problem is itself undecidable, or whether it admits a complementary certification method for lower bounds.

In the context of 2D lattice models like the kagome lattice Heisenberg antiferromagnet, certified upper bounds are obtained. For instance, The tightest fully general upper bound on the bulk spectral gap is 2.18J, and in symmetry-restricted sectors, the tightest certified upper bound is 1.15J. These bounds provide rigorous information: if such a bound lies below the energy of a proposed excitation, then that excitation is rigorously excluded from being the lowest bulk excitation.

The paper contrasts the algebraic bulk notion with finite-volume spectral gaps under fixed boundary conditions. While Definition 4.2 defines a non-degenerate uniform spectral gap under OBC, it is noted that a finite-volume uniform gap for some chosen boundary condition is a lower bound for the bulk gap [BDN16, Proposition 5.4]. Furthermore, the paper shows that "the NO-instance of the decision problem Eq.

Improvements for AI systems

This paper introduces a novel, complete, and rigorous framework for certifying upper bounds on the bulk spectral gap of quantum many-body systems in the thermodynamic limit using a hierarchy of Semidefinite Programs (SDPs) based on state polynomial optimization.

The improvements derived from this research can be applied to AI systems by providing tools to rigorously analyze and bound the complexity, stability, and convergence properties of complex, high-dimensional models that exhibit many-body physics characteristics.

Here are the specific improvements and what the improved AI system can achieve:

) Improvements for AI Systems: Rigorous Stability and Complexity Bounds in High-Dimensional Models

The core improvement is moving from variational estimates to rigorously certified upper bounds for spectral properties, which fundamentally changes how we assess model stability.

--- Certified Spectral Gap Certification (Replacing Variational Estimates) ---
The AI system can perform a rigorous check to determine if a complex model (e.g., a neural network representing a physical system, or the dynamics of an LLM) possesses an intrinsic gap separating its ground state from the first excited state in the thermodynamic limit.
This allows for the certification of stability: If the certified upper bound on the spectral gap is strictly positive, it rigorously proves that small perturbations (local excitations) will not cause catastrophic phase transitions or sudden collapse of correlations in that specific limit.
The system can be used to identify criticality or gaplessness in AI models, distinguishing between true physical instability and numerical noise/finite-size artifacts.
--- Hierarchy of Relaxation for Complexity Analysis ---
The framework allows the AI to systematically test whether a given model (represented by a Hamiltonian or interaction structure) is gapped at various levels of computational complexity (indexed by relaxation parameters like degree 'd' and system size 'n').
By tracking the convergence of these certified bounds, the AI can quantify the cost required to achieve higher certainty about a model's stability. This provides a rigorous measure of when numerical approximations are sufficient versus when exponentially increasing computational resources is necessary for a definitive answer.
--- Symmetry-Restricted Model Analysis ---
The system can be used to analyze AI architectures (like protein folding models or complex neural network layers) under specific physical symmetries (e.g., time-reversal, permutation symmetries).
By restricting the SDP hierarchy to these symmetry sectors, the AI can determine if a model is stable only under certain constraints (e.g., Is this AI architecture stable against rotations?). This allows for targeted optimization of architectures that are robust against known physical symmetries.
--- Robustness Against Boundary/Contextual Conditions ---
The paper distinguishes between bulk spectral gaps (intrinsic property) and finite-volume gaps with fixed boundary conditions (extrinsic property). The AI can be trained to analyze models under different contextual constraints (analogous to boundary conditions).
It can rigorously distinguish between intrinsic bulk stability and stability induced purely by the way the model is initialized or constrained, which is crucial for understanding how AI systems behave when transitioning between different operational modes.
--- Semi-Decidability of Model Properties ---
The paper proves that the bulk spectral gap problem is semi-decidable (i.e., we can always rule out a proposed gap size). This provides a formal guarantee: for any proposed stability threshold, an algorithm exists that will eventually confirm whether the model is stable above or below that threshold.
This capability allows for the creation of automated verification pipelines where researchers can formally prove the absence of certain instabilities in complex AI models within finite time.