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:2610.41858

Channel dichotomies

Aadil Oufkir, Mario Berta

cs.ITquant-phSubmitted Oct 30, 2026• Announced Nov 2, 2026• 0 citations
arXivHTMLPDF

Abstract

We study channel interconversion under non-signalling superchannels, where the asymptotic conversion rate is given by the ratio of the channel capacities. Our main result determines the second-order expansion of the optimal target length. Namely, when each channel has a single capacity-achieving dispersion, the coefficient is given by the inverse sesquinormal distribution, with parameters determined by the capacities and dispersions. The result extends state-dichotomy theory to channels: one superchannel approximates the target uniformly over inputs and maps every reference channel whose output is independent of its input to another such channel. As in state dichotomies, there are finite-error resonances where the second-order term vanishes, leaving an $O(\log n)$ remainder. Crucially, our new characterization cannot be obtained by concatenating channel coding and simulation protocols [Cao {\it et al.}~IEEE Trans.~Inf.~Theory (2024)]. Instead, the proof combines comparisons of binary hypothesis testing experiments with uniform Gaussian estimates and a construction that uses symmetry within type classes to satisfy the non-signalling constraints. Shared randomness assistance already suffices at first order, but we show that its second-order behaviour can differ strictly from the non-signalling case.

AI Summary

The paper studies how many uses of a finite classical target channel $W$ can be simulated from $n$ uses of a resource channel $T$, under non-signalling (NS) assistance and worst-input total-variation error $\epsilon$. It determines the fixed-error second-order correction to the capacity-ratio rate, rather than separately optimizing channel coding and simulation. When each channel has a single positive capacity-achieving dispersion, the optimal target length is $m^*_{\mathrm{NS}}=rn+(d_\epsilon/C_W)\sqrt n+O(\log n)$, where $r=C_T/C_W$ and $d_\epsilon=\inf_{\epsilon<\eta<1}\{\sqrt{V_T}\Phi^{-1}(\eta)-\sqrt{rV_W}\Phi^{-1}(\eta-\epsilon)\}$. This is the inverse sesquinormal profile known from state-dichotomy conversion. The limiting error at the capacity-ratio length vanishes when $V_T/C_T=V_W/C_W$; otherwise, a positive threshold error cancels the second-order term. A generalization treats nonunique positive dispersions through an optimization over resource Gaussian mixtures and target variances. The converse uses binary hypothesis-testing comparisons with uniform bounds covering correlated inputs and protocol-dependent reference distributions. Achievability combines type-class symmetrization with explicit completion of both NS marginals, paying $O(\log n)$ resource uses for auxiliary communication. Exact finite-blocklength formulas are also derived for additive channels and BEC-to-BSC conversion. Shared randomness attains the NS second-order profile for packet-erasure-to-bit-erasure conversion and BSC self-conversion, but a dispersion-matched BEC-to-BSC example exhibits a strict separation. General shared-randomness and entanglement-assisted characterizations remain open, as do general nonadditive zero-dispersion cases and third-order refinements.

Some signs of AI-generated textAI use disclosed
Based on previous tight second-order results for the interconversion of specific channels, the general characterization given here was developed with ChatGPT (5.6 Sol and 6 Astra).

Error found: The abstract states the singleton-dispersion characterization without the strictly positive capacities and dispersions required by the main theorem, while the paper does not establish the claimed generality for nonadditive zero-dispersion channels.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
34 pages, 4 figures

Related papers

New non-asymptotic random channel coding theorems

En‐hui Yang, Jin Meng

New non-asymptotic random coding theorems (with error probability ϵ and finite block length n) based on Gallager parity check ensemble are established for binary input arbitrary output channels. The resulting non-asymptotic achievability bounds, when combined with non-asymptotic equipartition properties, can be easily computed. Analytically, these non-asymptotic achievability bounds are shown to be asymptotically tight up to the second order of the coding rate as n goes to infinity with either constant or sub-exponentially decreasing ϵ. Numerically, they are also compared favourably, for finite n and ϵ of practical interest, with existing non-asymptotic achievability bounds in the literature in general.

arXiv:1303.0572•Information Theory and Applications Workshop (ITA)•Feb 1, 2013•1 citation

Identification without randomization

Rudolf Ahlswede, Ning Cai

In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.

IEEE Transactions on Information Theory•Jan 1, 1999•37 citations

Strong Converse Exponent of Channel Interconversion

Aadil Oufkir, Yongsheng Yao, Mario Berta

Abstract In their seminal work, Bennett et al. [1] showed that, with sufficient shared randomness, one noisy channel can simulate another at a rate equal to the ratio of their capacities. We establish that when coding above this channel interconversion capacity, the exact strong converse exponent is characterized by a simple optimization involving the difference of the corresponding Rényi channel capacities with Hölder dual parameters. We further extend this result to the entanglement-assisted interconversion of classical–quantum channels, showing that the strong converse exponent is likewise determined by differences of sandwiched Rényi channel capacities. The converse bound is obtained by relaxing to non-signaling assisted codes and applying Hölder duality together with the data processing inequality for Rényi divergences. Achievability is proven by concatenating refined channel coding and simulation protocols that go beyond first-order capacities, attaining an exponentially small conversion error, remaining robust under small variations in the input distribution, and tolerating a sublinear gap between the conversion rates.

arXiv:2509.15200•Annales Henri Poincaré•Sep 17, 2026•2 citations

ERROR PROBABILITY FOR A CHANNEL WITH TWO NON-ORTHOGONAL SIGNALS OF RANDOM PHASES

Elsevier eBooks•Jan 1, 1968•0 citations

One-Shot Multiple Access Channel Simulation

Aditya Nema, Sreejith Sreekumar, Mario Berta

We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs and characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel, featuring auxiliary random variables of bounded size. The achievability relies on a rejection-sampling algorithm to simulate an auxiliary channel between each sender and the decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments. To bound the cardinality of the auxiliary random variables, we employ the perturbation method from [Anantharamet al., IEEE Trans. Inf. Theory (2019)] in the one-shot setting. For the asymptotic setting and vanishing errors, our result expands to a tight single-letter rate characterization and consequently extends a special case of the simulation results of [Kurriet al., IEEE Trans. Inf. Theory (2022)] for fixed, independent and identically distributed (iid) product inputs to universal simulation for any product inputs. We broaden our discussion into the quantum realm by studying feedback simulation of quantum-to-classical (QC) MACs with product measurements [Atifet al., IEEE Trans. Inf. Theory (2022)]. For fixed product inputs and with shared randomness assistance, we give a quasi tight one-shot communication cost region with corresponding single-letter asymptotic iid expansion.

arXiv:2410.17198•IEEE Transactions on Information Theory•Jan 12, 2026•0 citations

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
We study channel interconversion under non-signalling superchannels, where the asymptotic conversion rate is given by the ratio of the channel capacities. Our main result determines the second-order expansion of the optimal target length. Namely, when each channel has a single capacity-achieving dispersion, the coefficient is given by the inverse sesquinormal distribution, with parameters determined by the capacities and dispersions. The result extends state-dichotomy theory to channels: one superchannel approximates the target uniformly over inputs and maps every reference channel whose output is independent of its input to another such channel. As in state dichotomies, there are finite-error resonances where the second-order term vanishes, leaving an O(log⁡n)O(\log n)O(logn) remainder. Crucially, our new characterization cannot be obtained by concatenating channel coding and simulation protocols [Cao {\it et al.}~IEEE Trans.~Inf.~Theory (2024)]. Instead, the proof combines comparisons of binary hypothesis testing experiments with uniform Gaussian estimates and a construction that uses symmetry within type classes to satisfy the non-signalling constraints. Shared randomness assistance already suffices at first order, but we show that its second-order behaviour can differ strictly from the non-signalling case.
The paper studies how many uses of a finite classical target channel WWW can be simulated from nnn uses of a resource channel TTT, under non-signalling (NS) assistance and worst-input total-variation error ϵ\epsilonϵ. It determines the fixed-error second-order correction to the capacity-ratio rate, rather than separately optimizing channel coding and simulation.
When each channel has a single positive capacity-achieving dispersion, the optimal target length is mNS∗=rn+(dϵ/CW)n+O(log⁡n)m^*_{\mathrm{NS}}=rn+(d_\epsilon/C_W)\sqrt n+O(\log n)mNS∗​=rn+(dϵ​/CW​)n​+O(logn), where r=CT/CWr=C_T/C_Wr=CT​/CW​ and dϵ=inf⁡ϵ<η<1{VTΦ−1(η)−rVWΦ−1(η−ϵ)}d_\epsilon=\inf_{\epsilon<\eta<1}\{\sqrt{V_T}\Phi^{-1}(\eta)-\sqrt{rV_W}\Phi^{-1}(\eta-\epsilon)\}dϵ​=infϵ<η<1​{VT​​Φ−1(η)−rVW​​Φ−1(η−ϵ)}. This is the inverse sesquinormal profile known from state-dichotomy conversion. The limiting error at the capacity-ratio length vanishes when VT/CT=VW/CWV_T/C_T=V_W/C_WVT​/CT​=VW​/CW​; otherwise, a positive threshold error cancels the second-order term. A generalization treats nonunique positive dispersions through an optimization over resource Gaussian mixtures and target variances.
The converse uses binary hypothesis-testing comparisons with uniform bounds covering correlated inputs and protocol-dependent reference distributions. Achievability combines type-class symmetrization with explicit completion of both NS marginals, paying O(log⁡n)O(\log n)O(logn) resource uses for auxiliary communication. Exact finite-blocklength formulas are also derived for additive channels and BEC-to-BSC conversion.
Shared randomness attains the NS second-order profile for packet-erasure-to-bit-erasure conversion and BSC self-conversion, but a dispersion-matched BEC-to-BSC example exhibits a strict separation. General shared-randomness and entanglement-assisted characterizations remain open, as do general nonadditive zero-dispersion cases and third-order refinements.
New non-asymptotic random coding theorems (with error probability ϵ and finite block length n) based on Gallager parity check ensemble are established for binary input arbitrary output channels. The resulting non-asymptotic achievability bounds, when combined with non-asymptotic equipartition properties, can be easily computed. Analytically, these non-asymptotic achievability bounds are shown to be asymptotically tight up to the second order of the coding rate as n goes to infinity with either constant or sub-exponentially decreasing ϵ. Numerically, they are also compared favourably, for finite n and ϵ of practical interest, with existing non-asymptotic achievability bounds in the literature in general.
In the theory of identification via noisy channels randomization in the encoding has a dramatic effect on the optimal code size, namely, it grows double-exponentially in the blocklength, whereas in the theory of transmission it has the familiar exponential growth. We consider now instead of the discrete memoryless channel (DMC) more robust channels such as the familiar compound (CC) and arbitrarily varying channels (AVC). They can be viewed as models for jamming situations. We make the pessimistic assumption that the jammer knows the input sequence before he acts. This forces communicators to use the maximal error concept and also makes randomization in the encoding superfluous. Now, for a DMC W by a simple observation, made by Ahlswede and Dueck (1989), in the absence of randomization the identification capacity, say C/sub NRI/(W), equals the logarithm of the number of different row-vectors in W. We generalize this to compound channels. A formidable problem arises if the DMC W is replaced by the AVC W. In fact, for 0-1-matrices only in W we are-exactly as for transmission-led to the equivalent zero-error-capacity of Shannon. But for general W the identification capacity C/sub NRI/(W) is quite different from the transmission capacity C(W). An observation is that the separation codes of Ahlswede (1989) are also relevant here. We present a lower bound on C/sub NRI/(W). It implies for instance for W={(/sub 0 1//sup 1 0/), (/sub /spl delta/ (1-/spl delta/)(1 0)/)}, /spl delta//spl isin/(0, 1/2 ) that C/sub NRI/(W)=1, which is obviously tight. It exceeds C(W), which is known to exceed 1-h(/spl delta/), where h is the binary entropy function. We observe that a separation code, with worst case average list size L~ (which we call an NRA code) can be partitioned into L~2/sup ne/ transmission codes. This gives a nonsingle-letter characterization of the capacity of AVC with maximal probability of error in terms of the capacity of codes with list decoding. We also prove that randomization in the decoding does not increase C/sub I/(W) and C/sub NRI/(W). Finally, we draw attention to related work on source coding.
Abstract In their seminal work, Bennett et al. [1] showed that, with sufficient shared randomness, one noisy channel can simulate another at a rate equal to the ratio of their capacities. We establish that when coding above this channel interconversion capacity, the exact strong converse exponent is characterized by a simple optimization involving the difference of the corresponding Rényi channel capacities with Hölder dual parameters. We further extend this result to the entanglement-assisted interconversion of classical–quantum channels, showing that the strong converse exponent is likewise determined by differences of sandwiched Rényi channel capacities. The converse bound is obtained by relaxing to non-signaling assisted codes and applying Hölder duality together with the data processing inequality for Rényi divergences. Achievability is proven by concatenating refined channel coding and simulation protocols that go beyond first-order capacities, attaining an exponentially small conversion error, remaining robust under small variations in the input distribution, and tolerating a sublinear gap between the conversion rates.
We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs and characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel, featuring auxiliary random variables of bounded size. The achievability relies on a rejection-sampling algorithm to simulate an auxiliary channel between each sender and the decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments. To bound the cardinality of the auxiliary random variables, we employ the perturbation method from [Anantharamet al., IEEE Trans. Inf. Theory (2019)] in the one-shot setting. For the asymptotic setting and vanishing errors, our result expands to a tight single-letter rate characterization and consequently extends a special case of the simulation results of [Kurriet al., IEEE Trans. Inf. Theory (2022)] for fixed, independent and identically distributed (iid) product inputs to universal simulation for any product inputs. We broaden our discussion into the quantum realm by studying feedback simulation of quantum-to-classical (QC) MACs with product measurements [Atifet al., IEEE Trans. Inf. Theory (2022)]. For fixed product inputs and with shared randomness assistance, we give a quasi tight one-shot communication cost region with corresponding single-letter asymptotic iid expansion.
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.