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

Abstract

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₂, . . . ,X_t). We consider the class of functionswhose value depends only on the intersection of X₁,X₂, . . . ,X_t; that is, for each F in this class there is an ƒ_F : 2^[n] → {0, 1}, such that F(X₁,X₂, . . . ,X_t) = ƒ_F (X₁ ∩ X₂ ∩. . . ∩ X_t). We show that the t-party k-round communication complexity of F is Ω(s_m(ƒ_F)/(k²)), where s_m(ƒ_F) stands for the 'monotone sensitivity of ƒ_F' and is defined by s_m(ƒ_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/k²) 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].