The Quantum Communication Complexity of Sampling

U. Vazirani


Sampling is an important primitive in quantum algorithms. We consider the following sampling problem in a communication complexity setting: Alice has a subset $A \subseteq \{1,2,\dots,n\}$ of cardinality $\sqrt{n}$ and Bob must pick a uniformly random subset of cardinality $\sqrt{n}$ and disjoint from A. We shall allow Bob a probability $\varepsilon$ of error, by requiring that the distribution of the subset he chooses is $1-\varepsilon$ close to the uniform distribution. We show that there is a constant $\varepsilon$ such that the minimum number of bits that Alice and Bob must exchange to carry out this task in a classical setting is $\Omega(\sqrt{n})$. By contrast the number of qubits exchanged by our quantum protocol to solve this problem is $O(\log{n})$. Therefore this provides the first example of an exponential separation between classical and quantum communication complexity in the bounded urd model.