Source-linked AI summary
A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding
Hoang Ta, Hoang Anh Tran
TL;DR
One-shot quantum-channel coding has computationally hard approximation aspects, while existing SDP bounds motivate stronger quantitative convergence guarantees. The paper constructs a Hermitian SOS hierarchy using state-discrimination duality and positive polynomial kernels, proving quadratic convergence with error proportional to advantage over random guessing. For binary messages, its bounds multiplicatively approximate the trace-norm contraction coefficient.
Problem
Approximating one-shot channel-coding success beyond a constant ratio is NP-hard when the message count is part of the input, motivating stronger quantitative SDP guarantees.
Source: §1 · pp. 1–2Method
The paper combines state-discrimination duality with a Hermitian SOS hierarchy, applying product squared-polynomial kernels to measurable positive dual slack fields.
Source: §1 · p. 2Results
The hierarchy has quadratic convergence with error proportional to advantage over random guessing, and its binary-message bounds multiplicatively approximate the trace-norm contraction coefficient.
Source: §1 · p. 2Takeaways & Limitations
An additive error ε is guaranteed at level L = O(dA/√ε), independently of dB, though SDP size still depends on dB.
Source: §1 · p. 2The reported computations use floating-point arithmetic, so repaired values are not certified by interval arithmetic.
Source: §5.2 · p. 21
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops a Hermitian SOS hierarchy for one-shot quantum-channel coding, addressing computational hardness and the limited convergence guarantees of an existing extension hierarchy. Its quadratic error bound scales with the advantage over random guessing, and its binary-message bounds approximate the trace-norm contraction coefficient multiplicatively.
1 Introduction
- Computing quantum-channel coding success remains NP-hard even for two messages, unlike classical binary coding, while the existing extension SDP requires a level choice tied to computational cost.The extension hierarchy’s matrices act on the input and multiple output copies; its convergence guarantee motivates stronger quantitative bounds.Source: §1 · p. 2
1.1 Technical overview
- The hierarchy restricts inputs to pure states, uses state-discrimination duality, and replaces pointwise positivity constraints with finite-degree SOS certificates.At each level, a finite-dimensional SDP gives a nonincreasing sequence of upper bounds on the optimal success probability.Source: §1 · p. 2, §1.1 · p. 3
1 Introduction
- The level-L error has quadratic convergence and is proportional to the advantage over random guessing; L = O(dA/√ε) suffices for additive error ε, independently of dB.The SDP size still depends on dB, and channels close to random guessing receive a stronger guarantee.Source: §1 · p. 2
- For binary messages, the relative error bound yields a multiplicative approximation of the trace-norm contraction coefficient.Every level is exact when ηtr(Φ) is 0 or 1.Source: §1 · pp. 2–3
1.1 Technical overview
- A product squared-polynomial kernel acts directly on measurable optimal dual slacks, producing polynomial SOS certificates without requiring the dual field to be polynomial or continuous.Because channel outputs share a mean and degree-two harmonic structure, an affine correction addresses the matrix constraints and trace bound together.Source: §1.1 · p. 3
1.2 Related work
- The contribution combines state-discrimination duality with kernels applied to bounded measurable positive slack fields, then uses shared output structure to correct the constraints simultaneously.The background situates this approach alongside prior SOS kernel convergence on spheres and SDP hierarchies for quantum communication.Source: §1.2 · pp. 4–5
2 Background
The background defines the one-shot coding problem and the mathematical tools used to build its hierarchy. It covers SOS positivity certificates on products of spheres and positive squared-kernel operators whose harmonic action supports the convergence analysis.
2.1 Basic notation
- The notation uses finite-dimensional operator spaces, with density operators defined as positive semidefinite Hermitian operators of trace one.A quantum channel is a completely positive, trace-preserving map.Source: §2.1 · p. 5
2.2 Problem statement
- For two messages, computing the quantum-channel coding success probability is NP-hard, and classical channels embedded in the quantum model also establish hardness when the message count is input.The optimal probability is an average over equiprobable messages; an existing extension hierarchy supplies convergent SDP upper bounds with an a priori error guarantee.Source: §2.2 · p. 6
2.3 Sum-of-squares certificates on products of spheres
- On products of spheres, scalar and Hermitian matrix SOS certificates provide semidefinite witnesses for pointwise nonnegativity, expressed modulo the sphere equations.The stated purpose is to replace pointwise positivity conditions in the hierarchy with semidefinite constraints.Source: §2.3 · pp. 7–8
2.4 Positive squared kernels on the sphere
- Positive squared-kernel operators preserve constants and scale degree-two harmonics by a common eigenvalue, the quantity governing the convergence error.The best attainable degree-two eigenvalue has a quadratic-in-level distortion bound, supported by a normalized monomial kernel choice.Source: §2.4 · pp. 10–11
3 The sum-of-squares hierarchy
The section builds a finite-dimensional SOS hierarchy for one-shot quantum channel coding by reducing the optimization to pure inputs, expressing them in real sphere coordinates, and replacing pointwise dual constraints with SOS certificates.
3.1 Reduction to pure input states
- Restricting each message's encoder state to a pure state leaves the joint optimum unchanged.For a fixed decoding POVM, each input state can be optimized independently and replaced by a pure state without decreasing the objective.Source: §3.1 · p. 11
3.2 Parametrization by real spheres
- Pure input vectors are represented by real points on a sphere, and the channel outputs become quadratic matrix polynomials in those coordinates.The global phase is immaterial because the output depends only on the input projector.Source: §3.2 · pp. 11–12
3.3 State-discrimination duality and an infinite optimization problem
- State-discrimination duality removes the decoding POVM exactly, leaving optimization over sphere-dependent output states and a dual matrix field.The pointwise dual value is the minimum trace of a matrix dominating each output state divided by k.Source: §3.3 · p. 12
3.4 The finite SOS hierarchy and its SDP representation
- Restricting the dual field to bounded-degree polynomials and certifying positivity with SOS constraints yields the finite hierarchy.The SOS constraints ensure valid upper bounds, while nested polynomial spaces and cones give monotonicity across levels.Source: §3.4 · pp. 13–14
- Each hierarchy level is a finite-dimensional SDP whose values are nonincreasing upper bounds on the optimal success probability.For fixed message count k and level L, the monomial dimension is (dA + L)O(kL).Source: §3.4 · pp. 13–14
4 Quadratic convergence
The paper proves quadratic convergence for the SOS hierarchy by smoothing positive dual slacks with polynomial kernels and correcting the channel constraints. In the binary case, the bounds also yield multiplicative approximations to the trace-norm contraction coefficient.
4.1 Kernel certificates and convergence
- The kernel's scaling of the degree-two output components is corrected using the outputs' shared mean and harmonic structure.The correction restores both the degree-two components and the common constant component of the constraints.Source: §4 · p. 15, §4.1 · pp. 16, 18
- Applying a positive squared-polynomial kernel to the positive matrix and scalar dual slacks yields finite-degree SOS certificates without approximating the generally nonsmooth optimal dual field.The construction uses a bounded Borel measurable optimal field and kernel representations that require neither continuity nor a strict positivity margin.Source: §4 · p. 15, §4.1 · pp. 17–18
- The hierarchy's error has quadratic level convergence, is proportional to the advantage Psucc(Φ, k) −1/k, and does not depend on output dimension dB.The endpoint success probabilities 1/k and 1 are exact at every level.Source: §4.1 · p. 19
4.2 Binary messages and trace-norm contraction
- For binary messages, the bounds give a multiplicative approximation to ηtr(Φ) with factor 1+ρ2dA,L, uniformly over positive values and exactly when ηtr(Φ)=0.When A=B, n successive channel applications contract trace distance by at most ηtr(Φ)^n.Source: §4.2 · pp. 19–20
5 Numerical experiments
The experiments compare SOS and extension SDP block orders at a guaranteed accuracy and test first-level binary-coding bounds on an exactly solvable benchmark and random qubit-to-qutrit channels. On the 40 sampled channels, repaired first-level SOS values are numerically tight relative to the reference values and lower than both computed extension values.
5 Numerical experiments
- The experiments compare the largest PSD block orders at a common guaranteed additive error and evaluate binary-message bounds on an exactly solvable channel and 40 random qubit-to-qutrit channels.The random sample contains 20 channels of Choi rank 6 and 20 of Choi rank 3; the same channels are used in all three formulations.Source: §5 · p. 20, §5.1 · p. 20, §5.2 · p. 21
5.1 SDP size at a prescribed accuracy
- The SOS block order is Θ(ε^-kdA), versus O(ε^-kdB(dB−1)) for symmetry-reduced extension and exponential growth in ε^-2 for direct extension when dB ≥2.These comparisons concern the largest PSD block and do not by themselves determine runtime.Source: §5.1 · p. 20
5.2 First-level bounds for binary channel coding
- For the exactly solvable benchmark, trace-norm contractivity gives ηtr(Φd) ≤1/(d−1), with equality attained by two distinct computational-basis states.For d=3, the extension formulations give ηtr(Φ3) ≤1/2, while the SOS construction supplies a feasible first-level certificate.Source: §5.2 · p. 21
- Mean extension gaps are 0.101499 without PPT and 0.101377 with PPT; repaired SOS values are lower in every instance by a minimum observed separation greater than 0.0164.The first-level gaps are measured relative to ηref; Figure 2 compares computed values with ηref and shows gaps by Choi rank.Source: §5.2 · p. 22, Table 2 · p. 22, Figure 2 · p. 22
- Repaired SOS values agree numerically with reference values throughout the sample, while the first extension level retains a visible gap with little improvement from PPT.The observations support numerical tightness on the sampled channels but do not establish exactness for all qubit-to-qutrit channels.Source: §5.2 · p. 22, Figure 2 · p. 22
Declaration of AI Usage
The authors led the research direction, hierarchy development, and convergence analysis. AI models assisted with exploring arguments and drafting, and the authors checked and substantially revised the generated material and take responsibility for the manuscript and results.
Declaration of AI Usage
- The authors led the research direction and development of the sum-of-squares hierarchy and its convergence analysis.They take full responsibility for the manuscript and the validity of its results.Source: Declaration of AI Usage · p. 23
- AI models assisted with exploring mathematical arguments, drafting intermediate proof sketches, and organizing and drafting parts of the exposition.The models named are ChatGPT 5.5 Pro and ChatGPT-5.6 Sol Pro.Source: Declaration of AI Usage · p. 23
- The authors carefully checked and substantially revised all AI-generated material.They state that they take full responsibility for the manuscript and the validity of its results.Source: Declaration of AI Usage · p. 23
A Hermitian matrix SOS cones and realification
The appendix establishes equivalence between the matrix SOS definition and a positive-semidefinite Gram representation, and gives the realification used in the SDP representation.
A Hermitian matrix SOS cones and realification
- A Hermitian matrix polynomial is SOS at level L exactly when there exists a positive-semidefinite Gram matrix satisfying the stated representation.The existence of such a Gram matrix is essential because the linear Gram map need not be injective.Source: A Hermitian matrix SOS cones and… · pp. 27–28
- Factoring a positive-semidefinite Gram matrix produces matrix SOS factors, while SOS factors yield a Gram matrix through their coefficient matrices.The equivalence uses factors whose entries lie in the span of the chosen polynomial basis.Source: A Hermitian matrix SOS cones and… · p. 27
- Realification preserves nonnegativity: a Hermitian matrix is nonnegative on complex vectors exactly when its realified matrix is nonnegative on real vectors.The real and imaginary parts of each complex vector give the corresponding real-vector representation.Source: A Hermitian matrix SOS cones and… · pp. 27–28
B Degree control in the product-sphere quotient
The appendix proves that the sphere equations generate the full vanishing ideal of the product of spheres and controls degrees when reducing polynomials modulo that ideal.
B Degree control in the product-sphere quotient
- A polynomial in the sphere ideal with degree at most 2L in each block admits a representation as a sum of sphere-equation multiples with controlled degrees.The quotient multipliers have degree at most 2L−2 in their corresponding block and at most 2L in the others.Source: B Degree control in the product-sphere… · p. 28
- The product-sphere ideal is the full vanishing ideal, so scalar and matrix polynomials agreeing on the product of spheres are congruent modulo the corresponding ideal.The stated result applies to real and complex scalar polynomials and to matrix polynomials.Source: B Degree control in the product-sphere… · pp. 28–29
- The proof uses blockwise harmonic decompositions to show that evaluation on the product of spheres is injective on the polynomial quotient.The restrictions of the selected basis polynomials are orthonormal, hence linearly independent, in the product-sphere L2 space.Source: B Degree control in the product-sphere… · p. 29
C Continuity and measurable selection
The appendix proves continuity of the optimal value and constructs Borel measurable selectors for optimal dual solutions. It uses compact feasible sets and measurable-selection results to obtain these properties.
Continuity
- The optimal value s is continuous because the POVM feasible set is nonempty and compact and the objective is jointly continuous.Berge’s maximum theorem is applied to the constant feasible-set correspondence.Source: C Continuity and measurable selection · p. 29
Measurable selection
- The dual-feasible correspondence F has nonempty compact values and a closed graph, which yields weak Borel measurability.The appendix derives weak measurability from the closed-graph property and compactness.Source: C Continuity and measurable selection · pp. 29–30
- A Borel measurable minimizer of Tr Y over F(x) is obtained using the measurable maximum theorem and bounds on optimal dual solutions.Restricting the dual feasible set to K preserves the optimal value, so the minimizer has trace s(x).Source: C Continuity and measurable selection · p. 30
- Alternatively, dual attainment and bounded optimal solutions make the optimal-solution correspondence nonempty, compact-valued, and closed-graph, allowing a Borel selector by the Kuratowski–Ryll-Nardzewski theorem.The selector satisfies the stated properties in (41).Source: C Continuity and measurable selection · p. 30
D The degree-two kernel constant
The appendix represents the degree-two kernel optimization with a finite matrix and establishes a dimension- and level-uniform quadratic-rate bound. It uses a kernel estimate for dimensions at least three and a Chebyshev argument for the circle.
Finite matrix representation
- The orthogonal-polynomial representation yields a real symmetric matrix T_D,L that is pentadiagonal because the kernel has degree two.The polynomial basis is orthonormal, and orthogonality makes matrix entries vanish when |r − s| > 2.Source: D The degree-two kernel constant · p. 30
Quadratic rate
- For D ≥3 and sufficiently large L relative to D, a degree-two kernel distortion estimate supplies a normalized polynomial used to establish the quadratic rate.The supplied passage specifies the threshold as L ≥ c′_0D.Source: D The degree-two kernel constant · p. 31
- For D = 2, the same rate follows from a direct argument using the Chebyshev basis and the largest zero of T_L+1.The argument uses Cauchy–Schwarz and a cosine bound for L ≥2.Source: D The degree-two kernel constant · pp. 31–32
- The convergence bound holds for every D ≥2 and L ≥1 with an absolute constant c1 independent of both parameters.The monomial choice extends the estimate to the remaining levels after enlarging c1 if necessary.Source: D The degree-two kernel constant · p. 32