Zero-error channel capacity and simulation assisted by non-local correlations

Abstract

Shannon's theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly, and in the presence of various resources that are all classes of non-signalling correlations: Shared randomness, shared entanglement and arbitrary non-signalling correlations. Specifically, when the channel being simulated is noiseless, this reduces to the zero-error capacity of the channel, assisted by the various classes of non-signalling correlations. When the resource channel is noiseless, it results in the "reverse" problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, 'one-shot' separations between the power of the different assisting correlations are exhibited. The most striking result of this kind is that entanglement can assist in zero-error communication, in stark contrast to the standard setting of communicaton with asymptotically vanishing error in which entanglement does not help at all. In the asymptotic case, shared randomness is shown to be just as powerful as arbitrary non-signalling correlations for noisy channel simulation, which is not true for the asymptotic zero-error capacities. For assistance by arbitrary non-signalling correlations, linear programming formulas for capacity and simulation are derived, the former being equal (for channels with non-zero unassisted capacity) to the feedback-assisted zero-error capacity originally derived by Shannon to upper bound the unassisted zero-error capacity. Finally, a kind of reversibility between non-signalling-assisted capacity and simulation is observed, mirroring the famous "reverse Shannon theorem".

18 pages, 1 figure. Small changes to text in v2. Removed an unnecessarily strong requirement in the premise of Theorem 11

References in corpus (1)

• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels

Cited by in corpus (45)

• Bell nonlocality
• Enhanced communication with the assistance of indefinite causal order
• Distributed Channel Synthesis
• Quantum Reverse Shannon Theorem
• Kochen-Specker Contextuality
• Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
• On the power of PPT-preserving and non-signalling codes
• Semidefinite programming strong converse bounds for classical capacity
• No-Signalling Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovasz Number
• Resource convertibility and ordered commutative monoids
• Quantum Channel Simulation and the Channel's Smooth Max-Information
• Semidefinite programming relaxations for quantum correlations
• A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
• Semidefinite programming converse bounds for quantum communication
• Contextuality in entanglement-assisted one-shot classical communication
• Semi-definite programming and quantum information
• A semidefinite programming upper bound of quantum capacity
• On zero-error communication via quantum channels in the presence of noiseless feedback
• The Communication Value of a Quantum Channel
• Mutually Unbiased Balanced Functions & Generalized Random Access Codes
• On entanglement assistance to a noiseless classical channel
• Adaptive advantage in entanglement-assisted communications
• A new property of the Lovász number and duality relations between graph parameters
• Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
• Certifying the Classical Simulation Cost of a Quantum Channel
• Channel Simulation: Finite Blocklengths and Broadcast Channels
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• Quantum Nonlocality: Multi-copy Resource Inter-convertibility & Their Asymptotic Inequivalence
• Entanglement can completely defeat quantum noise
• Reliable Simulation of Quantum Channels: the Error Exponent
• Multi-party zero-error classical channel coding with entanglement
• On the quantum no-signalling assisted zero-error classical simulation cost of non-commutative bipartite graphs
• On optimal entanglement assisted one-shot classical communication
• Strong Coordination over Noisy Channels
• Shadow Simulation of Quantum Processes
• Computability limits non-local correlations
• One-time Pad Encryption Model for Non-local Correlations
• Quantum non-signalling assisted zero-error classical capacity of qubit channels
• Cost of Simulating Entanglement in Steering Scenario
• Demonstration of universal contextuality through communication games free of both operational inequivalence and compatibility loopholes
• Classical communication cost of a bipartite quantum channel assisted by non-signalling correlations
• Constructing local models for general measurements on bosonic Gaussian states
• Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?
• Retrocausal capacity of a quantum channel: Communicating through noisy closed timelike curves
• Zero-error communication under discrete-time Markovian dynamics