|
This article is cited in 101 scientific papers (total in 101 papers)
Quantum communication complexity of symmetric predicates
A. A. Razborov Steklov Mathematical Institute, Russian Academy of Sciences
Abstract:
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<n\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.
Received: 29.04.2002
Citation:
A. A. Razborov, “Quantum communication complexity of symmetric predicates”, Izv. RAN. Ser. Mat., 67:1 (2003), 159–176; Izv. Math., 67:1 (2003), 145–159
Linking options:
https://www.mathnet.ru/eng/im422https://doi.org/10.1070/IM2003v067n01ABEH000422 https://www.mathnet.ru/eng/im/v67/i1/p159
|
Statistics & downloads: |
Abstract page: | 855 | Russian version PDF: | 242 | English version PDF: | 17 | References: | 36 | First page: | 3 |
|