Classical Interaction Cannot Replace a Quantum Message

Dmitry Gavinsky

Abstract

We give a communication problem between two players, Alice and Bob, that can be solved by Alice sending a quantum message to Bob, for which any classical *interactive* protocol requires exponentially more communication.

The transparencies (and the paper) can be found here: http://www.iqc.ca/~dgavinsky/talks/index.html (the newest item).

N.B.: No prior knowledge of quantum computing is required!