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

arXiv:2609.09629 · quant-ph, cs.IT, math.IT, math.OC · Submitted 2026-09-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding".

Mira: Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages

DFKR25: .

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, moving on to the title and authors of "A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding," it immediately tells us they're focusing on a method that builds a hierarchy using sum-of-squares to achieve quadratic convergence.

Mira: Yes, the title is quite descriptive; it lays out exactly what the paper achieves: constructing a sum of squares hierarchy and proving quadratic convergence DFKR25. It signals that they are tackling the computational difficulty directly.

Lev: I find it interesting that they are specifically focusing on quantum channel coding in this context, which connects their work to practical communication problems rather than just abstract mathematical settings DFKR25.

Kai: They do tackle the NP-hard problem of finding the optimal success probability for transmitting classical messages through a single use of a quantum channel, even for two messages DFKR25. That’s a very challenging task to address.

Mira: Exactly, and they are contrasting this with existing methods that rely on symmetric extensions, which we know only give bounds that decay as the inverse square root of the extension level DFKR25.

Lev: It seems they are positioning their work as an improvement over those established semidefinite programming hierarchies by offering a potentially much faster convergence rate DFKR25.

Kai: The authors are clearly aiming to provide a new tool for bounding these success probabilities, moving beyond the existing tools available in the literature on quantum communication DFKR25.

Mira: Their goal is to introduce a framework where they can construct feasible polynomial dual certificates using state-discrimination duality and positive polynomial kernels, which is a novel combination DFKR25.

Lev: From a researcher's viewpoint, I see this as potentially providing more actionable tools for analyzing the performance of quantum codes because of the improved convergence guarantees DFKR25.

The paper's summary: Kai: In summary, the paper explains that they construct a Hermitian sum-of-squares hierarchy and prove quadratic convergence in its level L, which is a significant theoretical advancement for bounding success probabilities DFKR25.

Mira: They achieve this by combining state-discrimination duality with positive polynomial kernels on products of spheres to create feasible polynomial dual certificates

DFKR2609.09629#pg2: . This construction bypasses the usual non-polynomial constraints by using a specific kernel technique DFKR25.

Lev: They set up the core optimization problem as P succ(, k) = x in X s(x), where s(x) is defined via a minimization over Hermitian matrices Y subject to constraints Tr Y: Y sigma i(x)/k for all input states DFKR25.

Kai: They then handle the tricky part of replacing pointwise positivity constraints by finite-degree SOS certificates by applying that kernel directly to the slack matrices Y, which they claim allows the resulting polynomials to have degree at most 2L in each block

DFKR2609.09629#pg2: .

Mira: Furthermore, they correct for the common harmonic structure by using a product squared-polynomial kernel K q and adjusting constraints via an affine correction when lambda > zero which keeps the SOS level intact DFKR25.

Lev: That process of parametrizing pure states by real unit vectors and using these specific kernels seems like a rigorous way to translate the physical setup into a mathematical framework that is amenable to polynomial optimization techniques DFKR25.

Kai: The main result is that they establish quadratic convergence with an error proportional to the advantage over random guessing, which means zero at most U L(, k) - P succ(, k) at most 4c 1d 2A/L squared (P succ(, k) - one/k) DFKR25.

Mira: This convergence rate is what makes the paper significant; it’s a substantial improvement over the previously known inverse square root decay of existing SDP hierarchies DFKR25.

Lev: If this error bound holds, it means we have a much more reliable way to estimate how close we are to the true success probability when dealing with real-world quantum channels DFKR25.

The paper's improvements: Kai: The paper details several specific technical improvements they made in their methodology, starting with how they handle the non-polynomial constraints by using a product squared-polynomial kernel K q DFKR25.

Mira: That kernel is essential because it maps those fields to ambient polynomials of degree at most 2L in each block when integrated, which then allows for exact SOS representations

DFKR2609.09629#pg2: . So they solved the problem of non-polynomial constraints by turning them into polynomial ones DFKR25.

Lev: From a hardware perspective, this means that the mathematical machinery is robust enough to handle the complexity of representing input states using these real unit vectors and still produce a certificate at level L DFKR25.

Kai: Then they tackle the constraints by correcting them through their common harmonic structure, where all output fields share a spherical mean tau and satisfy sigma i(x) = tau + h(x i) DFKR25.

Mira: The affine correction, using an eigenvalue lambda = lambda two(q), compensates for changes in the constraints while preserving the SOS level DFKR25. It’s a necessary step to ensure that the certificate remains valid under these specific symmetry conditions DFKR25.

Lev: I wonder how complex this correction actually is when you try to implement it on a physical device; is it just a simple matrix multiplication, or does it introduce significant overhead DFKR25?

Kai: The paper addresses the limitations by explicitly stating that the dependence of the error bound on P succ(, k) - one/k also gives a stronger guarantee for channels whose coding performance is close to random guessing DFKR25.

Mira: That suggests a practical implication: if our channel performance is near-random, this specific bound becomes more informative about the required computational resources DFKR25.

Lev: It’s valuable information because it tells us when the approximation quality of our certificate is most or least reliable in terms of required computation DFKR25.

Conclusion: Kai: So, to wrap up "A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding," we've seen a method that achieves quadratic convergence and tight error bounds based on the advantage over random guessing DFKR25.

Mira: This work is important because it provides a constructive way to build polynomial dual certificates using SOS methods, which addresses the complexity of state-discrimination duality in quantum settings

DFKR2609.09629#pg2: .

Lev: I think for error correction, having a hierarchy where the error shrinks quadratically with the level sounds like it provides a very stable and predictable way to estimate how close we are to perfect transmission DFKR25.

Kai: For the experimentalist, the numerical experiments showing that even with PPT constraints, this method performs better than other methods at every level L

DFKR2609.09629#pg2: .

Mira: This confirms that this approach offers a robust way to estimate performance across different levels of approximation without relying on approximations in the polynomial space itself DFKR25.

Lev: The paper "A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding" gives us a rigorous tool to determine the success probability limits by providing convergence guarantees that are much faster than previous methods DFKR25.

Hoang Ta, Hoang Anh Tran

Hanoi University of Science and Technology · National University of Singapore

quant-ph, cs.IT, math.IT, math.OC

Submitted: 2026-09-09

Updated: 2026-09-29

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 88/100

The gist: Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages [DFKR25].

Key concepts

Sum-of-Squares Hierarchy
This is a mathematical structure used to build approximations. In this paper, it is constructed to achieve quadratic convergence when bounding the optimal success probability for transmitting classical messages through a quantum channel.
Quadratic Convergence
This refers to the rate at which the error in an approximation shrinks as more levels of the hierarchy are added. The authors prove that their method achieves this faster, quadratic convergence, compared to previous inverse square root decay rates.
Polynomial Dual Certificates
These are mathematical objects constructed using state-discrimination duality and positive polynomial kernels. They serve as a novel way to construct feasible certificates that bypass usual non-polynomial constraints in quantum settings.
State-Discrimination Duality
This is a technique used in the paper to combine with positive polynomial kernels. It is essential for constructing the feasible polynomial dual certificates required for bounding success probabilities in quantum channel coding.

Terminology

Summary

Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages [DFKR25]. 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 (SOS) hierarchy for arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing.

The 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: Defining EL(Φ):= 2UL(Φ, 2) − 1, we obtain ηtr(Φ) ≤ EL(Φ) ≤ 1 + 4c1d 2A/L 2!ηtr(Φ) (L ≥ 1).

The construction involves:

- Parametrizing pure input states by real unit vectors and using state-discrimination duality to obtain an exact infinite-dimensional formulation. The optimization over the decoding POVM is eliminated, leading to the problem:

"Psucc(Φ, k) = max x∈X s(x), s(x) = min Y ∈Herm(B)

Tr Y: Y ⪰ σi(x)/k for all i ∈ [k]."

- Replacing pointwise positivity constraints by finite-degree SOS certificates. The main obstacle is that a pointwise optimal dual field need not be polynomial, which is addressed by applying a product squared-polynomial kernel Kq directly to the positive matrix slacks Y

"If the real polynomial q has degree at most L, the kernel maps these fields to ambient polynomials of degree at most 2L in each block. Integrating their Gram coefficients yields finite positive semidefinite Gram matrices, so the resulting polynomials admit exact SOS representations."

- Correcting constraints through their common harmonic structure. All output fields have the same spherical mean τ and satisfy σi(x) = τ + h(xi), where h is a Hermitian matrix-valued spherical harmonic of degree two. The kernel fixes constant fields on X and multiplies each h(xi) by the same eigenvalue λ = λ2(q). For λ > 0, define YˆL = λ-1KqY

The affine correction compensates for this change while preserving the SOS level.

**- Establishing quadratic convergence. The main result establishes quadratic convergence with an error proportional to the advantage over random guessing: "There are absolute constant c1 > 0 such that, for every L ≥ 1, 0 ≤ UL(Φ, k) − Psucc(Φ, k) ≤ 4c1d 2A/L squared (Psucc(Φ, k) − 1/k). Consequently, the choice L = O(dA/√ε) guarantees an additive relaxation error of at most ε ∈ (0, 1). For binary messages, this relative error bound becomes a multiplicative approximation of the trace-norm contraction coefficient: ηtr(Φ) ≤ EL(Φ) ≤ 1 + 4c1d 2A/L 2!ηtr(Φ) (L ≥ 1). The paper also shows that every level L ≥ 1 is exact when ηtr(Φ) ∈ [0, 1]. The convergence rate is quantified in Theorem 4.5: For every L ≥ 1, we have Psucc(Φ, k) ≤ UL(Φ, k) ≤ min[1, Psucc(Φ, k) + ρ 2dA/L (Psucc(Φ, k) − 1/k)]. Finally, the error bound is shown to be independent of the output dimension dB: This dependence on Psucc(Φ, k) − 1/k also gives a stronger guarantee for channels whose coding performance is close to random guessing. The numerical experiments confirm that the first SOS level is numerically tight throughout the sample and improves on the first extension level, both with and without PPT constraints. The mean extension gaps are reported in Table 2: The repaired SOS value is smaller than both computed extension values in every instance, with a minimum observed separation greater than 0.0164. The gap relative to the reference value satisfies 0 ≤ Eˆ1 − ηref ≤ 4.10 × 10-7 across all 40 channels. (58) It is also noted that If Psucc(Φ, k) ∈ [1/k, 1], then UL(Φ, k) = Psucc(Φ, k) for every L ≥ 1." (Corollary 4.6).

Improvements for AI systems

Based on the provided scientific paper, here are specific improvements that can be made to AI systems by leveraging its theoretical framework:

The core contribution of this work is a constructive proof for a Hermitian Sum-of-Squares (SOS) hierarchy with quadratic convergence for computing the optimal success probability of transmitting classical messages through quantum channels. This framework provides rigorous, polynomial-time upper bounds on the performance of quantum communication systems that are significantly stronger than existing SDP hierarchies.

Here are specific improvements and capabilities:

  1. Improving Quantum Channel Coding Performance Estimation:

  2. Quantifying Communication Limits with High Precision:

  3. Developing Robust Decision-Making Under Uncertainty (Hypothesis Testing):

  4. Optimizing Quantum State Preparation for Transmission:

  5. Enhancing Robustness Against Channel Impairments (Using PPT Constraints):

  6. Improving Quantum Channel Coding Performance Estimation:

The paper provides a hierarchy of upper bounds, where the error decays quadratically with the level parameter (i.e., Level-L error is proportional to 1/L2).

  • An improved AI system can calculate the optimal success probability, denoted as an achievable upper bound, for transmitting classical messages over a quantum channel with guaranteed accuracy.

  • Specifically, for a fixed input dimension of the sender space and a desired additive relaxation error of at most ε (where ε is chosen based on the level L), the system can determine an encoding/decoding strategy that guarantees success probability within an additive gap of at most 4c1d2A/L2. This allows for highly precise performance prediction in complex quantum communication scenarios.

  1. Quantifying Communication Limits with High Precision:

The paper derives a multiplicative approximation for the trace-norm contraction coefficient (for binary messages) as well as a general bound on the success probability gap relative to random guessing.

  • An improved AI system can estimate the fundamental limits of quantum channel performance (the trace-norm contraction coefficient, ηtr), even when computing the exact value is NP-hard.

  • For binary channels, it can provide a multiplicative approximation of this coefficient with a known approximation factor (e.g., related to 1 + ρ2dA/L2). This allows for determining the achievable rate of reliable communication with quantifiable error margins, which is crucial for designing high-throughput quantum networks.

  1. Developing Robust Decision-Making Under Uncertainty (Hypothesis Testing):

The framework is deeply rooted in state-discrimination duality and hypothesis testing, linking channel performance to concepts like trace distance and contraction coefficients.

  • An improved AI system can perform optimal hypothesis testing on the output of a noisy quantum channel to distinguish between multiple classical messages with maximized success probability.

  • It can utilize the derived SDP hierarchy to determine if perfect transmission (or a near-perfect transmission, i.e., whether ηtr(Φ) = 1) is theoretically possible, which directly informs the feasibility of perfect quantum communication schemes.

  1. Optimizing Quantum State Preparation for Transmission:

The method involves parameterizing pure input states by real coordinates and using SOS certificates to relax the non-polynomial constraints of state discrimination duality.

  • An improved AI system can optimize the initial quantum input states (encoding) to maximize the success probability, given a fixed set of potential receiver measurements (POVM).

  • It can use this hierarchy to find near-optimal pure input states that are certified with high confidence (at level L), ensuring that the chosen encoding is robust against small perturbations in the channel or measurement apparatus.

  1. Enhancing Robustness Against Channel Impairments (Using PPT Constraints):

The paper explicitly compares SOS hierarchies with those including Positive Partial Transpose (PPT) constraints, showing that PPT constraints can lead to tighter bounds on SDP size and better performance for certain channels.

  • An improved AI system can evaluate the impact of applying PPT constraints during the optimization process.

  • It can select an encoding/decoding strategy that is specifically robust against noise characterized by partial transposition (e.g., in entanglement detection or quantum error correction protocols), as it identifies tighter, more computationally tractable certificates when these constraints are enforced.

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.

Sources

Related papers