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

Scalable Ground-State Certification of Quantum Spin Systems via Structured Noncommutative Polynomial Optimization

Jie Wang, David Jansen, Irénée Frerot, Marc-Olivier Renou, Victor Magron, Antonio Acín

quant-phmath.OCSubmitted Apr 2, 2026• Announced Apr 3, 2026• 6 citations• Revised Aug 12, 2026 (v2)
v1 · Apr 2, 2026v2 · Aug 12, 2026
arXivHTMLPDF

Abstract

A fundamental challenge in quantum physics is determining the ground-state properties of many-body systems. Whereas standard variational approaches posit a wave-function ansatz and minimize over the possible states expressible by that ansatz, the problem can alternatively be formulated as a noncommutative polynomial optimization problem and treated through a hierarchy of semidefinite programming relaxations. In contrast to variational calculations, these relaxations provide lower bounds on ground-state energies and both lower and upper bounds on observable expectation values. However, this approach typically suffers from severe scalability issues, limiting its applicability to small-to-medium-scale systems. In this article, we demonstrate that systematically leveraging the inherent structures of the system can substantially mitigate these scalability challenges and thus permits computing meaningful bounds for quantum spin systems on square lattices of size up to $16\times16$.

Journal reference
SciPost Phys. 21, 074 (2026)
DOI
10.21468/SciPostPhys.21.3.074
Comments
42 pages, 11 figures

Related papers

Certifying Ground-State Properties of Many-Body Systems

Jie Wang, Jacopo Surace, Irénée Frérot +4 more

A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024

arXiv:2310.05844•Physical Review X•Jul 11, 2024•32 citations

Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians

Igor Klep, Nando Leijenhorst, Victor Magron

The $k$-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For $k$-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most $C(k)ξ^{n,4}_{d+1}/n$, where $ξ^{n,4}_{d+1}$ is the smallest root of a Krawtchouk polynomial and $C(k)$ is independent of the number of qubits $n$ and the hierarchy level $d$. General $k$-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.

quant-pharXiv:2605.29959•May 29, 2026•2 citations

Certified algorithms for equilibrium states of local quantum Hamiltonians

Hamza Fawzi, Omar Fawzi, Samuel O. Scalet

Predicting observables in equilibrium states is a central yet notoriously hard question in quantum many-body systems. In the physically relevant thermodynamic limit, certain mathematical formulations of this task have even been shown to result in undecidable problems. Using a finite-size scaling of algorithms devised for finite systems often fails due to the lack of certified convergence bounds for this limit. In this work, we design certified algorithms for computing expectation values of observables in the equilibrium states of local quantum Hamiltonians, both at zero and positive temperature. Importantly, our algorithms output rigorous lower and upper bounds on these values. This allows us to show that expectation values of local observables can be approximated in finite time, contrasting related undecidability results. When the Hamiltonian is commuting on a 2-dimensional lattice, we prove fast convergence of the hierarchy at high temperature and as a result for a desired precision ε, local observables can be approximated by a convex optimization program of quasi-polynomial size in 1/ε.

arXiv:2311.18706•Nature Communications•Aug 27, 2024•48 citations

Noisy intermediate-scale quantum algorithm for semidefinite programming

Kishor Bharti, Tobias Haug, Vlatko Vedral +1 more

Semidefinite programs (SDPs) are convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization, and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an nondeterministic polynomial time-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for solving SDPs. The classical optimization program of our NISQ solver is another SDP over a lower dimensional ansatz space. We harness the SDP-based formulation of the Hamiltonian ground-state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex and can be solved in polynomial time with the number of ansatz parameters, and every local minimum is a global minimum. We find numeric evidence that NISQ SDP can improve the estimation of ground-state energies in a scalable manner. Further, we efficiently solve constrained problems to calculate the excited states of Hamiltonians, find the lowest energy of symmetry constrained Hamiltonians, and determine the optimal measurements for quantum state discrimination. We demonstrate the potential of our approach by finding the largest eigenvalue of up to ${2}^{1000}$ dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.

arXiv:2106.03891•Physical Review A•May 31, 2022•39 citations

Bootstrap certification of string order in quantum spin chains

Sagnik Banerjee, Haoyu Guo, Debanjan Chowdhury

The many-body bootstrap certifies ground-state properties by minimizing energy over correlators constrained only by positivity, without any variational wavefunction. Its cost, however, grows exponentially with the size of the operators involved, placing the long-range string correlators that diagnose topological phases out of reach. We overcome this by treating string operators as primary objects: bare and endpoint-dressed strings satisfy a closed operator algebra with one another and with local words, yielding a semidefinite program whose cost grows only polynomially with string length. A single computation then yields estimates of string correlators of all lengths. Rigorous two-sided bounds are obtained for each target string once the ground-state energy is pinned within a window. When benchmarked against density-matrix renormalization group computations on the cluster Ising and spin$-1$ Heisenberg chains, the method certifies the nonlocal string order of the cluster and Haldane phases directly from the Hamiltonian. Our rigorous certification of string order parameters reveal that the sharpness of the bounds is set by which operators enter the calculation, not by their length alone. By exploiting algebraic closure of strings and local words, our framework lifts spatially extended observables into polynomially tractable bootstrap variables, opening up a route to wavefunction-free certification of nonlocal order in quantum many-body systems.

cond-mat.str-elCross-listedarXiv:2609.22420•Sep 22, 2026•1 citation

A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems

Kshiti Sneh Rai, Ilya Kull, Patrick Emonts +3 more

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.

arXiv:2411.03680•Quantum•Apr 13, 2026•15 citations
A fundamental challenge in quantum physics is determining the ground-state properties of many-body systems. Whereas standard variational approaches posit a wave-function ansatz and minimize over the possible states expressible by that ansatz, the problem can alternatively be formulated as a noncommutative polynomial optimization problem and treated through a hierarchy of semidefinite programming relaxations. In contrast to variational calculations, these relaxations provide lower bounds on ground-state energies and both lower and upper bounds on observable expectation values. However, this approach typically suffers from severe scalability issues, limiting its applicability to small-to-medium-scale systems. In this article, we demonstrate that systematically leveraging the inherent structures of the system can substantially mitigate these scalability challenges and thus permits computing meaningful bounds for quantum spin systems on square lattices of size up to 16×1616\times1616×16.
A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024
The kkk-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For kkk-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most C(k)ξd+1n,4/nC(k)ξ^{n,4}_{d+1}/nC(k)ξd+1n,4​/n, where ξd+1n,4ξ^{n,4}_{d+1}ξd+1n,4​ is the smallest root of a Krawtchouk polynomial and C(k)C(k)C(k) is independent of the number of qubits nnn and the hierarchy level ddd. General kkk-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.
Predicting observables in equilibrium states is a central yet notoriously hard question in quantum many-body systems. In the physically relevant thermodynamic limit, certain mathematical formulations of this task have even been shown to result in undecidable problems. Using a finite-size scaling of algorithms devised for finite systems often fails due to the lack of certified convergence bounds for this limit. In this work, we design certified algorithms for computing expectation values of observables in the equilibrium states of local quantum Hamiltonians, both at zero and positive temperature. Importantly, our algorithms output rigorous lower and upper bounds on these values. This allows us to show that expectation values of local observables can be approximated in finite time, contrasting related undecidability results. When the Hamiltonian is commuting on a 2-dimensional lattice, we prove fast convergence of the hierarchy at high temperature and as a result for a desired precision ε, local observables can be approximated by a convex optimization program of quasi-polynomial size in 1/ε.
Semidefinite programs (SDPs) are convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization, and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an nondeterministic polynomial time-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for solving SDPs. The classical optimization program of our NISQ solver is another SDP over a lower dimensional ansatz space. We harness the SDP-based formulation of the Hamiltonian ground-state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex and can be solved in polynomial time with the number of ansatz parameters, and every local minimum is a global minimum. We find numeric evidence that NISQ SDP can improve the estimation of ground-state energies in a scalable manner. Further, we efficiently solve constrained problems to calculate the excited states of Hamiltonians, find the lowest energy of symmetry constrained Hamiltonians, and determine the optimal measurements for quantum state discrimination. We demonstrate the potential of our approach by finding the largest eigenvalue of up to 21000{2}^{1000}21000 dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
The many-body bootstrap certifies ground-state properties by minimizing energy over correlators constrained only by positivity, without any variational wavefunction. Its cost, however, grows exponentially with the size of the operators involved, placing the long-range string correlators that diagnose topological phases out of reach. We overcome this by treating string operators as primary objects: bare and endpoint-dressed strings satisfy a closed operator algebra with one another and with local words, yielding a semidefinite program whose cost grows only polynomially with string length. A single computation then yields estimates of string correlators of all lengths. Rigorous two-sided bounds are obtained for each target string once the ground-state energy is pinned within a window. When benchmarked against density-matrix renormalization group computations on the cluster Ising and spin−1-1−1 Heisenberg chains, the method certifies the nonlocal string order of the cluster and Haldane phases directly from the Hamiltonian. Our rigorous certification of string order parameters reveal that the sharpness of the bounds is set by which operators enter the calculation, not by their length alone. By exploiting algebraic closure of strings and local words, our framework lifts spatially extended observables into polynomially tractable bootstrap variables, opening up a route to wavefunction-free certification of nonlocal order in quantum many-body systems.
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.