Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians

• URL: http://arxiv.org/abs/2605.29959v1
• Date: Thu, 28 May 2026 14:01:21 GMT
• Title: Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians
• Abstract summary: We prove finite-level convergence rates for noncommutative sum-of-squares hierarchies in the Pauli setting.<n>These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.
• Score: 1.2249546377051437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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)ξ^{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.

Related papers

• How Deep Are Deep GPs, Really? A Sharp Threshold and a Non-Gaussian Limit for Compositional GPs [48.096969031315744]
  Previous work has established that for the RBF kernel and a certain range of bandwidths $r$, the prior degenerates in the limit.<n>We prove that for $r$ below the threshold $r_c(d)$ the prior converges to a limit distribution $_barZ$.
  arXiv  Detail & Related papers  (2026-06-06T15:12:43Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians [0.0]
  We give a hierarchy of SDP certificates for bounding the spectral gap of local qubit Hamiltonians from below.<n>We prove that the resulting certificates have size at fixed degree and convergeally (in fact, at level $n$)<n>We also give an example showing that for a commuting 1-local Hamiltonian, the hierarchy certifies a non lower bound on the spectral gap.
  arXiv  Detail & Related papers  (2025-10-09T16:42:21Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• LDPC stabilizer codes as gapped quantum phases: stability under graph-local perturbations [0.025206105035672277]
  We generalize the proof of stability of topological order, due to Bravyi, Hastings and Michalakis, to Hamiltonians corresponding to low-density parity check codes. We show that LDPC codes very generally define stable gapped quantum phases, even in the non-Euclidean setting.
  arXiv  Detail & Related papers  (2024-11-04T18:52:44Z)
• Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
  We show that solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP.<n>Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result.
  arXiv  Detail & Related papers  (2024-10-17T13:43:18Z)
• Upper bound hierarchies for noncommutative polynomial optimization [1.2249546377051437]
  This work focuses on minimizing the eigenvalue of a noncommutative to a finite number of noncommutative constraints.<n>We derive converging hierarchies of upper bounds due to Lasserre problem for minimizing compact sets.
  arXiv  Detail & Related papers  (2024-02-03T11:53:57Z)
• Analysis of sum-of-squares relaxations for the quantum rotor model [0.0]
  The noncommutative sum-of-squares hierarchy was introduced by Navascu'es-Pironio-Ac'i as a sequence of semidefinite programming relaxations for approximating quantum values of nonlocal games. Recent work has started to analyze the hierarchy for approximating ground energies of local Hamiltonians.
  arXiv  Detail & Related papers  (2023-11-15T14:53:22Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Quantum phase transitions mediated by clustered non-Hermitian degeneracies [0.0]
  A family of phase transitions in closed and open quantum systems is known to be mediated by a non-Hermitian degeneracy. In our paper the EP-mediated quantum phase transitions with $K>1$ are called "clustered" For the sake of maximal simplicity our attention is restricted to the real-harmonic-oscillator-type N by N matrix Hamiltonians.
  arXiv  Detail & Related papers  (2021-02-24T13:17:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.