Channel Simulation: Finite Blocklengths and Broadcast Channels

Abstract

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.

38 pages, 6 figures

References in corpus (20)

• Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
• Post-selection technique for quantum channels with applications to quantum cryptography
• A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks
• Coordination Capacity
• Distributed Channel Synthesis
• Quantum Reverse Shannon Theorem
• The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
• A Tight Upper Bound for the Third-Order Asymptotics for Most Discrete Memoryless Channels
• Quantum message compression with applications
• Zero-error channel capacity and simulation assisted by non-local correlations
• Quantum Channel Simulation and the Channel's Smooth Max-Information
• Universal coding for classical-quantum channel
• A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
• Identifying the Information Gain of a Quantum Measurement
• Moderate deviation analysis for classical communication over quantum channels
• Computing Quantum Channel Capacities
• Partially smoothed information measures
• Quantum Side Information: Uncertainty Relations, Extractors, Channel Simulations
• Moderate deviation expansion for fully quantum tasks
• Multiple Access Channel Simulation

Cited by in corpus (1)

• One-shot Multiple Access Channel Simulation