Source-linked AI summary
Improving zero-error classical communication with entanglement
Toby S. Cubitt, Debbie Leung, William Matthews, Andreas Winter
TL;DR
The paper asks whether entanglement or more general correlations can improve zero-error classical communication. It constructs channels exhibiting one-shot entanglement advantages, connects the phenomenon to pseudo-telepathy, and derives a simple non-signalling-assisted theory.
Problem
The paper studies whether shared correlations can increase the number of classical messages transmitted perfectly over a single use of a classical channel.
Source: p. 1Method
It characterizes entanglement assistance through confusability graphs, constructs channels from Kochen-Specker basis sets, relates coding to pseudo-telepathy games, and analyzes non-signalling assistance via hypergraphs.
Source: pp. 2–4Results
For certain classical channels, entanglement increases one-shot zero-error capacity, while non-signalling assistance admits a simple formula and can enable zero-error transmission even when unassisted capacity is zero.
Source: p. 4Takeaways & Limitations
Quantum and generalized non-signalling effects can improve a classical zero-error communication task in the one-shot setting.
Source: pp. 1, 4Entanglement cannot help a channel with no unassisted zero-error capacity, because that would permit perfect communication through a completely noisy channel.
Source: p. 2
Abstract
from arXiv · showhide
Given one or more uses of a classical channel, only a certain number of messages can be transmitted with zero probability of error. The study of this number and its asymptotic behaviour constitutes the field of classical zero-error information theory, the quantum generalisation of which has started to develop recently. We show that, given a single use of certain classical channels, entangled states of a system shared by the sender and receiver can be used to increase the number of (classical) messages which can be sent with no chance of error. In particular, we show how to construct such a channel based on any proof of the Bell-Kochen-Specker theorem. This is a new example of the use of quantum effects to improve the performance of a classical task. We investigate the connection between this phenomenon and that of ``pseudo-telepathy'' games. The use of generalised non-signalling correlations to assist in this task is also considered. In this case, a particularly elegant theory results and, remarkably, it is sometimes possible to transmit information with zero-error using a channel with no unassisted zero-error capacity.