We study channel simulation under common randomness assistance in the finite-blocklength regime and identify the smooth channel max-information as a linear program one-shot converse on the minimal simulation cost for fixed error tolerance. We show that this one-shot converse can be achieved exactly using no-signaling-assisted codes, and approximately achieved using common randomness-assisted codes. Our one-shot converse thus takes on an analogous role to the celebrated meta-converse in the complementary problem of channel coding, and we find tight relations between these two bounds. We asymptotically expand our bounds on the simulation cost for discrete memoryless channels, leading to the second-order as well as the moderate-deviation rate expansion, which can be expressed in terms of the channel capacity and channel dispersion known from noisy channel coding. Our bounds imply the well-known fact that the optimal asymptotic rate of one channel to simulate another under common randomness assistance is given by the ratio of their respective capacities. Additionally, our higher-order asymptotic expansion shows that this reversibility falls apart in the second order. Our techniques extend to discrete memoryless broadcast channels. In stark contrast to the elusive broadcast channel capacity problem, we show that the reverse problem of broadcast channel simulation under common randomness assistance allows for an efficiently computable single-letter characterization of the asymptotic rate region in terms of the broadcast channel’s multipartite mutual information.
We study channel simulation under common randomness assistance in the finite-blocklength regime and identify the smooth channel max-information as a linear program one-shot converse on the minimal simulation cost for fixed error tolerance. We show that this one-shot converse can be achieved exactly using no-signaling-assisted codes, and approximately achieved using common randomness-assisted codes. Our one-shot converse thus takes on an analogous role to the celebrated meta-converse in the complementary problem of channel coding, and we find tight relations between these two bounds. We asymptotically expand our bounds on the simulation cost for discrete memoryless channels, leading to the second-order as well as the moderate-deviation rate expansion, which can be expressed in terms of the channel capacity and channel dispersion known from noisy channel coding. Our bounds imply the well-known fact that the optimal asymptotic rate of one channel to simulate another under common randomness assistance is given by the ratio of their respective capacities. Additionally, our higher-order asymptotic expansion shows that this reversibility falls apart in the second order. Our techniques extend to discrete memoryless broadcast channels. In stark contrast to the elusive broadcast channel capacity problem, we show that the reverse problem of broadcast channel simulation under common randomness assistance allows for an efficiently computable single-letter characterization of the asymptotic rate region in terms of the broadcast channel’s multipartite mutual information.
We study the approximate channel simulation problem in the normal approximation regime. Our starting point is the fact established by Cao et al.~\cite{Cao_channel_simulation}, that the minimal codebook size Mε∗(W) for a fixed error tolerance ε>0 is closely related to the ε-smooth channel max-information, Imaxε(W). Using this, we refine earlier large-blocklength approximations to Mε∗(W⊗n) for discrete memoryless channels. Specifically, we provide tight third-order expansions for Gallager-symmetric channels and demonstrate that the third-order term is channel-dependent. As in corresponding channel coding expansions, we identify a substantial rate gap between singular and nonsingular channels. Notably, the direction of this gap is reversed relative to channel coding: The third-order term is −21logn for singular channels but O(loglogn) for nonsingular channels.
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 the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. Our main results are as follows. First, we show that the minimum error of simulation under non-signalling assisted codes is efficiently computable via semidefinite programming. The cost of simulating a channel via noiseless quantum channels under non-signalling assisted codes can also be characterized as a semidefinite program. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the channel's mutual information. We show that the one-shot quantum simulation cost under non-signalling assisted codes is exactly equal to the channel's smooth max-information. Due to the quantum reverse Shannon theorem, the channel's smooth max-information converges to the channel's mutual information in the independent and identically distributed asymptotic limit. Together with earlier findings on the (activated) non-signalling assisted one-shot capacity of channels [Wang et al., arXiv:1709.05258], this suggest that the operational min- and max-type one-shot analogues of the channel's mutual information are the channel's hypothesis testing relative entropy and the channel's smooth max-information, respectively.
We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. First, we show that the minimum error of simulation and the one-shot quantum simulation cost under no-signalling assisted codes are given by semidefinite programs. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel's smooth max-information as the one-shot quantum simulation cost under no-signalling assisted codes, which significantly simplifies the study of channel simulation and provides insights and bounds for the case under entanglement-assisted codes. Third, we derive the asymptotic equipartition property of the channel's smooth max-information; i.e., it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. This implies the quantum reverse Shannon theorem in the presence of no-signalling correlations. Finally, we explore the simulation cost of various quantum channels.
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 study the problem of random-assisted simulation of discrete broadcast channel in one-shot and i.i.d. setups. We derive one-shot inner and outer bounds of the set of attainable message-size pairs for simulating WYZ|Xwithin some total variation distance (TVD) tolerance of ϵ. The inner bounds are based on the bipartite convex split lemma. Whereas the outer bounds are based on the properties of the multi-partite max information. Using these bounds, we establish a single-letter expression of the simulation region of a broadcast channel.