Quantum communication complexity of symmetric predicates

Details Quantum communication complexity of symmetric predicates Quantum communication complexity of symmetric predicates

2002-04-04

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

Izvestiya of the Russian Academy of Science, mathematics, Vol. 67, No 1, 2003, pp. 159-176 (145-159 in Engl. transl.)

Physics

Quantum Physics

20 pages

Scientific paper

We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate $f(x,y)$ depending only on $|x\cap y|$ ($x,y\subseteq [n]$). Namely, for a predicate $D$ on $\{0,1,...,n\}$ let $\ell_0(D)\df \max\{\ell : 1\leq\ell\leq n/2\land D(\ell)\not\equiv D(\ell-1)\}$ and $\ell_1(D)\df \max\{n-\ell : n/2\leq\ell < n\land D(\ell)\not\equiv D(\ell+1)\}$. Then the bounded-error quantum communication complexity of $f_D(x,y) = D(|x\cap y|)$ is equal (again, up to a logarithmic factor) to $\sqrt{n\ell_0(D)}+\ell_1(D)$. In particular, the complexity of the set disjointness predicate is $\Omega(\sqrt n)$. This result holds both in the model with prior entanglement and without it.

Affiliated with

Also associated with

No associations

Rating

Quantum communication complexity of symmetric predicates 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 Quantum communication complexity of symmetric predicates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum communication complexity of symmetric predicates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-553257