title: Communication Tasks with Infinite Quantum-Classical Separation.
abstract: 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 parties' 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 their classical counterpart. 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 may have access to entanglement. With this assistance, 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 Pusey-Barrett-Rudolph theorem which arises in the context of the foundations of quantum theory.
authors.affiliation: Department of Physics and Astronomy, University College London, Gower Street, London WC1E 6BT, United Kingdom.
authors.forename: Christopher
authors.initials: C
authors.lastname: Perry
authors.affiliation: Department of Computer Science and Centre for Quantum Technologies, National University of Singapore, Singapore 119615, Singapore.
authors.forename: Rahul
authors.initials: R
authors.lastname: Jain
authors.affiliation: Department of Physics and Astronomy, University College London, Gower Street, London WC1E 6BT, United Kingdom.|Department of Computer Science and Centre for Quantum Technologies, National University of Singapore, Singapore 119615, Singapore.
authors.forename: Jonathan
authors.initials: J
authors.lastname: Oppenheim