pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

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

William Matthews, IQC Waterloo

joint work with Toby Cubitt, Debbie Leung, and Andreas Winter

We will show that there are classical channels whose classical (one-shot) zero-error capacity can be increased by making use of a suitable entangled state shared between the sender and receiver. This constitutes a novel use of entanglement to enhance a classical communication task. Our examples are based on proofs of the Bell-Kochen-Specker theorem and the phenomenon is shown to be related to "pseudo-telepathy'' games.

These examples pose the question: To what extent can entanglement assist for zero-error communication? To this end we have found upper bounds by considering assistance by general non-signalling (NS) correlations e.g. the 'box' of Popescu and Rohrlich. This vastly simplifies the theory (and sometimes enables zero-error communication even when the available channel has no zero-error capacity). We give an efficiently computable, single-letter formula for both the NS-assisted zero-error capacity and the NS-assisted asymptotic communication cost of exact simulation (similarly for the corresponding single-shot quantities). We even obtain a weak form of asymptotic reversibility between zero-error coding and simulation in the presence of NS correlations (analogous to the reverse Shannon theorem), which we show cannot be made any stronger.