Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity
Abstract
We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space K, we introduce a semidefinite programming parameter Γ(K) that is exactly multiplicative under tensor products and upper-bounds ΘNS(K), where log2ΘNS(K)=C0,NS(K) and C0,NS(K) denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on ΘNS given by semidefinite programs, Γ is the tightest. We also prove that the previously introduced simulation lower bound Σ−(K) is exactly multiplicative and satisfies ΘNS(K)≤Γ(K)≤Σ−(K)≤Γ(K)2. Using this multiplicativity, we show that neither S0,NS(K)=log2Σ−(K) nor its regularized extension S0,NS(K)=limn→∞n−1log2Σ−(K⊗ n) holds in general. This answers an open question about the asymptotic simulation cost S0,NS(K). For classical-quantum channels, we obtain sharp bounds. If r is the effective output dimension, then ΘNS≤Γ≤(1+r1/2)ΘNS/2 and Γ≤Σ−≤(1+r1/2)Γ/2. If k is the minimum rank of the output support projections, then Σ−/ΘNS≤[(1+r1/2)/(1+k1/2)]2, and this bound is sharp for every 1≤ k≤ r. Thus, we obtain the sharp bound S0,NS−C0,NS≤2log2[(1+r1/2)/(1+k1/2)].
Related
- Fast Randomized Entropically Regularized Semidefinite Programming
- Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- Inexact PDHG for Large-Scale Semidefinite Programming
- Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
BibTeX
@misc{li2026multiplicative,
title = {{Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity}},
author = {Xin Li and Yinan Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21071},
eprint = {2610.21071},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21071},
}
RIS
TY - UNPB
TI - Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity
AU - Xin Li
AU - Yinan Li
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21071
UR - https://arxiv.org/abs/2610.21071
AB - We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space K, we introduce a semidefinite programming parameter Γ(K) that is exactly multiplicative under tensor products and upper-bounds Θ_NS(K), where log_2Θ_NS(K)=C_0,NS(K) and C_0,NS(K) denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on Θ_NS given by semidefinite programs, Γ is the tightest. We also prove that the previously introduced simulation lower bound Σ^−(K) is exactly multiplicative and satisfies Θ_NS(K)≤Γ(K)≤Σ^−(K)≤Γ(K)^2. Using this multiplicativity, we show that neither S_0,NS(K)=log_2Σ^−(K) nor its regularized extension S_0,NS(K)=lim_n→∞n^−1log_2Σ^−(K^⊗ n) holds in general. This answers an open question about the asymptotic simulation cost S_0,NS(K). For classical-quantum channels, we obtain sharp bounds. If r is the effective output dimension, then Θ_NS≤Γ≤(1+r^1/2)Θ_NS/2 and Γ≤Σ^−≤(1+r^1/2)Γ/2. If k is the minimum rank of the output support projections, then Σ^−/Θ_NS≤[(1+r^1/2)/(1+k^1/2)]^2, and this bound is sharp for every 1≤ k≤ r. Thus, we obtain the sharp bound S_0,NS−C_0,NS≤2log_2[(1+r^1/2)/(1+k^1/2)].
ER -