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

Simple item page
dc.creatorJain, Rahul
dc.creatorRadhakrishnan, Jaikumar
dc.creatorSen, Pranab
dc.date2003-03-22
dc.date2003-04-09
dc.date.accessioned2026-07-07T06:06:24Z
dc.date.available2026-07-07T06:06:24Z
dc.descriptionWe consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}, such that F(X_1,X_2, ..., X_t) = f_F(X_1 \cap X_2 \cap ... \cap X_t). We show that the t-party k-round communication complexity of F is Omega(s_m(f_F)/(k^2)), where s_m(f_F) stands for the `monotone sensitivity of f_F' and is defined by s_m(f_F) \defeq max_{S\subseteq [n]} |{i: f_F(S \cup {i}) \neq f_F(S)|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Omega(n/k^2) qubits. For k=1, our lower bound matches the Omega(n) lower bound observed by Buhrman and de Wolf (based on a result of Nayak, and for 2 <= k <= n^{1/4}, improves the lower bound of Omega(sqrt{n}) shown by Razborov. (For protocols with no restrictions 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.)
dc.description15 pages, content added and modified, references added
dc.identifierhttps://arxiv.org/abs/quant-ph/0303138
dc.identifierhttp://arxiv.org/abs/quant-ph/0303138
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/90962
dc.subjectQuantum Physics
dc.titleA lower bound for bounded round quantum communication complexity of set disjointness
dc.typetext

Files

Collections

arXiv