Jaikumar Radhakrishnan

In the set disjointness problem, there are two parties A and B, each with a subset of {1,...,n}. They wish to communicate to determine if their sets are disjoint. For this problem quantum protocols do provably better than classical protocols. Recently, Aaronson and Ambainis showed a protocol for this problem where the two parties exchange O(sqrt{n}) qubits, matching the previous lower bound of Omega(sqrt{n}) shown by Razborov. (The classical randomized communication complexity of this problem is theta(n).) We consider bounded-round quantum communication protocols for the set disjointness problem, and show that in any communication protocol with k rounds, the two parties must exchange Omega(n/k^2) qubits. This lower bound is obtained by adapting the the information theoretic proof technique of Bar-Yossef, Jayram, Kumar and Sivakumar to the quantum setting. An upper bound of O(n/k) follows easily from the O(sqrt{n}) upper bound due to Aaronson and Ambainis. For protocols with no restriction on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov.