Interaction in quantum communication and the complexity of set disjointness
Hartmut Klauck, Ashwin Nayak, Amnon Ta‐Shma, David Zuckerman · 2001
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. Moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties.