A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding
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
- Quantum hypothesis testing of non-mixed-unitarity: A multifaceted hierarchy of quantum channel discrimination
- Anchored Regularized Direct Least Squares (ARDLS): Integrating Established Prioritization Operators for Priority Elicitation in the Analytic Hierarchy Process
- Perfect squares in reciprocal-sum sequences and primes that are inert in quadratic fields
- Convergence Rates for Lasserre's Upper-Bound Hierarchy on ℝd with Gaussian Measure
- Convergence of Least Squares Methods for PDEs on R^d with Shallow ReLU^k Networks
BibTeX
@misc{ta2026sumofsquares,
title = {{A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding}},
author = {Hoang Ta and Hoang Anh Tran},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09629},
eprint = {2609.09629},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09629},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding
AU - Hoang Ta
AU - Hoang Anh Tran
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.09629
UR - https://arxiv.org/abs/2609.09629
AB - 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.
ER -