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

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

2003-03-22

arxiv.org/abs/quant-ph/0303138v2

Physics

Quantum Physics

15 pages, content added and modified, references added

Scientific paper

We 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.)

Affiliated with

Also associated with

No associations

Rating

A lower bound for bounded round quantum communication complexity of set disjointness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A lower bound for bounded round quantum communication complexity of set disjointness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A lower bound for bounded round quantum communication complexity of set disjointness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-476224