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• 0 citations
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 approaches, such as variational calculations, consist of writing down a wave function ansatz and minimizing over the possible states expressible by this ansatz, one can alternatively formulate the problem as a noncommutative polynomial optimization problem. This optimization problem can then be addressed using a hierarchy of semidefinite programming relaxations. In contrast to variational calculations, the semidefinite program can provide lower bounds for ground state energies and upper and lower 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 leveraging the inherent structures of the system can significantly mitigate these scalability challenges and thus allows us to compute meaningful bounds for quantum spin systems on up to $16\times16$ square lattices.

Journal reference
SciPost Phys. 21, 074 (2026)
DOI
10.21468/SciPostPhys.21.3.074
Comments
37 pages, 9 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•15 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•0 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 $\varepsilon$, local observables can be approximated by a convex optimization program of quasi-polynomial size in $1/\varepsilon$.

arXiv:2311.18706•Nov 30, 2023•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/ε.

Nature Communications•Aug 27, 2024•18 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•0 citations

Lower bounds to variational problems with guarantees

Jens Eisert

Variational methods play an important role in the study of quantum many-body problems, both in the flavor of classical variational principles based on tensor networks as well as of quantum variational principles in near-term quantum computing. This work stresses that for translationally invariant lattice Hamiltonians with periodic boundary conditions, one can easily derive efficiently computable lower bounds to ground state energies that can and should be compared with variational principles providing upper bounds. As small technical results, it is shown that (i) the Anderson bound and a (ii) common hierarchy of semidefinite relaxations both provide approximations with performance guarantees that scale as a constant in the energy density for cubic lattices. (iii) Also, the Anderson bound is systematically improved as a hierarchy of semidefinite relaxations inspired by the quantum marginal problem.

arXiv:2301.06142•Physical Review A•Jan 6, 2026•5 citations
A fundamental challenge in quantum physics is determining the ground-state properties of many-body systems. Whereas standard approaches, such as variational calculations, consist of writing down a wave function ansatz and minimizing over the possible states expressible by this ansatz, one can alternatively formulate the problem as a noncommutative polynomial optimization problem. This optimization problem can then be addressed using a hierarchy of semidefinite programming relaxations. In contrast to variational calculations, the semidefinite program can provide lower bounds for ground state energies and upper and lower 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 leveraging the inherent structures of the system can significantly mitigate these scalability challenges and thus allows us to compute meaningful bounds for quantum spin systems on up to 16×1616\times1616×16 square lattices.
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 ε\varepsilonε, local observables can be approximated by a convex optimization program of quasi-polynomial size in 1/ε1/\varepsilon1/ε.
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/ε.
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.
Variational methods play an important role in the study of quantum many-body problems, both in the flavor of classical variational principles based on tensor networks as well as of quantum variational principles in near-term quantum computing. This work stresses that for translationally invariant lattice Hamiltonians with periodic boundary conditions, one can easily derive efficiently computable lower bounds to ground state energies that can and should be compared with variational principles providing upper bounds. As small technical results, it is shown that (i) the Anderson bound and a (ii) common hierarchy of semidefinite relaxations both provide approximations with performance guarantees that scale as a constant in the energy density for cubic lattices. (iii) Also, the Anderson bound is systematically improved as a hierarchy of semidefinite relaxations inspired by the quantum marginal problem.