Classical interaction cannot replace a quantum message

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.