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

• URL: http://arxiv.org/abs/2606.04940v1
• Date: Wed, 03 Jun 2026 14:30:52 GMT
• Title: Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra
• Abstract summary: We develop explicit convergence rates for relaxations of noncommutative optimization problems generated from Pauli algebra.<n>Our result represents the first quantitative analysis of the rate of convergence for relaxations of noncommutative optimization problems.
• Score: 5.389800405902633
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Moment/Sum-of-Hermitian-Squares relaxations for noncommutative polynomial optimization problems have become an important tool for analyzing problems within quantum theory. Despite their widespread success, little is known about their rate of convergence and, consequently, their accuracy. In this work, we develop explicit convergence rates for relaxations of noncommutative polynomial optimization problems generated from the Pauli algebra -- covering applications to the ground state energy problem for n-qubit systems. In particular, we show that the rate of convergence can be bounded in terms of the smallest roots of a family of orthogonal polynomials known as Krawtchouk polynomials. Our result represents the first quantitative analysis of the rate of convergence for relaxations of noncommutative polynomial optimization problems.

Related papers

• Quantum estimates for classical polynomial optimization [0.0]
  The problem of finding bounds on tensors is both difficult and important given its applications to questions ranging from dynamical stability in complex landscapes to data analysis.<n>From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and largest eigenvalues of the coefficient corresponding to the given amount.<n>In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on Stricharts.
  arXiv  Detail & Related papers  (2026-07-28T08:34:11Z)
• Finite de Finetti for convex bodies and Polynomial Optimization [0.0]
  We prove a finite de Finetti representation theorem for general convex bodies.<n>Our strategy generalizes a quantitative monogamy-of-entanglement argument from quantum theory to arbitrary convex bodies.<n>As an application, we express the optimal GPT value of a two-player non-local game as an optimization problem.
  arXiv  Detail & Related papers  (2026-01-21T17:04:13Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  We prove upper bounds on the covering number of numerous sets in Euclidean space.<n>We illustrate the power of the result on three computational applications.
  arXiv  Detail & Related papers  (2023-11-09T03:06:59Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Globally Optimal Quantum Control [1.979158763744267]
  We present Quantum Control via Polynomial Optimization (QCPOP), a method that eliminates a problem by directly finding globally optimal solutions.<n>The resulting increase in speed in which can be a thousandfold or more makes it possible to solve problems that were previously intractable.
  arXiv  Detail & Related papers  (2022-09-13T07:41:40Z)
• Sum-of-Squares Relaxations for Information Theory and Variational Inference [0.0]
  We consider extensions of the Shannon relative entropy, referred to as $f$-divergences. We derive a sequence of convex relaxations for computing these divergences. We provide more efficient relaxations based on spectral information divergences from quantum information theory.
  arXiv  Detail & Related papers  (2022-06-27T13:22:40Z)
• On constant-time quantum annealing and guaranteed approximations for graph optimization problems [0.0]
  Quantum Annealing (QA) is a computational framework where a quantum system's continuous evolution is used to find the global minimum of an objective function. In this paper we use a technique borrowed from theoretical physics, the Lieb-Robinson (LR) bound, and develop new tools proving that short, constant time quantum annealing guarantees constant factor approximations ratios. Our results are of similar flavor to the well-known ones obtained in the different but related QAOA (quantum optimization algorithms) framework.
  arXiv  Detail & Related papers  (2022-02-03T15:23:18Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization [25.680334940504405]
  This paper establishes the convergence of the rate of a non-smooth subient method with momentum for constrained problems. For problems, we show how the unconstrained case can be analyzed under weaker assumptions than the state-of-the-art.
  arXiv  Detail & Related papers  (2020-02-13T12:10:17Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.