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

Optimization Letters

Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity

Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun

Published Mar 21, 2026• 0 citations
Publisher

Abstract

In this paper, we study the discrete complex quadratic optimization problem, where the goal is to maximize a multivariate Hermitian quadratic objective function over complex m’th roots of unity. This problem is a generalization of the well-studied quadratic unconstrained binary optimization problem (QUBO), and has applications in signal processing, including in maximal likelihood estimation and multiple-input multiple-output detection, in addition to applications in statistical physics, in particular the computation of ground states of the Potts model. We study the sum-of-squares hierarchy for this problem, which is a sequence of semidefinite relaxations that is known to converge to the optimal solution after at most n steps. A previous result of Fawzi, Saunderson and Parrilo showed that in the the binary case ( $$m=2$$ ), at most $$\lceil n/2 \rceil $$ levels of the hierarchy are actually needed. In this paper we generalize this result and establish that the hierarchy converges after at most $$\lfloor n/2\rfloor +1$$ level for any $$m \ge 2$$ . Our proof generalizes the ideas used in the $$m=2$$ case, and is based on constructing chordal covers of appropriate Cayley graphs.

DOI
10.1007/s11590-026-02289-7

Related papers

A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding

Hoang Ta, Hoang Anh Tran

Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.

quant-pharXiv:2609.09629•Sep 10, 2026•0 citations

Exact algorithms for quadratic optimization over roots of unity

Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun

We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex $m$'th root of unity. Such problems have applications in signal processing, MIMO detection, and the computation of ground states in statistical physics, among others. Our contributions in this paper are twofold. We first study the convergence of the sum-of-squares hierarchy and prove its convergence to the exact solution after only $\lfloor n/2\rfloor+1$ levels (as opposed to $n$ levels). Our proof follows and generalizes the techniques and results used for the binary $m=2$ case developed by Fawzi, Saunderson, Parrilo. Second, we construct an integer binary reformulation of the problem based on zonotopes which reduces by half the number of binary variables in the simple reformulation. We show on numerical experiments that this reformulation can result in significant speedups (up to 10x) in solution time.

arXiv:2508.02006•Aug 4, 2025•0 citations

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

Ali Almasi, Dávid Bugár, Cambyse Rouzé +1 more

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.

quant-pharXiv:2606.04940•Jun 4, 2026•0 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

The sum-of-squares hierarchy on the sphere and applications in quantum information theory

Kun Fang, Hamza Fawzi

Abstract We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty and Wehner. Specifically, we show that the rate of convergence is no worse than $$O(d^2/\ell ^2)$$ O ( d 2 / ℓ 2 ) in the regime $$\ell = \Omega (d)$$ ℓ = Ω ( d ) where $$\ell $$ ℓ is the level of the hierarchy and d the dimension, solving a problem left open in the recent paper by de Klerk and Laurent ( arXiv:1904.08828 ). Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem. By exploiting the duality relation between sums of squares and the Doherty–Parrilo–Spedalieri hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascués, Owari and Plenio.

arXiv:1908.05155•Mathematical Programming•Jul 6, 2020•56 citations

Moment-Sos and Spectral Hierarchies for Polynomial Optimization on the Sphere and Quantum de Finetti Theorems

Alexander Taveira Blomenhofer, Monique Laurent

Abstract. We revisit the convergence analysis of two approximation hierarchies for polynomial optimization on the unit sphere. The first one is based on the moment-sos approach and gives semidefinite bounds for which Fang and Fawzi (2021) showed an analysis in [Formula: see text] for the [Formula: see text]th level bound, using the polynomial kernel method. The second hierarchy was recently proposed by Lovitz and Johnston (2023) and gives spectral bounds for which they show a convergence rate in [Formula: see text], using a quantum de Finetti theorem of Christandl et al. (2007) that applies to complex Hermitian matrices with a “double” symmetry. We investigate links between these approaches, in particular, via duality of moments and sums of squares. Our main results include showing that the spectral bounds cannot have a convergence rate better than [Formula: see text] and that they do not enjoy generic finite convergence. In addition, we propose alternative performance analyses that involve explicit constants depending on intrinsic parameters of the optimization problem. For this we develop a novel “banded” real de Finetti theorem that applies to real matrices with “double” symmetry. We also show how to use the polynomial kernel method to obtain a de Finetti type result in [Formula: see text] for real maximally symmetric matrices, improving an earlier result in [Formula: see text] of Doherty and Wehner (2012).

arXiv:2412.13191•SIAM Journal on Optimization•Feb 20, 2026•0 citations
In this paper, we study the discrete complex quadratic optimization problem, where the goal is to maximize a multivariate Hermitian quadratic objective function over complex m’th roots of unity. This problem is a generalization of the well-studied quadratic unconstrained binary optimization problem (QUBO), and has applications in signal processing, including in maximal likelihood estimation and multiple-input multiple-output detection, in addition to applications in statistical physics, in particular the computation of ground states of the Potts model. We study the sum-of-squares hierarchy for this problem, which is a sequence of semidefinite relaxations that is known to converge to the optimal solution after at most n steps. A previous result of Fawzi, Saunderson and Parrilo showed that in the the binary case ( m=2m=2m=2 ), at most ⌈n/2⌉\lceil n/2 \rceil ⌈n/2⌉ levels of the hierarchy are actually needed. In this paper we generalize this result and establish that the hierarchy converges after at most ⌊n/2⌋+1\lfloor n/2\rfloor +1⌊n/2⌋+1 level for any m≥2m \ge 2m≥2 . Our proof generalizes the ideas used in the m=2m=2m=2 case, and is based on constructing chordal covers of appropriate Cayley graphs.
Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.
We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex mmm'th root of unity. Such problems have applications in signal processing, MIMO detection, and the computation of ground states in statistical physics, among others. Our contributions in this paper are twofold. We first study the convergence of the sum-of-squares hierarchy and prove its convergence to the exact solution after only ⌊n/2⌋+1\lfloor n/2\rfloor+1⌊n/2⌋+1 levels (as opposed to nnn levels). Our proof follows and generalizes the techniques and results used for the binary m=2m=2m=2 case developed by Fawzi, Saunderson, Parrilo. Second, we construct an integer binary reformulation of the problem based on zonotopes which reduces by half the number of binary variables in the simple reformulation. We show on numerical experiments that this reformulation can result in significant speedups (up to 10x) in solution time.
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.
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.
Abstract We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty and Wehner. Specifically, we show that the rate of convergence is no worse than O(d2/ℓ2)O(d^2/\ell ^2)O(d2/ℓ2) O ( d 2 / ℓ 2 ) in the regime ℓ=Ω(d)\ell = \Omega (d)ℓ=Ω(d) ℓ = Ω ( d ) where ℓ\ell ℓ ℓ is the level of the hierarchy and d the dimension, solving a problem left open in the recent paper by de Klerk and Laurent ( arXiv:1904.08828 ). Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem. By exploiting the duality relation between sums of squares and the Doherty–Parrilo–Spedalieri hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascués, Owari and Plenio.
Abstract. We revisit the convergence analysis of two approximation hierarchies for polynomial optimization on the unit sphere. The first one is based on the moment-sos approach and gives semidefinite bounds for which Fang and Fawzi (2021) showed an analysis in [Formula: see text] for the [Formula: see text]th level bound, using the polynomial kernel method. The second hierarchy was recently proposed by Lovitz and Johnston (2023) and gives spectral bounds for which they show a convergence rate in [Formula: see text], using a quantum de Finetti theorem of Christandl et al. (2007) that applies to complex Hermitian matrices with a “double” symmetry. We investigate links between these approaches, in particular, via duality of moments and sums of squares. Our main results include showing that the spectral bounds cannot have a convergence rate better than [Formula: see text] and that they do not enjoy generic finite convergence. In addition, we propose alternative performance analyses that involve explicit constants depending on intrinsic parameters of the optimization problem. For this we develop a novel “banded” real de Finetti theorem that applies to real matrices with “double” symmetry. We also show how to use the polynomial kernel method to obtain a de Finetti type result in [Formula: see text] for real maximally symmetric matrices, improving an earlier result in [Formula: see text] of Doherty and Wehner (2012).