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.

Bibliographie

[1] Ambainis A., Schulman L., Ta-Shma A., Vazirani U., Wigderson A., “The quantum communication complexity of sampling”, Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, 1998, 342–351

[2] Beals R., Buhrman H., Cleve R., Mosca M., de Wolf R., “Quantum lower bounds by polynomials”, Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, 1998, 352–361; Preliminary version available at E-print quant-ph/9802049

[3] Buhrman H., Cleve R., Wigderson A., “Quantum vs. classical communication and computation”, Proceedings of the 30th ACM Symposium on the Theory of Computing, 1998, 63–86 ; Preliminary version available at E-print quant-ph/9802040 | MR

[4] Babai L., Frankl P., Simon J., “Complexity classes in communication complexity theory”, Proceedings of the 27th IEEE FOCS, 1986, 337–347

[5] Bhatia R., Matrix Analysis, Graduate texts in mathematics, 169, Springer-Verlag, Berlin–N. Y., 1997 | MR | Zbl

[6] Buhrman H., de Wolf R., “Complexity measures and decision tree complexity: a survey”, Theoretical Computer Science, 2000 | MR

[7] Buhrman H., de Wolf R., “Communication complexity lower bounds by polynomials”, Proceedings of the 16th IEEE Conference on Computational Complexity, 2001, 120–130; Preliminary version available at E-print cs.CC/9910010

[8] Cleve R., Buhrman H., “Substituting quantum entanglement for communication”, Phys. Rev. A, 56 (1997), 1201–1204 ; Preliminary version available at E-print quant-ph/9704026 | DOI | MR

[9] Cleve R., van Dam W., Nielsen M., Tapp A., “Quantum entanglement and the communication complexity of the inner product function”, Proceedings of the 1st NASA QCQC Conference, Lecture Notes in Computer Science, 1509, Springer-Verlag, N. Y.–Berlin, 1998, 61–74 ; Preliminary version available at E-print quant-ph/9708019 | MR

[10] Chor B., Goldreich O., “Unbiased bits from sources of weak randomness and probabilistic communication complexity”, SIAM J. on Computing, 17:2 (1988), 230–261 | DOI | MR | Zbl

[11] Delsarte Ph., “Hahn polynomials, discrete harmonics and $t$-designs”, SIAM J. on Applied Mathematics, 34:1 (1978), 157–166 | DOI | MR

[12] Grover L. K., “A fast quantum mechanical algorithm for database search”, Proceedings of the 28th ACM Symposium on the Theory of Computing, 1996, 212–219 ; Preliminary version available at E-print quant-ph/9605043 | MR | Zbl

[13] {Høyer} P., de Wolf R., “Improved quantum communication complexity bounds for disjointness and equality”, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, 2002, 299–310 ; Preliminary version available at E-print quant-ph/0109068 | MR | Zbl

[14] Klauck H., “Lower bounds for quantum communication complexity”, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, 288–297 ; Preliminary version available at E-print quant-ph/0106160 | MR

[15] Klauck H., Nayak A., {Ta-Shma} A., Zuckerman D., “Interaction in quantum communication and the complexity of set disjointness”, Proceedings of the 33rd ACM Symposium on the Theory of Computing, 2001, 124–133 | MR

[16] Knuth D., Combinatorial matrices, Manuscript available at , 1991 http://www-cs-faculty.stanford.edu/~knuth/preprints.html#unpub

[17] Kremer I., Quantum communication, Master's thesis, Hebrew University, Jerusalem, 1995

[18] Kalyanasundaram B., Schnitger G., “The probabilistic communication complexity of set intersection”, SIAM J. on Discrete Mathematics, 5:4 (1992), 545–557 | DOI | MR | Zbl

[19] Mehlhorn K., Schmidt E. M., “Las {Vegas} is better than determinism in {VLSI} and distributive computing”, Proceedings of the 14th ACM STOC, 1982, 330–337

[20] Nisan N., Szegedy M., “On the degree of {Boolean} functions as real polynomials”, Computational complexity, 4 (1994), 301–313 | DOI | MR | Zbl

[21] Nayak A., Salzman J., “On communication over an entanglement-assisted quantum channel”, Proceedings of the 34th ACM Symposium on the Theory of Computing, 2002 | MR

[22] Paturi R., “On the degree of polynomials that approximate symmetric {Boolean} functions”, Proceedings of the 24th ACM Symposium on the Theory of Computing, 1992, 468–474

[23] Razborov A., “On the distributional complexity of disjointness”, Theoretical Computer Science, 106 (1992), 385–390 | DOI | MR | Zbl

[24] Vazirani U., “Towards a strong communication complexity theory of generating quasi-random sequences from two communicating slightly-random sources”, Combinatorica, 7:4 (1987), 375–392 | DOI | MR | Zbl

[25] Yao A., “Some complexity questions related to distributive computing”, Proceedings of the 11th ACM STOC, 1979, 209–213

[26] Yao A., “Quantum circuit complexity”, Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, 1993, 352–361 | MR