Quantum communication complexity of symmetric predicates

A. A. Razborov

Izvestiya. Mathematics , Tome 67 (2003) no. 1, pp. 145-159

Résumé

We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate $f(x,y)$ $x,y\subseteq [n]$) depending only on $|x\cap y|$. More precisely, given a predicate $D$ on $\{0,1,\dots,n\}$, we put \begin{align*} \ell_0(D)\overset{\mathrm{def}}{=}\max\{\ell\mid 1\leqslant\ell\leqslant n/2\land D(\ell)\not\equiv D(\ell-1)\}, \\ \ell_1(D)\overset{\mathrm{def}}{=}\max\{n-\ell\mid n/2\leqslant\ell\land D(\ell) \not\equiv D(\ell+1)\}. \end{align*} Then the bounded-error quantum communication complexity of $f_D(x,y)=D(|x\cap y|)$ is equal to $\sqrt{n\ell_0(D)}+\ell_1(D)$ (up to a logarithmic factor). In particular, the complexity of the set disjointness predicate is equal to $\Omega(\sqrt n\,)$. This result holds both in the model with prior entanglement and in the model without it.