  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.
