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

arXiv:2410.08140 · IEEE International Symposium on Information Theory (ISIT)

Optimality of Meta-Converse for Channel Simulation

Mario Berta, Omar Fawzi, Aadil Oufkir

Published Jul 7, 2024• 4 citations
arXivHTMLPDF

Abstract

We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy - which exactly corresponds to the meta-converse for channel simulation - to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. As our main result, we prove a guarantee on the ratio of success probabilities of at least$(1-\frac{-1}{\mathbf{e}})$, for both the classical and the quantum setting. We further - show this ratio to be optimal. It can be improved to$(1-\frac{1}{t})$using$o$(ln$(t)$) additional bits (qubits) of communication.

DOI
10.1109/isit57864.2024.10619187

Related papers

Exponents for Shared Randomness-Assisted Channel Simulation

Aadil Oufkir, Michael X. Cao, Hao–Chung Cheng +1 more

We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Namely, we find that these exponents can be written as simple optimizations over the R´enyi channel mutual information. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity. We derive our results by asymptotically expanding the meta-converse for channel simulation [Caoet al., IEEE Trans. Inf. Theory (2024)], which corresponds to nonsignaling assisted codes. We prove this to be asymptotically tight by employing the approximation algorithms from [Bertaet al., Proc. IEEE ISIT (2024)], which show how to round any non-signaling assisted strategy to a strategy that only uses shared randomness. Notably, this implies that any additional quantum entanglement-assistance does not change the error or the strong converse exponents.

IEEE Transactions on Information Theory•Feb 16, 2026•5 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•Quantum•Oct 6, 2025•3 citations

Zero-Error Channel Capacity and Simulation Assisted by Non-Local Correlations

Toby S. Cubitt, Debbie Leung, William Matthews +1 more

The theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. Finally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.

arXiv:1003.3195•IEEE Transactions on Information Theory•Aug 1, 2011•97 citations

Noisy Interactive Quantum Communication

Gilles Brassard, Ashwin Nayak, Alain Tapp +2 more

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.

Annual Symposium on Foundations of Computer Science•Oct 1, 2014•15 citations

Classical Communication Cost of a Bipartite Quantum Channel Assisted by Non-Signaling Correlations

Chengkai Zhu, Xuanqiang Zhao, Xin Wang

Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot $ε$-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.

arXiv:2408.02506•IEEE Transactions on Information Theory•May 9, 2025•1 citation

On Converse Bounds for Classical Communication Over Quantum Channels

Xin Wang, Kun Fang, Marco Tomamichel

We explore several new converse bounds for classical communication over quantum channels in both the one-shot and asymptotic regimes. First, we show that the Matthews-Wehner meta-converse bound for entanglementassisted classical communication can be achieved by activated, no-signaling assisted codes, suitably generalizing a result for classical channels. Second, we derive a new efficiently computable meta-converse on the amount of classical information unassisted codes can transmit over a single use of a quantum channel. As applications, we provide a finite resource analysis of classical communication over quantum erasure channels, including the second-order and moderate deviation asymptotics. Third, we explore the asymptotic analogue of our new meta-converse, the Υ-information of the channel. We show that its regularization is an upper bound on the classical capacity, which is generally tighter than the entanglement-assisted capacity and other known efficiently computable strong converse bounds. For covariant channels, we show that the Υ-information is a strong converse bound.

arXiv:1709.05258•IEEE Transactions on Information Theory•Feb 11, 2019•47 citations
We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy - which exactly corresponds to the meta-converse for channel simulation - to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. As our main result, we prove a guarantee on the ratio of success probabilities of at least(1−−1e)(1-\frac{-1}{\mathbf{e}})(1−e−1​), for both the classical and the quantum setting. We further - show this ratio to be optimal. It can be improved to(1−1t)(1-\frac{1}{t})(1−t1​)usingooo(ln(t)(t)(t)) additional bits (qubits) of communication.
We determine the exact error and strong converse exponents of shared randomness-assisted channel simulation in worst case total-variation distance. Namely, we find that these exponents can be written as simple optimizations over the R´enyi channel mutual information. Strikingly, and in stark contrast to channel coding, there are no critical rates, allowing a tight characterization for arbitrary rates below and above the simulation capacity. We derive our results by asymptotically expanding the meta-converse for channel simulation [Caoet al., IEEE Trans. Inf. Theory (2024)], which corresponds to nonsignaling assisted codes. We prove this to be asymptotically tight by employing the approximation algorithms from [Bertaet al., Proc. IEEE ISIT (2024)], which show how to round any non-signaling assisted strategy to a strategy that only uses shared randomness. Notably, this implies that any additional quantum entanglement-assistance does not change the error or the strong converse exponents.
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.
The theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. Finally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.
Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot εεε-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.
We explore several new converse bounds for classical communication over quantum channels in both the one-shot and asymptotic regimes. First, we show that the Matthews-Wehner meta-converse bound for entanglementassisted classical communication can be achieved by activated, no-signaling assisted codes, suitably generalizing a result for classical channels. Second, we derive a new efficiently computable meta-converse on the amount of classical information unassisted codes can transmit over a single use of a quantum channel. As applications, we provide a finite resource analysis of classical communication over quantum erasure channels, including the second-order and moderate deviation asymptotics. Third, we explore the asymptotic analogue of our new meta-converse, the Υ-information of the channel. We show that its regularization is an upper bound on the classical capacity, which is generally tighter than the entanglement-assisted capacity and other known efficiently computable strong converse bounds. For covariant channels, we show that the Υ-information is a strong converse bound.