pith. sign in

arxiv: 2605.29959 · v1 · pith:D273IG3Jnew · submitted 2026-05-28 · 🪐 quant-ph · math.OC

Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians

Igor Klep , Nando Leijenhorst , Victor Magron This is my paper

Pith reviewed 2026-06-29 06:52 UTC · model grok-4.3

classification 🪐 quant-ph math.OC
keywords semidefinite programmingground-state energiesPauli Hamiltoniansconvergence ratesKrawtchouk polynomialsnoncommutative optimizationquantum many-body systems
0
0 comments X

The pith

For k-local even-weight Pauli Hamiltonians both SDP hierarchies bound the ground-state energy with error at most C(k) times a Krawtchouk root divided by n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves explicit error rates for semidefinite programming hierarchies that certify ground-state energies of quantum many-body systems. For Hamiltonians whose Pauli expansion has only even-weight terms, both the lower-bound and upper-bound relaxations converge with an error no larger than C(k) times the smallest root of a Krawtchouk polynomial divided by the number of qubits. A single ancilla qubit reduces the general case to this even-weight setting. These rates give the first quantitative finite-level guarantees, showing that low hierarchy levels already produce accurate results for large systems since the constant factor does not depend on n or the level d.

Core claim

The authors show that for k-local Hamiltonians with only even-weight Pauli terms, the error of both the NPA-type lower-bound hierarchy and the upper-bound hierarchy is at most C(k) ξ^{n,4}_{d+1}/n, with C(k) independent of n and d, and that general cases reduce to this by adding one ancilla qubit. The proof relies on constructing almost-reproducing kernels for the Pauli algebra whose spectra are related to Krawtchouk polynomials.

What carries the argument

Almost-reproducing kernels for the Pauli algebra whose spectra are tied to the roots of Krawtchouk polynomials to produce the error bound.

If this is right

  • The approximation error shrinks as 1/n for fixed hierarchy level d as the system size grows.
  • Adding one ancilla qubit preserves the spectrum while allowing the even-weight analysis to apply.
  • The constant C(k) depends only on locality k, not on system size or relaxation order.
  • Low levels of the hierarchy already yield useful certificates for large n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The kernel construction technique could be adapted to other algebras or Hamiltonians beyond Pauli.
  • Numerical implementations might use the bound to decide when to stop increasing the hierarchy level.
  • This approach connects ideas from commutative polynomial optimization to the noncommutative quantum setting.

Load-bearing premise

The almost-reproducing kernels must have spectra exactly matching the Krawtchouk polynomial roots in the manner needed to yield the stated error term.

What would settle it

Compute the actual hierarchy error for a concrete k-local even-weight Hamiltonian with small n and compare it against the predicted upper bound C(k) ξ / n; if the error exceeds the bound, the claim fails.

Figures

Figures reproduced from arXiv: 2605.29959 by Igor Klep, Nando Leijenhorst, Victor Magron.

Figure 1
Figure 1. Figure 1: Normalized smallest Krawtchouk roots controlling the convergence rates in Theorems 1 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original abstract

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)\xi^{n,4}_{d+1}/n$, where $\xi^{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves explicit quantitative convergence rates for the NPA-type lower-bound hierarchy and a matching upper-bound hierarchy on the ground-state energy of k-local Pauli Hamiltonians. For Hamiltonians whose Pauli expansion contains only even-weight terms, both hierarchies achieve error at most C(k) ξ^{n,4}_{d+1}/n, where ξ^{n,4}_{d+1} is the smallest root of a Krawtchouk polynomial of degree d+1 and C(k) is independent of n and d. The general (odd-weight) case reduces to the even-weight case by adding one ancilla qubit. The proof proceeds by constructing almost-reproducing kernels for the Pauli algebra and relating their spectra to Krawtchouk polynomials, yielding a noncommutative analogue of recent kernel-based analyses in commutative polynomial optimization.

Significance. If the central derivation holds, the result supplies the first quantitative finite-level accuracy guarantees for noncommutative SDP relaxations of Pauli Hamiltonians. This is a substantive advance for Hamiltonian complexity and quantum many-body physics, where only qualitative finite-convergence statements were previously available. The explicit 1/n scaling with a constant independent of both system size and hierarchy level, together with the Krawtchouk connection, strengthens the practical utility of low-level NPA relaxations.

major comments (1)
  1. [Abstract, final paragraph; kernel-construction section] Abstract (final paragraph) and the kernel-construction section: the quantitative error bound C(k) ξ^{n,4}_{d+1}/n is obtained only if the spectra of the constructed almost-reproducing kernels satisfy a precise relation to the roots of the Krawtchouk polynomial K_{d+1}^{n,4}. The manuscript must explicitly derive how the almost-reproducing property and the eigenvalue formula together produce the claimed 1/n rate independent of d; any mismatch in this spectral identification would invalidate the stated convergence rate.
minor comments (2)
  1. Notation for the Krawtchouk polynomials and the parameter 4 in ξ^{n,4}_{d+1} should be defined at first use and cross-referenced to the standard definition in the literature.
  2. The reduction via one ancilla qubit is stated to preserve the spectrum; a brief explicit verification of this step would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the need for greater explicitness in the derivation of the quantitative error bound. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract, final paragraph; kernel-construction section] Abstract (final paragraph) and the kernel-construction section: the quantitative error bound C(k) ξ^{n,4}_{d+1}/n is obtained only if the spectra of the constructed almost-reproducing kernels satisfy a precise relation to the roots of the Krawtchouk polynomial K_{d+1}^{n,4}. The manuscript must explicitly derive how the almost-reproducing property and the eigenvalue formula together produce the claimed 1/n rate independent of d; any mismatch in this spectral identification would invalidate the stated convergence rate.

    Authors: The kernel-construction section already derives the eigenvalues of the almost-reproducing kernels via the representation theory of the Pauli algebra and identifies them with the roots of the Krawtchouk polynomial K_{d+1}^{n,4}. The almost-reproducing property is then used to bound the duality gap by the smallest such root; the factor 1/n arises directly from the normalization of the kernel (which scales as 1/n for the trace inner product on n qubits) together with the k-locality of the Hamiltonian, which contributes only to the constant C(k). This produces the stated rate independent of both n and d. Nevertheless, to address the referee's concern about transparency, we will insert a short dedicated paragraph immediately after the eigenvalue formula that walks through the algebraic steps from the reproducing property to the 1/n scaling. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation constructs kernels and relates spectra to known Krawtchouk polynomials independently

full rationale

The paper derives the quantitative error bound C(k) ξ^{n,4}_{d+1}/n by constructing almost-reproducing kernels for the Pauli algebra and relating their spectra to Krawtchouk polynomials (standard objects from coding theory). The abstract explicitly describes this as a noncommutative analogue of existing commutative kernel analyses, with no self-citations, fitted inputs renamed as predictions, self-definitional steps, or ansatzes smuggled via prior work by the same authors. The reduction to the even-weight case via ancilla is a standard spectrum-preserving transformation. The derivation chain is self-contained against external mathematical benchmarks and does not reduce any claimed prediction to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract alone supplies no free parameters, invented entities, or non-standard axioms; the result is presented as a proof relying on standard properties of Krawtchouk polynomials and the Pauli algebra.

pith-pipeline@v0.9.1-grok · 5773 in / 1226 out tokens · 31861 ms · 2026-06-29T06:52:52.123801+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra

    quant-ph 2026-06 unverdicted novelty 8.0

    Explicit convergence rates for noncommutative SOS hierarchies on the Pauli algebra are bounded using smallest roots of Krawtchouk polynomials.

Reference graph

Works this paper leans on

35 extracted references · 6 canonical work pages · cited by 1 Pith paper

  1. [1]

    The Complexity of the Local Hamiltonian Problem

    Julia Kempe, Alexei Kitaev, and Oded Regev. The Complexity of the Local Hamiltonian Problem. SIAM Journal on Computing, 35(5):1070–1097, January 2006.https://epubs.siam.org/doi/10. 1137/S0097539704445226

    2006

  2. [2]

    Quantum hamiltonian complexity

    Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum hamiltonian complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159–282, 2015

    2015

  3. [3]

    Oxford University Press, 2004

    Henrik Bruus and Karsten Flensberg.Many-Body Quantum Theory in Condensed Matter Physics: An Introduction. Oxford University Press, 2004

    2004

  4. [4]

    Certifying ground-state properties of many-body systems.Physical Review X, 14(3):031006, 2024

    Jie Wang, Jacopo Surace, Irénée Frérot, Benoît Legat, Marc-Olivier Renou, Victor Magron, and Antonio Acín. Certifying ground-state properties of many-body systems.Physical Review X, 14(3):031006, 2024

    2024

  5. [5]

    Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik

    James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. Simulation of electronic structure hamil- tonians using quantum computers.Molecular Physics, 109(5):735–750, 2011

    2011

  6. [6]

    Mazziotti

    David A. Mazziotti. Realization of quantum chemistry without wave functions through first-order semidefinite programming.Phys. Rev. Lett., 93:213001, Nov 2004

    2004

  7. [7]

    The complexity of antiferromagnetic interactions and 2D lat- tices.Quantum Information and Computation, 17(7&8):636–672, May 2017.http://www.rintonpress

    Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lat- tices.Quantum Information and Computation, 17(7&8):636–672, May 2017.http://www.rintonpress. com/journals/doi/QIC17.7-8-6.html

    2017

  8. [8]

    Approximation Algorithms for QMA-Complete Problems.SIAM Journal on Computing, 41(4):1028–1050, January 2012.https://epubs.siam.org/doi/10.1137/ 110842272

    Sevag Gharibian and Julia Kempe. Approximation Algorithms for QMA-Complete Problems.SIAM Journal on Computing, 41(4):1028–1050, January 2012.https://epubs.siam.org/doi/10.1137/ 110842272. 18

    2012

  9. [9]

    Fernando G. S. L. Brandão and Aram W. Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47–80, 2016

    2016

  10. [10]

    An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

    Robbie King. An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs. Quantum, 7:1180, November 2023.https://quantum-journal.org/papers/q-2023-11-09-1180/

    2023

  11. [11]

    William Helton and Scott A

    J. William Helton and Scott A. McCullough. A positivstellensatz for non-commutative polynomials. Trans. Am. Math. Soc., 356(9):3721–3737, 2004

    2004

  12. [12]

    Bounding the set of quantum correlations

    Miguel Navascués, Stefano Pironio, and Antonio Acín. Bounding the set of quantum correlations. Physical Review Letters, 98:010401, 2007

    2007

  13. [13]

    A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.New Journal of Physics, 10(7):073013, 2008

    Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations.New Journal of Physics, 10(7):073013, 2008

    2008

  14. [14]

    SpringerBriefs in Mathematics

    Sabine Burgdorf, Igor Klep, and Janez Povh.Optimization of Polynomials in Non-Commuting Vari- ables. SpringerBriefs in Mathematics. Springer International Publishing, Cham, 2016.http://link. springer.com/10.1007/978-3-319-33338-0

    work page doi:10.1007/978-3-319-33338-0 2016

  15. [15]

    Pironio, M

    S. Pironio, M. Navascués, and A. Acín. Convergent relaxations of polynomial optimization problems with noncommuting variables.SIAM J. Optim., 20(5):2157–2180, 2010

    2010

  16. [16]

    I. Klep, V. Magron, and J. Volčič. Complete upper bound hierarchies for spectral minimum in noncom- mutative polynomial optimization.Journal of Mathematical Analysis and Applications, 563(1), 2026

    2026

  17. [17]

    The sum-of-squares hierarchy on the sphere and applications in quantum information theory.Mathematical Programming, 190(1):331–360, November 2021

    Kun Fang and Hamza Fawzi. The sum-of-squares hierarchy on the sphere and applications in quantum information theory.Mathematical Programming, 190(1):331–360, November 2021

    2021

  18. [18]

    An effective version of Schmüdgen’s Positivstellensatz for the hypercube.Optimization Letters, 17(3):515–530, April 2023.https://doi.org/10.1007/ s11590-022-01922-5

    Monique Laurent and Lucas Slot. An effective version of Schmüdgen’s Positivstellensatz for the hypercube.Optimization Letters, 17(3):515–530, April 2023.https://doi.org/10.1007/ s11590-022-01922-5

    2023

  19. [19]

    Sum-of-squares hierarchies for binary polynomial optimiza- tion.Mathematical Programming, 197(2):621–660, February 2023.https://doi.org/10.1007/ s10107-021-01745-9

    Lucas Slot and Monique Laurent. Sum-of-squares hierarchies for binary polynomial optimiza- tion.Mathematical Programming, 197(2):621–660, February 2023.https://doi.org/10.1007/ s10107-021-01745-9

    2023

  20. [20]

    Sum-of-squares hierarchies for polynomial optimization and the Christoffel–Darboux kernel

    Lucas Slot. Sum-of-squares hierarchies for polynomial optimization and the Christoffel–Darboux kernel. SIAM Journal on Optimization, 32(4):2612–2635, 2022

    2022

  21. [21]

    An overview of convergence rates for sum of squares hierarchies in polynomial optimization

    Monique Laurent and Lucas Slot. An overview of convergence rates for sum of squares hierarchies in polynomial optimization. In Shin’ichi Oishi, Hisashi Okamoto, and Ken Hayami, editors,Recent Developments in Industrial and Applied Mathematics, pages 149–176, Singapore, 2026. Springer Nature Singapore

    2026

  22. [22]

    Approximation algorithms for quantum many-body problems.Journal of Mathematical Physics, 60(3):032203, March 2019.https: //doi.org/10.1063/1.5085428

    Sergey Bravyi, David Gosset, Robert König, and Kristan Temme. Approximation algorithms for quantum many-body problems.Journal of Mathematical Physics, 60(3):032203, March 2019.https: //doi.org/10.1063/1.5085428

    work page doi:10.1063/1.5085428 2019

  23. [23]

    Lasserre

    Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments.SIAM Journal on Optimization, 11(3):796–817, January 2001

    2001

  24. [24]

    Lasserre

    Jean B. Lasserre. A new look at nonnegativity on closed sets and polynomial optimization.SIAM Journal on Optimization, 21(3):864–885, 2011.https://doi.org/10.1137/100806990

    work page doi:10.1137/100806990 2011

  25. [25]

    Convergence analysis for lasserre’s measure-based hierarchy of upper bounds for polynomial optimization.Mathematical Programming, 162:363–392, 2017

    Etienne de Klerk, Monique Laurent, and Zhao Sun. Convergence analysis for lasserre’s measure-based hierarchy of upper bounds for polynomial optimization.Mathematical Programming, 162:363–392, 2017

    2017

  26. [26]

    V. I. Levenshtein. Universal bounds for codes and designs.Handbook of Coding Theory, 9:499–648, 1998. 19

    1998

  27. [27]

    MacWilliams and Neil J

    Florence J. MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes. Number 16 in North Holland Mathematical Library. North-Holland Publ. Comp, Amsterdam New York Oxford, 3. printing, 2. reprint edition, 1983

    1983

  28. [28]

    Ashley Montanaro and Tobias J. Osborne. Quantum boolean functions.Chicago Journal of Theoretical Computer Science, 2010(1), January 2010

    2010

  29. [29]

    Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube.Mathematics of Operations Research, 45(1):86–98, 2020

    Etienne de Klerk and Monique Laurent. Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube.Mathematics of Operations Research, 45(1):86–98, 2020. https://www.jstor.org/stable/27343309

    work page arXiv 2020

  30. [30]

    Relaxations and exact solutions to quantum max cut via the algebraic structure of swap operators.Quantum, 8:1352, 2024

    Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J William Helton, and Igor Klep. Relaxations and exact solutions to quantum max cut via the algebraic structure of swap operators.Quantum, 8:1352, 2024

    2024

  31. [31]

    Sparse noncommutative polynomial optimization.Mathe- matical Programming, 193(2):789–829, June 2022.https://doi.org/10.1007/s10107-020-01610-1

    Igor Klep, Victor Magron, and Janez Povh. Sparse noncommutative polynomial optimization.Mathe- matical Programming, 193(2):789–829, June 2022.https://doi.org/10.1007/s10107-020-01610-1

    work page doi:10.1007/s10107-020-01610-1 2022

  32. [32]

    Convergence rates for sums-of-squares hier- archies with correlative sparsity.Mathematical Programming, 209(1):435–473, 2025

    Milan Korda, Victor Magron, and Rodolfo Rios-Zertuche. Convergence rates for sums-of-squares hier- archies with correlative sparsity.Mathematical Programming, 209(1):435–473, 2025

    2025

  33. [33]

    S. T. Belinschi, V. Magron, and V. Vinnikov. Noncommutative Christoffel-Darboux Kernels.Transac- tions of the American Mathematical Society, 376(01):181–230, 2023

    2023

  34. [34]

    MIPco = coRE.http://arxiv.org/abs/2510.07162, 2025

    Junqiao Lin. MIPco = coRE.http://arxiv.org/abs/2510.07162, 2025. arXiv:2510.07162

    work page arXiv 2025

  35. [35]

    MIP* = RE.Commun

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE.Commun. ACM, 64(11):131–138, 2021. 20

    2021