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

Jain, R. ; Radhakrishnan, J. ; Sen, P. (2003) A lower bound for the bounded round quantum communication complexity of set disjointness Proceedings - Annual Symposium on Foundations of Computer Science . pp. 220-229. ISSN 0272-5428

PDF - Author Version

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/SFCS.2003.1238196


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 Ω(smF)/(k2)), where smF) stands for the 'monotone sensitivity of ƒF' and is defined by smF) =Δ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].

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:89505
Deposited On:27 Apr 2012 13:38
Last Modified:19 May 2016 04:02

Repository Staff Only: item control page