О квантовой коммуникационной сложности симметрических предикатов

С точностью до логарифмического множителя определяется коммуникационная сложность вычисления произвольной, зависящей лишь от $|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 наименований.