Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians
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) ξ_{d+1}^{n,4} / n, where ξ_{d+1}^{n,4} is the smallest root of a Krawtchouk polynomial and C(k) is independent of n and d. General k-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit. 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.
Executive summary
This paper proves the first explicit finite-level convergence rates for noncommutative SoS / SDP hierarchies certifying ground-state energies of k-local Pauli Hamiltonians. Both the NPA-type lower-bound hierarchy and Lasserre-type upper-bound hierarchy converge with error ≤ C(k) ξ_{d+1}^{n,4} / n, where ξ_{d+1}^{n,4} is the smallest root of a Krawtchouk polynomial with parameter q=4. The proof is a noncommutative adaptation of the Christoffel–Darboux kernel method developed for commutative polynomial optimisation on the binary cube. For Yuan's Y5 programme — quantum / quantum-inspired Goemans-Williamson-style SDP relaxations via Pauli-sparse Gibbs states — this is a directly relevant theoretical foundation: it provides certificate rates for the SDP relaxations of the same Pauli-Hamiltonian class that Y5 attacks computationally.
Main contribution
For a k-local Pauli Hamiltonian H = Σ_{|S|≤k} H_S whose Pauli expansion only contains even-weight terms, the d-th level of the NPA lower-bound hierarchy ν_d(p) and Lasserre upper-bound hierarchy μ_d(p) satisfy λ_min(p) − ν_d(p) ≤ C(k) ξ_{d+1}^{n,4} / n and μ_d(p) − λ_min(p) ≤ C(k)/2 · ξ_{d+1}^{n,4} / n, where ξ is the smallest Krawtchouk root and C(k) < (2/3) k(k+2)(1+√2)^{2k+1} is independent of n,d. The even-weight assumption is non-restrictive: an arbitrary k-local Hamiltonian on n qubits embeds into an even-weight one on n+1 qubits with identical spectrum (Appendix A, generalising Bravyi 2019).
Key theorems / lemmas
- Theorem 1 (main, NPA lower-bound hierarchy): For Hermitian even-weight p of degree k with ‖p(σ)‖_∞ ≤ 1, if
(4k/3) · ξ_{d+1}^{n,4}/n ≤ 1/2, thenλ_min(p) − ν_d(p) ≤ C(k) ξ_{d+1}^{n,4} / n. - Theorem 2 (Lasserre upper-bound hierarchy): Under the same hypotheses,
μ_d(p) − λ_min(p) ≤ (C(k)/2) · ξ_{d+1}^{n,4} / n, unconditional in d. - Lemma (almost-reproducing kernel, properties P1–P3): Construct an invertible linear map K : ℂ⟨x⟩_{2d}/I → ℂ⟨x⟩_{2d}/I such that (P1) K1=1, (P2) K maps PSD polynomials into Σ_d⟨x⟩/I, (P3) ‖K⁻¹p − p‖_∞ ≤ ε for even-weight p of degree k with ‖p‖_∞ ≤ 1. The existence of such K yields the convergence rate via the lemma chain
λ_min(p) − ν_d(p) ≤ ε. - Even-weight reduction (Appendix A): Every k-local Hamiltonian on n qubits embeds into an even-weight Hamiltonian on n+1 qubits with identical spectrum, locality k′=k if k even, k′=k+1 if k odd. Extends Bravyi 2019 Lemma 1 (k=2) to general k.
- Asymptotic Krawtchouk root:
lim_{d/n→t} ξ_d^{n,q}/n = φ_q(t) = (q−1)/q − [(q−2)/q · t + (2/q)√((q−1)t(1−t))]; for q=4 this gives the orange dashed curve in Figure 1.
Detailed walkthrough
The k-local Hamiltonian problem — certifying λ_min(H) for H = Σ_{|S|≤k} H_S — is QMA-hard for k≥2, so tractable approximations are essential. SoS / SDP relaxations (NPA hierarchy and its noncommutative descendants) produce a sequence of relaxations whose values converge to λ_min as the relaxation level d grows. The classical results give finite convergence at d=n, but say nothing quantitative about practically computable low levels — exactly the regime that matters for any actual computation.
The paper imports the Christoffel–Darboux kernel toolbox developed for commutative polynomial optimisation (sphere: Fang–Fawzi 2021; binary cube: Slot 2023; ball/simplex: Slot 2024) into the noncommutative Pauli setting. The key construction is an invertible kernel K on the quotient algebra ℂ⟨x⟩/I that (P1) fixes the constant, (P2) maps PSD polynomials into sums-of-Hermitian-squares of degree at most 2d, and (P3) is approximately the identity on low-degree even Pauli polynomials with spectral-norm error ε. Lemma 3 then shows that the existence of such K immediately gives λ_min(p) − ν_d(p) ≤ ε via the chain K⁻¹(p − λ_min + ε) being PSD, then K-mapped back into the SoS cone.
The technical heart of the paper is constructing K and bounding ε. The natural starting point is the reproducing kernel of the normalised trace inner product on ℂ⟨x⟩/I; the authors perturb its homogeneous components to make the result positive while preserving near-reproducing behaviour on degree ≤ k even polynomials. After diagonalisation, the spectrum of the resulting kernel is governed by Krawtchouk polynomials with parameter q=4 (the q=4 reflects the four Pauli letters {I, X, Y, Z}). The error ε is then bounded by the smallest Krawtchouk root ξ_{d+1}^{n,4}/n, modulo a constant C(k) that captures the locality.
Section 1.1 states the two main theorems formally. Theorem 1 (the NPA lower-bound rate) requires a mild non-vanishing condition (4k/3) ξ_{d+1}^{n,4}/n ≤ 1/2 on the hierarchy level. Theorem 2 (the Lasserre upper-bound rate) is unconditional, with a constant of C(k)/2. Both are dimension-independent in the sense that C(k) does not depend on n or d. The asymptotic Krawtchouk-root formula (Cor. 5.21 of Levenshtein 1998 / Slot 2023 Thm. 34) is reproduced, giving the orange asymptotic curve φ_4(t) in Figure 1.
Section 1.2 sketches the proof strategy via the lemma chain on K. Section 1.3 gives the paper roadmap: §2 recalls Krawtchouk polynomials and the kernel formalism; §3 constructs homogeneous reproducing kernels for the Pauli algebra and diagonalises them; §4 proves Theorem 1; §5 proves Theorem 2; §6 discusses limitations and possible extensions to qudits, swap-operator formulations (Quantum Max Cut), and sparse hierarchies; Appendix A handles the even-weight reduction. The full paper is 20 pages with detailed kernel constructions and Krawtchouk-polynomial estimates filling the technical sections.
For numerical illustration, Figure 1 (in-source tikzpicture) plots the normalised smallest Krawtchouk root ξ_{d+1}^{40,4}/40 against the relaxation fraction d/n for a 40-qubit example, alongside the asymptotic limit φ_4(t) and the sufficient-condition thresholds 3/(4k) for k=2 and k=4 from Theorem 1. The plot shows the rate is meaningful (non-trivial bound) once d/n exceeds a modest threshold that depends on k.
Figures
No figures extracted from source. The paper's single figure (Figure 1) is an in-source tikzpicture rather than an external file, so it was not captured by the figure-extraction pass.
Citations to Yuan's papers
Overlap with Y1–Y6
- Y5 (GW speed-ups via Pauli-sparse Gibbs states): Strong methodological overlap. Y5 solves SDP relaxations of structured Goemans-Williamson problems through quantum / quantum-inspired Gibbs sampling exploiting Pauli sparsity. This paper proves convergence rates for the lower- and upper-bound SDP / SoS hierarchies on Pauli Hamiltonians. The two are complementary: Y5 gives a faster solver for SDP relaxations; this paper gives a quantitative certificate-quality bound for those relaxations. A Yuan follow-up combining "Pauli-sparse Gibbs solver + Krawtchouk-root certificate" would have both speed and accuracy guarantees.
- Y4 (Grover + ADMM for cardinality-constrained binary optimisation): Adjacent — Y4 uses semidefinite / ADMM structure on the classical side of its hybrid algorithm. The convergence-rate framework here could in principle be applied to bound the quality of any SDP relaxation appearing in cardinality-constrained settings.
Recommended action for Yuan
- Read carefully, especially the kernel-construction proof technique (§3, §4) and the even-weight reduction (Appendix A). If a future Y5 extension presents new SDP-relaxation algorithms, citing this paper's certificate rates would let you make precise accuracy claims rather than just "convergent".
- Reach out to Magron / Klep — there is genuine complementarity between Y5's Pauli-sparse Gibbs sampling and their certificate rates, and a co-authored note (or just an exchange) could clarify whether the rates here apply directly to the SDP relaxations Y5 solves.
- Cite in the related-work / theoretical-foundations section of any future Y5-line paper that mentions SDP / SoS relaxations of Pauli Hamiltonians.