Improving Zero-Error Classical Communication with Entanglement

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 behavior constitutes the field of classical zero-error information theory. 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 without error. In particular, we show how to construct such a channel based on any proof of the Kochen-Specker theorem. We investigate the connection to pseudotelepathy games. The use of generalized nonsignaling correlations to assist in this task is also considered. In this case, an elegant theory results and, remarkably, it is sometimes possible to transmit information with zero error using a channel with no unassisted zero-error capacity.

Figure 1

A KS basis set of six bases for ${\mathbb{C}}^4$ is tabulated at the bottom of the figure, one basis per row. The vectors are presented as 4-tuples labeled by a number. The diagram represents a channel $\mathcal{N}$ with an input symbol for each vector in the set. It has an output symbol for each gray loop: on input $x$ the output is drawn uniformly at random from those corresponding to the three loops which contain that $x$. Inputs are confusable if and only if corresponding vectors are orthogonal, so by Theorem 2, $c_0(\mathcal{N})<6$ (in fact it is 5), but $c_{\mathrm{SE}}(\mathcal{N})\ge 6$. It is interesting to note that to send one of six symbols (with equal prior probabilities) by a single use of $\mathcal{N}$, the best unassisted code has error probability $1/18$.