  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. Next, we consider a version of the task where the parties can
only send classical messages but may have access to entanglement. When assisted
by entanglement, Alice only needs to send a constant number of bits, while
without entanglement, the number of bits Alice must send grows linearly with n.
The task is related to the PBR theorem which arises in the context of the
foundations of quantum theory.
