|
Эта публикация цитируется в 102 научных статьях (всего в 102 статьях)
О квантовой коммуникационной сложности симметрических предикатов
А. А. Разборов Математический институт им. В. А. Стеклова РАН
Аннотация:
С точностью до логарифмического множителя определяется коммуникационная сложность вычисления произвольной, зависящей лишь от $|x\cap y|$, функции $f(x,y)$, $x,y\subseteq [n]$, с допустимой вероятностью ошибки, отделенной от 1/2. Более точно, для предиката $D$ на множестве $\{0,1,\dots,n\}$ полагаем
\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*}
Тогда квантовая коммуникационная сложность функции $f_D(x,y)=D(|x\cap y|)$ в этой модели равна (с точностью до логарифмического множителя) величине $\sqrt{n\ell_0(D)}+\ell_1(D)$. В частности, сложность предиката, называемого дизъюнктность, оказывается равной $\Omega(\sqrt n\,)$. Полученный результат выполняется как в модели с предварительным зацеплением, так и в модели без такого зацепления.
Библиография: 26 наименований.
Поступило в редакцию: 29.04.2002
Образец цитирования:
А. А. Разборов, “О квантовой коммуникационной сложности симметрических предикатов”, Изв. РАН. Сер. матем., 67:1 (2003), 159–176; Izv. Math., 67:1 (2003), 145–159
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im422https://doi.org/10.4213/im422 https://www.mathnet.ru/rus/im/v67/i1/p159
|
Статистика просмотров: |
Страница аннотации: | 884 | PDF русской версии: | 252 | PDF английской версии: | 19 | Список литературы: | 40 | Первая страница: | 3 |
|