Estimating spectral gaps of quantum many-body Hamiltonians is a highly challenging computational task, even under assumptions of locality and translation-invariance. Yet, the quest for rigorous gap certificates is motivated by their broad applicability, ranging from many-body physics to quantum computing and classical sampling techniques. Here we present a general method for obtaining lower bounds on the spectral gap of frustration-free quantum Hamiltonians in the thermodynamic limit. We formulate the gap certification problem as a hierarchy of optimization problems (semidefinite programs) in which the certificate – a proof of a lower bound on the gap – is improved with increasing levels. Our approach encompasses existing finite-size methods, such as Knabe's bound and its subsequent improvements, as those appear as particular possible solutions in our optimization, which is thus guaranteed to either match or surpass them. We demonstrate the power of the method on one-dimensional spin-chain models where we observe an improvement by several orders of magnitude over existing finite size criteria in both the accuracy of the lower bound on the gap, as well as the range of parameters in which a gap is detected.
Estimating spectral gaps of quantum many-body Hamiltonians is a highly challenging computational task, even under assumptions of locality and translation-invariance. Yet, the quest for rigorous gap certificates is motivated by their broad applicability, ranging from many-body physics to quantum computing and classical sampling techniques. Here we present a general method for obtaining lower bounds on the spectral gap of frustration-free quantum Hamiltonians in the thermodynamic limit. We formulate the gap certification problem as a hierarchy of optimization problems (semidefinite programs) in which the certificate – a proof of a lower bound on the gap – is improved with increasing levels. Our approach encompasses existing finite-size methods, such as Knabe's bound and its subsequent improvements, as those appear as particular possible solutions in our optimization, which is thus guaranteed to either match or surpass them. We demonstrate the power of the method on one-dimensional spin-chain models where we observe an improvement by several orders of magnitude over existing finite size criteria in both the accuracy of the lower bound on the gap, as well as the range of parameters in which a gap is detected.
We give a convergent hierarchy of SDP certificates for lower bounds on the spectral gap of a local qubit Hamiltonian H. Our approach is based on the NPA hierarchy applied to a polynomially-sized system of constraints defining the universal enveloping algebra of the Lie algebra su(2n) along with additional constraints which force the representation to be ∧2(C2n), one which the induced Hamiltonian has ground energy λ0(H)+λ1(H). Combined with an upper bound on the ground state energy, which can be obtained either using a hierarchy introduced by Fawzi, Fawzi, and Scalet or a noncommutative analog developed by Klep, Magron, Massé, and Volčič of a hierarchy introduced by Lasserre, we obtain lower bounds on the spectral gap of H without assuming frustration-freeness or geometric locality. We prove that the resulting certificates have polynomial size at fixed degree and converge at level n. As illustrations of the certificates which can be obtained, we show that for a commuting 1-local Hamiltonian the hierarchy certifies the optimal bound on its spectral gap and prove that similar hierarchies require degree growing with n to certify the same bound. We then extend this to prove a lower bound on the spectral gap of the transverse-field XY model, which is not frustration-free, on arbitrary regular graphs without any assumption of geometric locality.
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.
We develop a bootstrap approach to deriving lower bounds on the spectral gap of the first Haldane pseudopotential Hamiltonian on the sphere with NΦ flux quanta for arbitrary NΦ, including in the thermodynamic limit NΦ→∞. This method can in principle be generalized to pseudopotentials describing other model wavefunctions such as the Moore--Read state or Read--Rezayi sequence. Our approach is based on Knabe's observation that if H is a Hamiltonian with ground state energy zero then the spectral gap is at least ε>0 if and only if H2⪰εH. To show this inequality, we split H2 into two parts, one that can be analytically bounded and another that can be bounded using a finite semidefinite program (SDP). Crucially, the size of this program is determined only by cutoff parameters, and the program depends on NΦ only parametrically, allowing us to obtain numerically exact (up to solver precision) lower bounds on the gap. In order to turn these numerical bounds into mathematically rigorous results, we introduce an algorithm that can produce nearly-optimal exact interior feasible points for large rational SDPs even if the affine constraints are highly redundant and ill-conditioned. We additionally provide an algorithm that establishes the rank stability of the SDP in the NΦ→∞ limit, which is needed to certify the bound in the thermodynamic limit. Beyond establishing a Laughlin gap greater than 1/100 in the thermodynamic limit and revealing a potential method for deriving spectral gap lower bounds for other pseudopotentials, our work provides a general method for turning numerical SDP bounds into rigorous mathematical proofs, which may have wide applicability. In particular, this work demonstrates that bootstrap methods can be used to rigorously resolve major open problems in quantum many-body physics.
Here is the finding. For frustration-free spin-1/2 chains, the spectral gap question is decidable. We can completely classify these systems into gapped and gapless phases. This holds even though the general problem for translationally invariant Hamiltonians is undecidable, as shown by Cubitt, Perez-Garcia, and Wolf in 2015. Here is the context. We are talking about Hamiltonians written as a sum of local terms, each positive semidefinite, with a ground state annihilated by every term. That is the frustration-free condition. The spectral gap is the energy difference between the first excited state and the ground state. For a general quantum many-body system, determining whether that gap closes in the thermodynamic limit is notoriously hard. But for this restricted class, the mathematics gives us a clean answer. Here is the mechanism. The key is the matrix product state representation. The ground state of a gapped phase has finite correlation length. Its MPS transfer matrix is injective Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
A central question in quantum many-body physics is estimating the ground energy of a k-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random n-qubit Hamiltonian system defined as the sum of signed k-local Pauli operators. In particular, we prove that for any constant ℓ, there exists an efficiently computable length nO(ℓ) certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an ε-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on k-XOR refutations to k-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed k-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) Ω(logn)-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to Ω(n)-levels.
Preprint of the article "A fixed-level certification dichotomy for an infinite family of frustration-free spin chains" (22 pages, no figures). To every finite loopless directed graph T the paper attaches a rational, range-three, frustration-free spin-chain interaction: arcs of T carry hopping bands for domain walls, missing arcs act as hard local penalties. The main theorem is the exact three-term equivalence: T is acyclic <=> liminf_m gap_m(T) > 0 <=> delta_LTI(5) > 0, where gap_m is the spectral gap of the periodic chain on m sites and delta_LTI(5) is the value of the local translation-invariant (LTI) semidefinite certification hierarchy at level 5, its first sound level. The certification level is fixed while the size of the graph and the local Hilbert-space dimension are unbounded across the family. To the author's knowledge, this is the first fixed-level completeness result for a spectral-gap certification hierarchy over an infinite family of frustration-free chains: a single finite combinatorial invariant, acyclicity, decides both the thermodynamic spectral gap and the success of the certificate at one universal level. The acyclic direction is proved by an explicit rational certificate, a superpotential built from a topological height and three local corrections, giving delta_LTI(5) >= min{1/48, 1/sqrt(12H)} for a DAG of height H. The cyclic direction is made quantitative by a free-fermion analysis of the invariant winding sectors: directed cycles carry a diffusive lowest mode of energy of order 1/m^2, and the finite-volume gaps of the directed 2- and 3-cycles are computed exactly, 2(1-cos(pi/m)) and 2(1-cos(2pi/m)). The relationship with the PVBS chains of Bachmann and Nachtergaele and with earlier gapped-gapless classifications is discussed explicitly. All computer-assisted statements use exact symbolic arithmetic. The complete reproducibility package (symbolic pipeline, generated blocks with exact characteristic polynomials, Sturm data, LDL^T certificates, SHA-256 digests) is archived separately at https://doi.org/10.5281/zenodo.21790411. The manuscript has been submitted to Reports on Mathematical Physics.