Quantum channel coding: Approximation algorithms and strong converse exponents

Aadil Oufkir; Mario Berta

doi:10.22331/q-2025-10-06-1877

Quantum channel coding: Approximation algorithms and strong converse exponents

¹The UM6P Vanguard Center, Mohammed VI Polytechnic University, Rocade Rabat-Salé, Technopolis, Morocco
²Institute for Quantum Information, RWTH Aachen University, Aachen, Germany

Published:	2025-10-06, volume 9, page 1877
Editor:	Paul Erker
Eprint:	arXiv:2410.21124v2
Doi:	https://doi.org/10.22331/q-2025-10-06-1877
Citation:	Quantum 9, 1877 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We study relaxations of entanglement-assisted quantum channel coding and establish that non-signaling assistance and a natural semi-definite programming relaxation — termed meta-converse — are equivalent in terms of success probabilities. We then present a rounding procedure that transforms any non-signaling-assisted strategy into an entanglement-assisted one and prove an approximation ratio of $(1 – e^{-1})$ in success probabilities for the special case of measurement channels. For fully quantum channels, we give a weaker (dimension dependent) approximation ratio, that is nevertheless still tight to characterize the strong converse exponent of entanglement-assisted channel coding [Li and Yao, IEEE Tran. Inf. Theory (2024)]. Our derivations leverage ideas from position-based coding, quantum decoupling theorems, the matrix Chernoff inequality, and input flattening techniques.

► BibTeX data

@article{Oufkir2025quantumchannel,
  doi = {10.22331/q-2025-10-06-1877},
  url = {https://doi.org/10.22331/q-2025-10-06-1877},
  title = {Quantum channel coding: {A}pproximation algorithms and strong converse exponents},
  author = {Oufkir, Aadil and Berta, Mario},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1877},
  month = oct,
  year = {2025}
}

► References

[1] Anurag Anshu, Rahul Jain, and Naqueeb Ahmad Warsi, ``Building Blocks for Communication Over Noisy Quantum Networks'' IEEE Trans. Inf. Theory 65, 1287-1306 (2018).
https://doi.org/10.1109/TIT.2018.2851297

[2] Suguru Arimoto ``On the converse to the coding theorem for discrete memoryless channels'' IEEE Transactions on Information Theory 19, 357–359 (1973).
https://doi.org/10.1109/TIT.1973.1055007

[3] Siddharth Barmanand Omar Fawzi ``Algorithmic Aspects of Optimal Channel Coding'' IEEE Transactions on Information Theory 64, 1038–1045 (2017).
https://doi.org/10.1109/TIT.2017.2696963

[4] Salman Beigiand Marco Tomamichel ``Lower Bounds on Error Exponents via a New Quantum Decoder'' ArXiv preprint arXiv:2310.09014 (2023).
https://doi.org/10.48550/arxiv.2310.09014

[5] Charles H. Bennett, Peter W. Shor, John A. Smolin, and Ashish V. Thapliyal, ``Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem'' IEEE Transactions on Information Theory 48, 2637–2655 (2002).
https://doi.org/10.1109/TIT.2002.802612

[6] Charles H. Bennett, Peter W. Shor, John A. Smolin, and Ashish V. Thapliyal, ``Entanglement-Assisted Classical Capacity of Noisy Quantum Channels'' Physical Review Letters 83, 3081–3084 (1999).
https://doi.org/10.1103/PhysRevLett.83.3081

[7] Mario Berta, Francesco Borderi, Omar Fawzi, and Volkher B. Scholz, ``Semidefinite programming hierarchies for constrained bilinear optimization'' Mathematical Programming 194, 781–829 (2022).
https://doi.org/10.1007/s10107-021-01650-1

[8] Mario Berta, Omar Fawzi, and Aadil Oufkir, ``Optimality of meta-converse for channel simulation'' 2024 IEEE International Symposium on Information Theory (ISIT) 1209–1214.
https://doi.org/10.1109/ISIT57864.2024.10619187

[9] Mario Berta, Omar Fawzi, and Volkher B. Scholz, ``Quantum Bilinear Optimization'' SIAM Journal on Optimization (2016).
https://doi.org/10.1137/15M1037731

[10] Francesco Buscemiand Nilanjana Datta ``The Quantum Capacity of Channels With Arbitrarily Correlated Noise'' IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https://doi.org/10.1109/TIT.2009.2039166

[11] Hao-Chung Cheng, Min-Hsiu Hsieh, and Marco Tomamichel, ``Quantum Sphere-Packing Bounds With Polynomial Prefactors'' IEEE Transactions on Information Theory 65, 2872–2898 (2019).
https://doi.org/10.1109/TIT.2019.2891347

[12] Matthias Christandl, Robert König, and Renato Renner, ``Postselection technique for quantum channels with applications to quantum cryptography'' Physical review letters 102, 020504 (2009).
https://doi.org/10.1103/PhysRevLett.102.020504

[13] Imre Csiszárand János Körner ``Information Theory: Coding Theorems for Discrete Memoryless Systems'' Cambridge University Press (2011).
https://doi.org/10.1017/CBO9780511921889

[14] Marco Dalai ``Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels'' IEEE Transactions on Information Theory 59, 8027–8056 (2013).
https://doi.org/10.1109/TIT.2013.2283794

[15] Nilanjana Datta, Marco Tomamichel, and Mark M. Wilde, ``On the second-order asymptotics for entanglement-assisted communication'' Quantum Information Processing 15, 2569–2591 (2016).
https://doi.org/10.1007/s11128-016-1272-5

[16] I. Devetak ``The private classical capacity and quantum capacity of a quantum channel'' IEEE Transactions on Information Theory 51, 44–55 (2005).
https://doi.org/10.1109/TIT.2004.839515

[17] Kun Fang, Xin Wang, Marco Tomamichel, and Mario Berta, ``Quantum Channel Simulation and the Channel's Smooth Max-Information'' IEEE Transactions on Information Theory 66, 2129–2140 (2019).
https://doi.org/10.1109/TIT.2019.2943858

[18] Robert M. Fano ``Transmission of Information: A Statistical Theory of Communication'' MIT Press (1961).
https://mitpress.mit.edu/9780262561693/transmission-of-information

[19] Omar Fawziand Paul Fermé``Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance'' IEEE Transactions on Information Theory 70, 7563–7580 (2024).
https://doi.org/10.1109/TIT.2024.3410047

[20] Omar Fawziand Paul Fermé``Multiple-Access Channel Coding With Non-Signaling Correlations'' IEEE Transactions on Information Theory 70, 1693–1719 (2023).
https://doi.org/10.1109/TIT.2023.3301719

[21] Omar Fawzi, Johanna Seif, and Dániel Szilágyi, ``Approximation algorithms for classical-quantum channel coding'' IEEE.
https://doi.org/10.1109/ISIT.2019.8849617

[22] Manish K. Guptaand Mark M. Wilde ``Multiplicativity of Completely Bounded p-Norms Implies a Strong Converse for Entanglement-Assisted Capacity'' Communications in Mathematical Physics 334, 867–887 (2015).
https://doi.org/10.1007/s00220-014-2212-9

[23] Evgueni A. Haroutunian, Mariam E. Haroutunian, and Ashot N. Harutyunyan, ``Reliability Criteria in Information Theory and in Statistical Hypothesis Testing'' Foundations and Trends® in Communications and Information Theory 4, 97–263 (2008).
https://doi.org/10.1561/0100000008

[24] Masahito Hayashi ``Information Spectrum Approach to Second-Order Coding Rate in Channel Coding'' IEEE Transactions on Information Theory 55, 4947–4966 (2009).
https://doi.org/10.1109/TIT.2009.2030478

[25] Masahito Hayashi ``Optimal sequence of quantum measurements in the sense of Stein's lemma in quantum hypothesis testing'' Journal of Physics A: Mathematical and General 35, 10759 (2002).
https://doi.org/10.1088/0305-4470/35/50/307

[26] Masahito Hayashiand Hiroshi Nagaoka ``General formulas for capacity of classical-quantum channels'' IEEE Transactions on Information Theory 49, 1753–1768 (2003).
https://doi.org/10.1109/TIT.2003.813556

[27] Masahito Hayashiand Marco Tomamichel ``Correlation detection and an operational interpretation of the Rényi mutual information'' Journal of Mathematical Physics 57 (2016).
https://doi.org/10.1063/1.4964755

[28] Alexander S. Holevo ``Information capacity of a quantum observable'' Problems of Information Transmission 48, 1–10 (2012).
https://doi.org/10.1134/S0032946012010012

[29] Alexander S. Holevo ``The capacity of the quantum channel with general signal states'' IEEE Transactions on Information Theory 44, 269–273 (1998).
https://doi.org/10.1109/18.651037

[30] Min-Hsiu Hsieh, Igor Devetak, and Andreas Winter, ``Entanglement-Assisted Capacity of Quantum Multiple-Access Channels'' IEEE Transactions on Information Theory 54, 3078–3090 (2008).
https://doi.org/10.1109/TIT.2008.924726

[31] Debbie Leungand William Matthews ``On the Power of PPT-Preserving and Non-Signalling Codes'' IEEE Transactions on Information Theory 61, 4486–4499 (2015).
https://doi.org/10.1109/TIT.2015.2439953

[32] Ke Liand Dong Yang ``Reliability Function of Classical-Quantum Channels'' ArXiv preprint arXiv:2407.12403 (2024).
https://doi.org/10.48550/arxiv.2407.12403

[33] Ke Liand Yongsheng Yao ``Strong Converse Exponent for Entanglement-Assisted Communication'' IEEE Transactions on Information Theory 70, 5017–5029 (2023).
https://doi.org/10.1109/TIT.2023.3335219

[34] Seth Lloyd ``Capacity of the noisy quantum channel'' Physical Review A 55, 1613–1622 (1997).
https://doi.org/10.1103/PhysRevA.55.1613

[35] William Matthews ``A Linear Program for the Finite Block Length Converse of Polyanskiy–Poor–VerdúVia Nonsignaling Codes'' IEEE Transactions on Information Theory 58, 7036–7044 (2012).
https://doi.org/10.1109/TIT.2012.2210695

[36] William Matthewsand Stephanie Wehner ``Finite Blocklength Converse Bounds for Quantum Channels'' IEEE Transactions on Information Theory 60, 7317–7329 (2014).
https://doi.org/10.1109/TIT.2014.2353614

[37] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel, ``On quantum Rényi entropies: a new generalization and some properties'' Journal of Mathematical Physics 54, 122203 (2013).
https://doi.org/10.1063/1.4838856

[38] Tomohiro Ogawaand Hiroshi Nagaoka ``Strong converse to the quantum channel coding theorem'' IEEE Transactions on Information Theory 45, 2486–2489 (2002).
https://doi.org/10.1109/18.796386

[39] Aadil Oufkir, Marco Tomamichel, and Mario Berta, ``Error exponent of activated non-signaling assisted classical-quantum channel coding'' arXiv preprint arXiv:2410.01084 (2024).
https://doi.org/10.48550/arxiv.2410.01084

[40] S. Pironio, M. Navascués, and A. Acín, ``Convergent Relaxations of Polynomial Optimization Problems with Noncommuting Variables'' SIAM Journal on Optimization (2010).
https://doi.org/10.1137/090760155

[41] Yury Polyanskiy, H. Vincent Poor, and Sergio Verdu, ``Channel Coding Rate in the Finite Blocklength Regime'' IEEE Transactions on Information Theory 56, 2307–2359 (2010).
https://doi.org/10.1109/TIT.2010.2043769

[42] Yury Polyanskiyand Sergio Verdú ``Arimoto channel coding converse and Rényi divergence'' 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) 1327–1333.
https://doi.org/10.1109/ALLERTON.2010.5707067

[43] Haoyu Qi, Qingle Wang, and Mark M. Wilde, ``Applications of position-based coding to classical communication over quantum channels'' Journal of Physics A: Mathematical and Theoretical 51, 444002 (2018).
https://doi.org/10.1088/1751-8121/aae290

[44] Joseph M. Renes ``Tight lower bound on the error exponent of classical-quantum channels'' ArXiv preprint arXiv:2407.11118 (2024).
https://doi.org/10.48550/arxiv.2407.11118

[45] Benjamin Schumacherand Michael D. Westmoreland ``Sending classical information via noisy quantum channels'' Physical Review A 56, 131–138 (1997).
https://doi.org/10.1103/PhysRevA.56.131

[46] Claude E. Shannon ``A Mathematical Theory of Communication'' The Bell system technical journal 27, 379–423 (1948).
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

[47] Claude E. Shannon, Robert G. Gallager, and Elwyn R. Berlekamp, ``Lower bounds to error probability for coding on discrete memoryless channels. I'' Information and Control 10, 65–103 (1967).
https://doi.org/10.1016/S0019-9958(67)90052-6

[48] Peter W. Shor ``The quantum channel capacity and coherent information'' lecture notes, MSRI Workshop on Quantum Computation 5 (2002).

[49] Maurice Sion ``On general minimax theorems'' Pacific Journal of Mathematics (1958).
https://doi.org/10.2140/pjm.1958.8.171

[50] Volker Strassen ``Asymptotische Abschätzungen in Shannons Informationstheorie'' Transactions of the Third Prague Conference on Information Theory 689–723 (1962).

[51] Marco Tomamichel ``Quantum Information Processing with Finite Resources'' Springer International Publishing (2016).
https://link.springer.com/book/10.1007/978-3-319-21891-5

[52] Marco Tomamicheland Vincent Y. F. Tan ``Second-Order Asymptotics for the Classical Capacity of Image-Additive Quantum Channels'' Communications in Mathematical Physics 338, 103–137 (2015).
https://doi.org/10.1007/s00220-015-2382-0

[53] Joel A. Tropp ``An Introduction to Matrix Concentration Inequalities'' Foundations and Trends® in Machine Learning 8, 1–230 (2015).
https://doi.org/10.1561/2200000048

[54] Ligong Wangand Renato Renner ``One-shot classical-quantum capacity and hypothesis testing'' Physical Review Letters 108, 200501 (2012).
https://doi.org/10.1103/PhysRevLett.108.200501

[55] Xin Wang, Kun Fang, and Marco Tomamichel, ``On Converse Bounds for Classical Communication Over Quantum Channels'' IEEE Transactions on Information Theory 65, 4609–4619 (2019).
https://doi.org/10.1109/TIT.2019.2898656

[56] Mark M. Wilde ``Quantum information theory'' Cambridge university press (2013).
https://doi.org/10.1017/CBO9781139525343

[57] Mark M. Wilde ``Sequential decoding of a general classical-quantum channel'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469 (2013).
https://doi.org/10.1098/rspa.2013.0259

[58] Mark M. Wilde, Andreas Winter, and Dong Yang, ``Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Rényi relative entropy'' Communications in Mathematical Physics 331, 593–622 (2014).
https://doi.org/10.1007/s00220-014-2122-x

[59] Andreas Winter ``Coding theorem and strong converse for quantum channels'' IEEE Transactions on Information Theory 45, 2481–2485 (2002).
https://doi.org/10.1109/18.796385

Cited by

[1] Aadil Oufkir, Marco Tomamichel, and Mario Berta, "Error exponent of activated non-signaling-assisted classical-quantum channel coding", Letters in Mathematical Physics 116 2, 33 (2026).

[2] Hao-Chung Cheng and Po-Chieh Liu, "Error Exponents for Quantum Packing Problems via An Operator Layer Cake Theorem", arXiv:2507.06232, (2025).

[3] Idris Delsol, Omar Fawzi, Jan Kochanowski, and Akshay Ramachandran, "Computational aspects of the trace norm contraction coefficient", arXiv:2507.16737, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 05:14:35) and SAO/NASA ADS (last updated successfully 2026-08-08 13:20:46). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-09 05:14:35: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.