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 X_i ⊆ [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 (X₁,...,X_t). We consider the class of Boolean valued functions whose value depends only on X₁ ∩...∩ X_t; that is, for each F in this class there is an f_F : 2^[n] → {0,1}, such that F(X₁,...,X_t) = f_F(X₁ ∩...∩ X_t). We show that the t-party k-round communication complexity of F is Ω(s_m(f_F)/(k²)), where s_m(f_F) stands for the monotone sensitivity of f_F´ and is defined by s_m(f_F) = ^▵ max_S⊆[n] |{i : f_F(S ∪ {i}) ≠ f_F(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Ω(n/k²) qubits. An upper bound of O(n/k) can be derived from the O(√n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the Ω(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 ≤ k ≪ n¹4 /, improves the lower bound of Ω(√n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange Ω(n¹3/) qubits. This, however, falls short of the optimal Ω (√n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L_∞ function considered in Z. Bar-Yossef et al. (2002).