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_Φ\to \infty$ . 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 $H^2 \succeq εH$ . To show this inequality, we split $H^2$ 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_Φ\to \infty$ 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.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_Φ\to \infty$. 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 $H^2 \succeq εH$. To show this inequality, we split $H^2$ 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_Φ\to \infty$ 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.

arXiv:2610.18854Oct 13, 20260 citations

Experiments in quadratic 0–1 programming

Francisco Barahona, Michael Jünger, Gerhard Reinelt

Mathematical ProgrammingMay 1, 1989196 citations

Exact Fixed and Adaptive Reconstruction of Sparse Complex States from Interference Measurements

Ivo Vajc

Exact Fixed and Adaptive Reconstruction of Sparse Complex States from Interference Measurements Abstract We investigate exact fixed and adaptive reconstruction in a finite, noiseless complex interference model. The admissible states are two-sparse vectors over the Gaussian integers, with two nonzero amplitudes normalized to 1 and one of four relative phases: 1, i, −1, or −i. Each admissible measurement consists of a single-coordinate phase gate followed by a pairwise interference-intensity observation. For this restricted measurement family, we establish the exact minimum number of nonadaptive measurements: F(n) = n(n − 1), for n ≥ 3. We also construct a deterministic adaptive reconstruction algorithm requiring at most n + 1 measurements for n = 3 and n ≥ 5, and at most six measurements for n = 4. These results establish a quadratic-versus-linear separation between optimal nonadaptive reconstruction complexity and an achievable adaptive reconstruction bound. Two independently implemented exact-arithmetic Python programs additionally compute optimal adaptive worst-case measurement depths of 4, 5, 5, and 6 for systems with 3, 4, 5, and 6 sites, respectively. The manuscript provides mathematical proofs, a constructive reconstruction procedure, finite computational verification, and a discussion of related phase-retrieval and adaptive-testing literature. The results concern a precisely specified discrete measurement model. They do not establish general phase-retrieval lower bounds, optimal asymptotic adaptive complexity, noise robustness, quantum computational speedup, or a Fibonacci-specific advantage. Reproducibility The accompanying archive contains the LaTeX manuscript, compiled PDF, bibliography, and two standalone Python 3 verification programs. The programs use exact arithmetic, require no external dependencies, and can be executed offline. Publication status: Preprint, version 1.1. Not peer-reviewed. OpenAI ChatGPT was used substantially in mathematical exploration, programming, certificate design, and manuscript drafting. The named author is responsible for reviewing the mathematics, checking the released files, verifying citations and originality claims, and deciding whether to submit.Exact Fixed and Adaptive Reconstruction of Sparse Complex States from Interference Measurements Abstract We investigate exact fixed and adaptive reconstruction in a finite, noiseless complex interference model. The admissible states are two-sparse vectors over the Gaussian integers, with two nonzero amplitudes normalized to 1 and one of four relative phases: 1, i, −1, or −i. Each admissible measurement consists of a single-coordinate phase gate followed by a pairwise interference-intensity observation. For this restricted measurement family, we establish the exact minimum number of nonadaptive measurements: F(n) = n(n − 1), for n ≥ 3. We also construct a deterministic adaptive reconstruction algorithm requiring at most n + 1 measurements for n = 3 and n ≥ 5, and at most six measurements for n = 4. These results establish a quadratic-versus-linear separation between optimal nonadaptive reconstruction complexity and an achievable adaptive reconstruction bound. Two independently implemented exact-arithmetic Python programs additionally compute optimal adaptive worst-case measurement depths of 4, 5, 5, and 6 for systems with 3, 4, 5, and 6 sites, respectively. The manuscript provides mathematical proofs, a constructive reconstruction procedure, finite computational verification, and a discussion of related phase-retrieval and adaptive-testing literature. The results concern a precisely specified discrete measurement model. They do not establish general phase-retrieval lower bounds, optimal asymptotic adaptive complexity, noise robustness, quantum computational speedup, or a Fibonacci-specific advantage. Reproducibility The accompanying archive contains the LaTeX manuscript, compiled PDF, bibliography, and two standalone Python 3 verification programs. The programs use exact arithmetic, require no external dependencies, and can be executed offline. Publication status: Preprint, version 1.1. Not peer-reviewed. OpenAI ChatGPT was used substantially in mathematical exploration, programming, certificate design, and manuscript drafting. The named author is responsible for reviewing the mathematics, checking the released files, verifying citations and originality claims, and deciding whether to submit.

Oct 25, 20260 citations

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physicsJan 1, 20110 citations

Approximation Algorithms for Quadratic Programming

Minyue Fu, Zhi-Quan Tom Luo, Yinyu Ye Y

Journal of Combinatorial OptimizationMar 1, 199879 citations

Advances in mathematical programming-based error-correction decoding

Michael Helmling

The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.The formulation of the decoding problem for linear block codes as an integer program (IP) with a rather tight linear programming (LP) relaxation has made a central part of channel coding accessible for the theory and methods of mathematical optimization, especially integer programming, polyhedral combinatorics and also algorithmic graph theory, since the important class of turbo codes exhibits an inherent graphical structure. We present several novel models, algorithms and theoretical results for error-correction decoding based on mathematical optimization. Our contribution includes a partly combinatorial LP decoder for turbo codes, a fast branch-and-cut algorithm for maximum-likelihood (ML) decoding of arbitrary binary linear codes, a theoretical analysis of the LP decoder's performance for 3-dimensional turbo codes, compact IP models for various heuristic algorithms as well as ML decoding in combination with higher-order modulation, and, finally, first steps towards an implementation of the LP decoder in specialized hardware. The scientific contributions are presented in the form of seven revised reprints of papers that appeared in peer-reviewed international journals or conference proceedings. They are accompanied by an extensive introductory part that reviews the basics of mathematical optimization, coding theory, and the previous results on LP decoding that we rely on afterwards.

Jul 24, 20150 citations

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_Φ\to \infty

. 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

H^2 \succeq εH

. To show this inequality, we split

H^2

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_Φ\to \infty

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.