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

arXiv:2609.09629

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

Hoang Ta, Hoang Anh Tran

quant-phcs.ITmath.OCSubmitted Sep 9, 2026• Announced Sep 10, 2026• 0 citations
v1 · Sep 9, 2026v2 · Sep 29, 2026
arXivHTMLPDF

Abstract

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.

Related papers

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

Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun

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.

Optimization Letters•Mar 21, 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

Semidefinite programming hierarchies for constrained bilinear optimization

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

Abstract We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $${\mathrm {Tr}}\big [H(D\otimes E)\big ]$$ Tr [ H ( D ⊗ E ) ] , maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our sum-of-squares hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo’s asymptotic de Finetti theorem for quantum channels. Finally, our proof methods answer a question of Brandão and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC’12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from $$O(d^{k/2})$$ O ( d k / 2 ) to $${\mathrm {poly}}(d,k)$$ poly ( d , k ) , where d denotes local dimension and k the number of copies.

arXiv:1810.12197•Mathematical Programming•Apr 15, 2021•32 citations

Semidefinite programming hierarchies for quantum error correction

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}\big[M(X\otimes Y)\big]$, maximized with respect to semidefinite constraints on $X$ and $Y$. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from $O(d^{k/2})$ to $\mathrm{poly}(d,k)$, where $d$ denotes local dimension and $k$ the number of copies.

•Jan 23, 2019•5 citations

Quantum Coding via Semidefinite Programming

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

We derive converging hierarchies of efficiently computable semidefinite programming outer bounds on the optimal fidelity for the transmission of quantum information over noisy quantum channels. Based on positive partial transpose conditions we give a sufficient criterion for the exact convergence at any given level of the hierarchies. The worst case convergence speed of our hierarchies is quantified via positive semidefinite representable outer approximations on the set of separable Choi states, which are based on novel finite de Finetti theorems for quantum channels.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•1 citation

SDP bounds on quantum codes

Gerard Anglès Munné, Andrew Nemec, Felix Huber

This paper provides a semidefinite programming hierarchy based on state polynomial optimization to determine the existence of quantum codes with given parameters. The hierarchy is complete, in the sense that a $(\!(n, K, δ)\!)_2$ code exists if and only if every level of the hierarchy is feasible. It is not limited to stabilizer codes and thus is applicable generally. While the machinery is formally dimension-free, we restrict it to qubit codes through quasi-Clifford algebras. We derive the quantum analog of a range of classical results: first, from an intermediate level a Lovász bound for self-dual quantum codes is recovered. Second, a symmetrization of a minor variation of this Lovász bound recovers the quantum Delsarte bound. Third, a symmetry reduction using the Terwilliger algebra leads to semidefinite programming bounds of size $O(n^4)$. With this we give an alternative proof that there is no $(\!(7, 1, 4)\!)_2$ quantum code, and show that $(\!(8, 9, 3)\!)_2$ and $(\!(10, 5, 4)\!)_2$ codes do not exist.

arXiv:2408.10323•Aug 19, 2024•0 citations
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.
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.
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 give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D⊗E)]{\mathrm {Tr}}\big [H(D\otimes E)\big ]Tr[H(D⊗E)] Tr [ H ( D ⊗ E ) ] , maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our sum-of-squares hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo’s asymptotic de Finetti theorem for quantum channels. Finally, our proof methods answer a question of Brandão and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC’12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2)O(d^{k/2})O(dk/2) O ( d k / 2 ) to poly(d,k){\mathrm {poly}}(d,k)poly(d,k) poly ( d , k ) , where d denotes local dimension and k the number of copies.
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[M(X⊗Y)]\mathrm{Tr}\big[M(X\otimes Y)\big]Tr[M(X⊗Y)], maximized with respect to semidefinite constraints on XXX and YYY. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2)O(d^{k/2})O(dk/2) to poly(d,k)\mathrm{poly}(d,k)poly(d,k), where ddd denotes local dimension and kkk the number of copies.
We derive converging hierarchies of efficiently computable semidefinite programming outer bounds on the optimal fidelity for the transmission of quantum information over noisy quantum channels. Based on positive partial transpose conditions we give a sufficient criterion for the exact convergence at any given level of the hierarchies. The worst case convergence speed of our hierarchies is quantified via positive semidefinite representable outer approximations on the set of separable Choi states, which are based on novel finite de Finetti theorems for quantum channels.
This paper provides a semidefinite programming hierarchy based on state polynomial optimization to determine the existence of quantum codes with given parameters. The hierarchy is complete, in the sense that a ( ⁣(n,K,δ) ⁣)2(\!(n, K, δ)\!)_2((n,K,δ))2​ code exists if and only if every level of the hierarchy is feasible. It is not limited to stabilizer codes and thus is applicable generally. While the machinery is formally dimension-free, we restrict it to qubit codes through quasi-Clifford algebras. We derive the quantum analog of a range of classical results: first, from an intermediate level a Lovász bound for self-dual quantum codes is recovered. Second, a symmetrization of a minor variation of this Lovász bound recovers the quantum Delsarte bound. Third, a symmetry reduction using the Terwilliger algebra leads to semidefinite programming bounds of size O(n4)O(n^4)O(n4). With this we give an alternative proof that there is no ( ⁣(7,1,4) ⁣)2(\!(7, 1, 4)\!)_2((7,1,4))2​ quantum code, and show that ( ⁣(8,9,3) ⁣)2(\!(8, 9, 3)\!)_2((8,9,3))2​ and ( ⁣(10,5,4) ⁣)2(\!(10, 5, 4)\!)_2((10,5,4))2​ codes do not exist.