Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Approximation algorithms for classical-quantum channel coding

Omar Fawzi, Johanna Seif, Dániel Szilágyi

Published Jul 1, 2019• 4 citations
Publisher

Abstract

We study the problem of finding the optimal code of size k for a given classical-quantum channel, with input space X and output space of dimension d, from an algorithmic point of view. We show that unlike the classical case, the relevant function is not submodular, and does not have the diminishing returns property. We also study a semidefinite programming relaxation, which corresponds to the setting where the sender and receiver have a non-signalling box, and show that it can be rounded in two different ways. If the SDP gives a value of p for the success probability, then a simple rounding strategy returns a code of size k with success probability at least p/O(log IXI log d). The second rounding method is p based on the pretty good measurement and returns a code with success probability close to p, but the code is smaller: it has size k · Ω(p2).

DOI
10.1109/isit.2019.8849617

Related papers

Algorithmic Aspects of Optimal Channel Coding

Siddharth Barman, Omar Fawzi

A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon, who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. The factor (1-e-1) can be improved arbitrarily close to 1 at the cost of slightly reducing the number of messages to be sent. Moreover, it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1) for the problem of computing the maximum success probability. 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most (1/(1 - e-1)). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.

arXiv:1508.04095•IEEE Transactions on Information Theory•Apr 24, 2017•22 citations

Quantum channel coding: Approximation algorithms and strong converse exponents

Aadil Oufkir, Mario Berta

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.

arXiv:2410.21124•Oct 28, 2024•0 citations

Quantum channel coding: Approximation algorithms and strong converse exponents

Aadil Oufkir, Mario Berta

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.

Quantum•Oct 6, 2025•2 citations

Algorithmic aspects of optimal channel coding

Siddharth Barman, Omar Fawzi

A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1). 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/1-e-1. In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•3 citations

Convergence Properties of Good Quantum Codes for Classical Communication

Alptug Aytekin, Mohamed Nomeir, Lei Hu +1 more

An important part of the information theory folklore had been about the output statistics of codes that achieve the capacity and how the empirical distributions compare to the output distributions induced by the optimal input in the channel capacity problem. Results for a variety of such empirical output distributions of good codes have been known in the literature, such as the comparison of the output distribution of the code to the optimal output distribution in vanishing and non-vanishing error probability cases. Motivated by these, we aim to achieve similar results for the quantum codes that are used for classical communication, that is the setting in which the classical messages are communicated through quantum codewords that pass through a noisy quantum channel. We first show the uniqueness of the optimal output distribution, to be able to talk more concretely about the optimal output distribution. Then, we extend the vanishing error probability results to the quantum case, by using techniques that are close in spirit to the classical case. We also extend non-vanishing error probability results to the quantum case on block codes, by using the second-order converses for such codes based on hypercontractivity results for the quantum generalized depolarizing semi-groups.

cs.ITCross-listedarXiv:2601.11498•IEEE International Symposium on Information Theory (ISIT)•Jan 19, 2026•1 citation

Semidefinite programming converse bounds for classical communication over quantum channels

Xin Wang, Wei Dong Xie, Runyao Duan

We study the classical communication over quantum channels when assisted by no-signalling (NS) and PPT-preserving (PPT) codes. We first show that both the optimal success probability of a given transmission rate and one-shot ϵ-error capacity can be formalized as semidefinite programs (SDPs) when assisted by NS or NS∩PPT codes. Based on this, we derive SDP finite blocklength converse bounds for general quantum channels, which also reduce to the converse bound of Polyanskiy, Poor, and Verdu for classical channels. Furthermore, we derive an SDP strong converse bound for the classical capacity of a general quantum channel: for any code with a rate exceeding this bound, the optimal success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bound, we derive improved upper bounds to the classical capacity of the amplitude damping channels and also establish the strong converse property for a new class of quantum channels.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•4 citations
We study the problem of finding the optimal code of size k for a given classical-quantum channel, with input space X and output space of dimension d, from an algorithmic point of view. We show that unlike the classical case, the relevant function is not submodular, and does not have the diminishing returns property. We also study a semidefinite programming relaxation, which corresponds to the setting where the sender and receiver have a non-signalling box, and show that it can be rounded in two different ways. If the SDP gives a value of p for the success probability, then a simple rounding strategy returns a code of size k with success probability at least p/O(log IXI log d). The second rounding method is p based on the pretty good measurement and returns a code with success probability close to p, but the code is smaller: it has size k · Ω(p2).
A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon, who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. The factor (1-e-1) can be improved arbitrarily close to 1 at the cost of slightly reducing the number of messages to be sent. Moreover, it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1) for the problem of computing the maximum success probability. 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most (1/(1 - e-1)). In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.
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)(1 - e^{-1})(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.
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.
A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1 - e-1)-approximation of the maximum success probability. Moreover, for this problem it is NP-hard to obtain an approximation ratio strictly better than (1 - e-1). 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most 1/1-e-1. In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú.
An important part of the information theory folklore had been about the output statistics of codes that achieve the capacity and how the empirical distributions compare to the output distributions induced by the optimal input in the channel capacity problem. Results for a variety of such empirical output distributions of good codes have been known in the literature, such as the comparison of the output distribution of the code to the optimal output distribution in vanishing and non-vanishing error probability cases. Motivated by these, we aim to achieve similar results for the quantum codes that are used for classical communication, that is the setting in which the classical messages are communicated through quantum codewords that pass through a noisy quantum channel. We first show the uniqueness of the optimal output distribution, to be able to talk more concretely about the optimal output distribution. Then, we extend the vanishing error probability results to the quantum case, by using techniques that are close in spirit to the classical case. We also extend non-vanishing error probability results to the quantum case on block codes, by using the second-order converses for such codes based on hypercontractivity results for the quantum generalized depolarizing semi-groups.
We study the classical communication over quantum channels when assisted by no-signalling (NS) and PPT-preserving (PPT) codes. We first show that both the optimal success probability of a given transmission rate and one-shot ϵ-error capacity can be formalized as semidefinite programs (SDPs) when assisted by NS or NS∩PPT codes. Based on this, we derive SDP finite blocklength converse bounds for general quantum channels, which also reduce to the converse bound of Polyanskiy, Poor, and Verdu for classical channels. Furthermore, we derive an SDP strong converse bound for the classical capacity of a general quantum channel: for any code with a rate exceeding this bound, the optimal success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bound, we derive improved upper bounds to the classical capacity of the amplitude damping channels and also establish the strong converse property for a new class of quantum channels.