A lower bound for the bounded round quantum communication complexity of set disjointness

We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input Xi ⊆ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X1,X2, . . . ,Xt). We consider the class of functionswhose value depends only on the intersection of X1,X2, . . . ,Xt; that is, for each F in this class there is an ƒF : 2[n] → {0, 1}, such that F(X1,X2, . . . ,Xt) = ƒF (X1 ∩ X2 ∩. . . ∩ Xt). We show that the t-party k-round communication complexity of F is Ω(sm(ƒF)/(k2)), where sm(ƒF) stands for the 'monotone sensitivity of ƒF' and is defined by sm(ƒF) =Δmax S⊆[n]|{i : ƒF (S ∪ {i}) ≠ ƒF(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Ω(n/k2) qubits. An upper bound of O(n/k) can be derived from the O(√n) upper bound due to Aaronson and Ambainis (see also [BCW98] and [HdW02]). For k = 1, our lower bound matches the √(n) lower bound observed by Buhrman and de Wolf [BdW01] (based on a result of Nayak [Nay99]), and for 2≤ ≤ k « n¼, improves the lower bound of Ω(√n) shown by Razborov [Raz02]. (For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange Ω(n⅓) qubits. This, however, falls short of the optimal Ω(√n) lower bound shown by Razborov [Raz02]). Our result is obtained by adapting to the quantumsetting the elegant information-theoretic arguments of Bar-Yossef, Jayram, Kumar and Sivakumar [BJKS02]. Using this method we can show similar lower bounds for the L∞ function considered in [BJKS02]