Communication tasks with infinite quantum-classical separation

Understand

Quantum resources can be more powerful than classical resources - a quantum computer can solve certain problems exponentially faster than a classical computer, and computing a function of two people's inputs can be done with exponentially less communication with quantum messages than with classical ones.

• Here we consider a task between two players, Alice and Bob where quantum resources are infinitely more powerful than classical ones.
• Alice is given a string of length n, and Bob's task is to exclude certain combinations of bits that Alice might have.
• If Alice must send classical messages, then she must reveal nearly n bits of information to Bob, but if she is allowed to send quantum bits, the amount of information she must reveal goes to zero with increasing n.