betaFeedback

WorksComputer Science

Channel dichotomies

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)O(\log n) remainder. Crucially, our new characterization cannot be obtained by concatenating channel coding and simulation protocols [Cao 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.

Introduction

AI disclaimer. 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). The manuscript proposes a solution to an open problem in quantum information theory that we believe is of interest to the community. We also see an urgent need for a community discussion of appropriate formats for the communication of AI-generated scientific content.

Channel coding [1] uses a noisy channel to transmit messages reliably. Channel simulation [2, 3] uses noiseless communication to reproduce a noisy channel. Channel interconversion combines these two tasks [4, 23]. Given a resource channel TT and a target channel WW, we ask how many uses of WW can be simulated using nn uses of TT, at a prescribed error.

With unlimited shared randomness, a channel code for TT followed by a simulation protocol for WW achieves the first-order rate CT/CWC_T/C_W [1, 2, 3]. The reverse conversion has the reciprocal rate. Thus capacity determines reversibility at first order. At finite blocklength, however, optimizing coding and simulation separately need not give the best interconversion protocol. This approach first transmits information reliably and then adds noise. A direct protocol can instead use the noise already present in the resource. For example, a channel simulates itself exactly by direct use. The capacity ratio alone therefore does not determine the second-order correction.

Overview of main results

We characterize this correction under non-signalling superchannels. The assistance is a non-signalling channel N(x,z∣s,y)N(x,z\mid s,y), also called a non-signalling box. The sender supplies ss and receives xx. The receiver supplies yy and receives zz. The distribution of xx does not depend on yy, and the distribution of zz does not depend on ss. Connecting the resource channel to this box gives

ΘN[T](z∣s)=∑x,yT(y∣x)N(x,z∣s,y).\Theta_N[T](z\mid s)=\sum_{x,y}T(y\mid x)N(x,z\mid s,y).

Non-signalling correlations include those obtainable from shared randomness or shared entanglement. Their optimal performance therefore gives a converse bound for both assistance classes [4]. These correlations do not themselves transmit a message: all communication passes through the resource channel. Figure 1 shows the corresponding transformation. The sender’s resource input is chosen without access to the resource output. No feedback is supplied. We measure error by the maximum, over target input words, of the total variation distance between the simulated and target output laws. This ensures that the approximation holds for every target input, without assuming an input distribution.

Figure 1. A non-signalling superchannel. The upper box is one bipartite conditional distribution, not two local maps supplied with a shared classical variable. Its sender marginal is independent of yny^n, and its receiver marginal is independent of sms^m. Connecting its output xnx^n to its input yny^n through T⊗nT^{\otimes n} gives the simulated channel. The return wire is not feedback to the sender.

The general result allows all dispersions in [Vmin⁡(K),Vmax⁡(K)][V_{\min}(K),V_{\max}(K)], provided CK>0C_K>0 and Vmin⁡(K)>0V_{\min}(K)>0 for K=T,WK=T,W (Theorem A.1), but to keep the main text simple, we assume (the general result and its proof are given in Appendix § 5)

Vmin⁡(T)=Vmax⁡(T)=VT>0,Vmin⁡(W)=Vmax⁡(W)=VW>0.V_{\min}(T)=V_{\max}(T)=V_T>0,\qquad V_{\min}(W)=V_{\max}(W)=V_W>0.

This specialization includes nontrivial binary symmetric and binary erasure channels and does not require a unique capacity-achieving input. Let mNS∗(n,ϵ;T,W)m_{\mathrm{NS}}^*(n,\epsilon;T,W) be the largest target length attainable with error at most ϵ\epsilon.

Theorem 1.1 (Second-order channel interconversion). Under these assumptions, for every fixed 0<ϵ<10<\epsilon<1,

mNS∗(n,ϵ;T,W)=rn+dϵCWn+O(log⁡n),r=CTCW.(1)m_{\mathrm{NS}}^*(n,\epsilon;T,W)=rn+\frac{d_\epsilon}{C_W}\sqrt{n}+O(\log n),\qquad r=\frac{C_T}{C_W}. \tag*{(1)}

where the coefficient is the one-dimensional Gaussian optimization

dϵ=inf⁡ϵ<η<1{VTΦ−1(η)−rVWΦ−1(η−ϵ)}.(2)d_\epsilon=\inf_{\epsilon<\eta<1}\left\{\sqrt{V_T}\Phi^{-1}(\eta)-\sqrt{rV_W}\Phi^{-1}(\eta-\epsilon)\right\}. \tag*{(2)}

Here Φ\Phi is the standard normal distribution function.

Equivalently, the optimal rate is r+dε/(CWn)+O(log⁡n/n)r + d_{\varepsilon}/(C_{W}\sqrt{n}) + O(\log n/n). The capacities determine the first-order conversion rate. The two total information variances nVTnV_{T} and rnVWrnV_{W} determine the correction. The formula is a difference of Gaussian quantiles optimized over one parameter, rather than the sum of the separate coding and simulation penalties. Section 4 proves the theorem. Appendix D also gives an exact characterization for additive channels without a positive-dispersion assumption, including their zero-dispersion cases. General channels with Vmin⁡=0V_{\min}=0 are not covered by the Gaussian theorem.

Relation to state dichotomies

The comparison of statistical experiments goes back to Blackwell, Sherman, and Stein. Le Cam’s deficiency theory treats approximate comparison [10, 11, 12]. A classical state dichotomy is a binary experiment, specified by a pair of distributions (p,q)(p,q). Its conversion to (p′,q′)(p',q') asks for a stochastic map that approximates p′p' from pp while mapping qq to q′q' exactly. Renes’ relative submajorization theorem expresses its optimal error as a gap between testing curves [14]. The corresponding second-order conversion law is determined in [6]. For channels, the corresponding reference objects are the replacer channels RQ(y∣x)=Q(y)R_{Q}(y\mid x)=Q(y), which carry no information about their input. A single NS superchannel satisfies

ΘN[T]=W~≈W,ΘN[RQ]=RDNQfor every output law Q,(3)\begin{aligned} \Theta_{N}[T] &= \widetilde{W} \approx W,\\ \Theta_{N}[R_{Q}] &= R_{D_{N}Q} \quad\text{for every output law } Q, \tag*{(3)} \end{aligned}

where DN(z∣y)=∑xN(x,z∣s,y)D_{N}(z\mid y)=\sum_{x}N(x,z\mid s,y) is a single stochastic map fixed by the protocol. Thus the same transformation maps every input-independent channel to another input-independent channel, rather than preserving just one chosen reference. The output reference DNQD_{N}Q is determined by the protocol and is not prescribed independently. This also motivates the choice of NS assistance: among classical superchannels, these are precisely the transformations that preserve the family of channels carrying no information [5]. Section 2 proves this directly from the two marginal conditions.

For each target input law PSP_{S}, this channel transformation induces a stochastic map between the joint input–output experiments

(PX(x)T(y∣x),PX(x)Q(y))⟼(PS(s)W~(z∣s),PS(s)(DNQ)(z)),\bigl(P_{X}(x)T(y\mid x),P_{X}(x)Q(y)\bigr) \longmapsto \bigl(P_{S}(s)\widetilde{W}(z\mid s),P_{S}(s)(D_{N}Q)(z)\bigr),

with PXP_{X} induced by the sender marginal. The same induced map works for every QQ (Proposition 3.1). The channel problem therefore has two requirements. The approximation must hold for every target input, and the same protocol must map every replacer channel to another replacer channel. A transformation of one chosen binary experiment need not satisfy either condition.

The distinction is operational. A state map can generate the target input label itself and correlate it with the output. A channel protocol must instead respond to an input supplied from outside. For example, a map for one fixed pair can appear to create a noiseless bit from a channel with constant output, while violating the receiver NS condition (§ 3.2). Our construction enforces the channel constraints at logarithmic communication cost. This is the sense in which the theory of state dichotomies extends to channels. It does not give a one-shot equivalence with the conversion of a fixed pair. The NS conditions must still be imposed.

From binary experiments to universal channel protocols

Our starting point is the comparison of testing curves in [14 Theorem 2]. Information spectrum estimates and Gaussian limits then suggest the second-order profile [7, 8, 6]. To prove a channel theorem, we need a protocol attaining that profile and a converse valid for every allowed protocol. Classical comparison theory already treats whole families of distributions. The extra requirement here is that a transformation of joint input–output distributions must respect the separation between sender and receiver. In particular, it must respond to the target input rather than generate that input itself.

Converse. This is more standard and the state map induced by a channel protocol is due to Oufkir, Yao, and Berta [23 Lemma 24]. It works for every resource reference law, but the target reference is fixed by the protocol and cannot be chosen independently. Resource inputs may also be correlated. Appendix § 6 handles these choices using uniform type-class estimates, bounds on output distributions, and Markov’s inequality. Near capacity-achieving inputs, we use the quadratic decay of mutual information [27]. A central limit theorem for one fixed iid input would not justify optimization over all these choices.

Achievability. We use the method of types [30]. First, restrict the target inputs to one type class. Averaging over target coordinate permutations makes the target input label uniform on that class. This gives the sender marginal needed to turn the state map into a conditional distribution for a channel protocol. The same symmetry makes the error equal for every input in the class. Next, average independently over resource permutations. The receiver marginal is then constant on each output type class. A reference distribution that assigns equal mass to these classes bounds this marginal at every output, up to a polynomial factor. We then enforce the receiver NS condition. The construction extends the diagonal and off-diagonal completion used in NS simulation [3 Proposition 18], while retaining the noisy resource. When the auxiliary symbols agree, we use the desired conditional distribution. When they differ, we add a nonnegative correction. Both NS conditions then hold for every input to the box. A second auxiliary message identifies the target type. Its mismatched branches must also be completed so that the full protocol remains NS. Ordinary coding below capacity sends both auxiliary messages using O(log⁡n)O(\log n) of the prescribed resource uses, with error at most n−2n^{-2}. The total error is bounded by the largest typewise error plus the auxiliary coding error. There is no factor equal to the number of types. § 3.2 gives the NS channels. Proposition 3.3 accounts for their communication cost.

Finite-error resonance and short blocklengths

The limiting error at length m=⌈rn+(d/CW)n⌉m=\lceil rn+(d/C_W)\sqrt{n}\rceil is

E(d)=sup⁡ξ∈R{Φ(ξVT)−Φ(ξ−drVW)}.(4)\mathcal{E}(d)=\sup_{\xi\in\mathbb{R}}\left\{\Phi\left(\frac{\xi}{\sqrt{V_T}}\right)-\Phi\left(\frac{\xi-d}{\sqrt{rV_W}}\right)\right\}. \tag*{(4)}

This is the sesquinormal profile Sν(d/VT)S_\nu(d/\sqrt{V_T}) of [6 Lemma 1], with ν=rVW/VT\nu=rV_W/V_T. Here we show that this profile is also attainable by universal channel protocols. The coefficient in Theorem 1.1 is obtained by inverting this limiting error. In particular, define the threshold error

ϵ∗:=E(0)=∣Φ(xν)−Φ(xν/ν)∣,xν=νln⁡νν−1,ν=rVWVT.(5)\epsilon_*:=\mathcal{E}(0)=\left|\Phi(x_\nu)-\Phi(x_\nu/\sqrt{\nu})\right|,\qquad x_\nu=\sqrt{\frac{\nu\ln\nu}{\nu-1}},\qquad\nu=\frac{rV_W}{V_T}. \tag*{(5)}

with ϵ∗=0\epsilon_*=0 at ν=1\nu=1. If ν≠1\nu\ne1, then 0<ϵ∗<1/20<\epsilon_*<1/2 and

dϵ∗=0,mNS∗(n,ϵ∗;T,W)n=r+O(log⁡nn).(6)d_{\epsilon_*}=0,\qquad\frac{m_{\mathrm{NS}}^*(n,\epsilon_*;T,W)}{n}=r+O\left(\frac{\log n}{n}\right). \tag*{(6)}

Thus, at a fixed and possibly small error, the n−1/2n^{-1/2} rate correction vanishes and only higher-order terms remain. This is a threshold-error interpretation of finite-error resonance illustrated for state dichotomies in Figure 2 of [6]. Such a threshold exists for every pair with ν≠1\nu\ne1.

Figure 2. Threshold errors at the capacity ratio, analogous to Fig. 2 of [6]. (a) NS conversion from a BEC to a BSC. The SR curve is not known. (b) SR conversion from a two-bit packet-erasure channel to a BEC. Here the SR, EA, and NS limits coincide. At the orange points, the second-order coefficient at 1% error vanishes. It is nonnegative in the shaded intervals. At the blue zeros, the error at the capacity ratio tends to zero. These are limiting curves, not finite-blocklength error bounds.

Its size depends on the difference between the two ratios of dispersion to capacity. For ϵ<ϵ∗\epsilon< \epsilon_* the coefficient is negative, and for ϵ>ϵ∗\epsilon> \epsilon_* it is positive. The total information fluctuations match when

VTCT=VWCW.(7)\frac{V_T}{C_T} = \frac{V_W}{C_W}. \tag*{(7)}

In this case,

E(d)=[2Φ(d2VT)−1]+,dϵ=2VTΦ−1(1+ϵ2).(8)\mathcal{E}(d) = \left[2\Phi\left(\frac{d}{2\sqrt{V_T}}\right)-1\right]_+, \qquad d_\epsilon= 2\sqrt{V_T}\Phi^{-1}\left(\frac{1+\epsilon}{2}\right). \tag*{(8)}

Here the error at the capacity-ratio length tends to zero. This zero-threshold resonance is not restricted to identical channels. In this case, dϵ>0d_\epsilon> 0 at every fixed ϵ>0\epsilon> 0, so zero-threshold resonance is distinct from cancellation at a positive threshold error.

References

  1. [1]C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27, 379–423, 623–656 (1948).
  2. [2]C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem, IEEE Trans. Inf. Theory 48, 2637–2655 (2002). doi:10.1109/TIT.2002.802612.DOI
  3. [3]M. X. Cao, N. Ramakrishnan, M. Berta, and M. Tomamichel, Channel simulation: Finite blocklengths and broadcast channels, IEEE Trans. Inf. Theory 70, 6780–6808 (2024). doi:10.1109/TIT.2024.3445998.DOI
  4. [4]T. S. Cubitt, D. Leung, W. Matthews, and A. Winter, Zero-error channel capacity and simulation assisted by non-local correlations, IEEE Trans. Inf. Theory 57, 5509–5523 (2011). doi:10.1109/TIT.2011.2159047.DOI
  5. [5]R. Takagi, K. Wang, and M. Hayashi, Application of the resource theory of channels to communication scenarios, Phys. Rev. Lett. 124, 120502 (2020). doi:10.1103/PhysRevLett.124.120502.DOI
  6. [6]P. Lipka-Bartosik, C. T. Chubb, J. M. Renes, M. Tomamichel, and K. Korzekwa, Quantum dichotomies and coherent thermodynamics beyond first-order asymptotics, PRX Quantum 5, 020335 (2024). doi:10.1103/PRXQuantum.5.020335.
  7. [7]M. Hayashi, Information spectrum approach to second-order coding rate in channel coding, IEEE Trans. Inf. Theory 55, 4947–4966 (2009). doi:10.1109/TIT.2009.2030478.DOI
  8. [8]Y. Polyanskiy, H. V. Poor, and S. Verdú, Channel coding rate in the finite blocklength regime, IEEE Trans. Inf. Theory 56, 2307–2359 (2010). doi:10.1109/TIT.2010.2043769.DOI
  9. [9]W. Matthews, A linear program for the finite block length converse of Polyanskiy–Poor–Verdú via nonsignaling codes, IEEE Trans. Inf. Theory 58, 7036–7044 (2012). doi:10.1109/TIT.2012.2210695.DOI
  10. [10]D. Blackwell, Equivalent comparisons of experiments, Ann. Math. Statist. 24, 265–272 (1953). doi:10.1214/aoms/1177729032.DOI
  11. [11]S. Sherman, On a theorem of Hardy, Littlewood, Polya, and Blackwell, Proc. Natl. Acad. Sci. USA 37, 826–831 (1951). doi:10.1073/pnas.37.12.826.DOI
  12. [12]L. Le Cam, Sufficiency and approximate sufficiency, Ann. Math. Statist. 35, 1419–1455 (1964). doi:10.1214/aoms/1177700372.DOI
  13. [13]E. Torgersen, Comparison of Statistical Experiments, Encyclopedia of Mathematics and its Applications, Vol. 36, Cambridge University Press (1991). doi:10.1017/CBO9780511666353.DOI
  14. [14]J. M. Renes, Relative submajorization and its use in quantum resource theories, J. Math. Phys. 57, 122202 (2016). doi:10.1063/1.4972295.DOI
  15. [23]A. Oufkir, Y. Yao, and M. Berta, Strong converse exponent of channel interconversion, Ann. Henri Poincaré (2026). doi:10.1007/s00023-026-01758-0.DOI
  16. [24]V. Kostina and S. Verdú, Lossy joint source–channel coding in the finite blocklength regime, IEEE Trans. Inf. Theory 59, 2545–2575 (2013). doi:10.1109/TIT.2013.2238657.DOI
  17. [25]R. Yaguchi and M. Hayashi, Second order analysis for joint source–channel coding with general channel and Markovian source, IEEE Trans. Inf. Theory 65, 5750–5770 (2019). doi:10.1109/TIT.2019.2917200.DOI
  18. [26]Y. Kochman, O. Ordentlich, and Y. Polyanskiy, A lower bound on the expected distortion of joint source–channel coding, IEEE Trans. Inf. Theory 66, 4722–4741 (2020). doi:10.1109/TIT.2020.2983148.DOI
  19. [27]M. X. Cao and M. Tomamichel, Comments on Channel coding rate in the finite blocklength regime: On the quadratic decaying property of the information rate function, IEEE Trans. Inf. Theory 69, 5528–5531 (2023). doi:10.1109/TIT.2023.3276203.DOI
  20. [28]A. D. Wyner and J. Ziv, A theorem on the entropy of certain binary sequences and applications: Part I, IEEE Trans. Inf. Theory 19, 769–772 (1973). doi:10.1109/TIT.1973.1055107.
  21. [29]I. Shevtsova, On the absolute constants in the Berry–Esseen type inequalities for identically distributed summands (2011). arXiv:1111.6554.arxiv.org/abs/1111.6554
  22. [30]I. Csiszár, The method of types, IEEE Trans. Inf. Theory 44, 2505–2523 (1998). doi:10.1109/18.720546.DOI
  23. [31]S. Barman and O. Fawzi, Algorithmic aspects of optimal channel coding, IEEE Trans. Inf. Theory 64, 1038–1045 (2018). doi:10.1109/TIT.2017.2696963.DOI
  24. [32]A. Oufkir, O. Fawzi, and M. Berta, Optimality of meta-converse for channel simulation, IEEE Trans. Inf. Theory 72, 4522–4536 (2026). doi:10.1109/TIT.2026.3689356.DOI
  25. [33]C. T. Li and V. Anantharam, A unified framework for one-shot achievability via the Poisson matching lemma, IEEE Trans. Inf. Theory 67, 2624–2651 (2021). doi:10.1109/TIT.2021.3058842.DOI
  26. [34]T. S. Han, Nonnegative entropy measures of multivariate symmetric correlations, Information and Control 36, 133–156 (1978). doi:10.1016/S0019-9958(78)90275-9.DOI
  27. [35]L. R. Ford, Jr., and D. R. Fulkerson, Maximal flow through a network, Canad. J. Math. 8, 399–404 (1956). doi:10.4153/CJM-1956-045-5.DOI

Paper details

vlnc:W_rghytmmq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents