Superadditivity of classical communication over quantum channels via random and deterministic permutations
Abstract
Since Hastings' proof of superadditivity of classical communication over quantum channels, considerable effort has been devoted to finding a structural explanation of this phenomenon that was originally established by concentration of measure for Haar random unitaries. The main observation of this work is that Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity. This replacement turns a continuous problem over unitary matrices into a discrete combinatorial problem over zero--one permutation matrices, and thereby opens a path toward derandomization. The theorem of Bordenave and Collins shows that random permutations have the required limiting behavior and the algorithm of O'Donnell and Wu then provides a deterministic asymptotic construction, running in polynomial time in the size when the channel parameters and accuracy are fixed. Thus the random construction can be derandomized in an asymptotic algorithmic sense. Finally, a quantitative random permutation estimate by Chen, Garza-Vargas, Tropp and van Handel gives a fully numerical estimate: there exists a tuple of 57,836,025 permutations acting on a set of size N ≤ 5.422× 10116216 such that the associated finite dimensional channel exhibits nonadditivity. This enormous value remains an obstacle to a practical construction.
Related
- Classical communication over quantum channels: does entanglement help in nature?
- Explicit channels with unbounded gains in classical communication using entangled inputs
- Maximal Lehmer Codes for Permutations with Classical and Consecutive 321-Avoidance
- Commitment over Gaussian channels with deterministic identification codes
- Deterministic Identification over Additive Gaussian Channels
BibTeX
@misc{lovitz2026superadditivity,
title = {{Superadditivity of classical communication over quantum channels via random and deterministic permutations}},
author = {Benjamin Lovitz and Peixue Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.25961},
eprint = {2608.25961},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25961},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Superadditivity of classical communication over quantum channels via random and deterministic permutations
AU - Benjamin Lovitz
AU - Peixue Wu
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2608.25961
UR - https://arxiv.org/abs/2608.25961
AB - Since Hastings' proof of superadditivity of classical communication over quantum channels, considerable effort has been devoted to finding a structural explanation of this phenomenon that was originally established by concentration of measure for Haar random unitaries. The main observation of this work is that Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity. This replacement turns a continuous problem over unitary matrices into a discrete combinatorial problem over zero--one permutation matrices, and thereby opens a path toward derandomization. The theorem of Bordenave and Collins shows that random permutations have the required limiting behavior and the algorithm of O'Donnell and Wu then provides a deterministic asymptotic construction, running in polynomial time in the size when the channel parameters and accuracy are fixed. Thus the random construction can be derandomized in an asymptotic algorithmic sense. Finally, a quantitative random permutation estimate by Chen, Garza-Vargas, Tropp and van Handel gives a fully numerical estimate: there exists a tuple of 57,836,025 permutations acting on a set of size N ≤ 5.422× 10^116216 such that the associated finite dimensional channel exhibits nonadditivity. This enormous value remains an obstacle to a practical construction.
ER -