RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izv. RAN. Ser. Mat., 2003, Volume 67, Issue 1, Pages 159–176 (Mi izv422)

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,…,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.

DOI: https://doi.org/10.4213/im422

Full text: PDF file (1573 kB)
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 2003, 67:1, 145–159

Bibliographic databases:

UDC: 510.52
MSC: 03D15, 68Q15, 81P68

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

Citation in format AMSBIB
\Bibitem{Raz03} \by A.~A.~Razborov \paper Quantum communication complexity of symmetric predicates \jour Izv. RAN. Ser. Mat. \yr 2003 \vol 67 \issue 1 \pages 159--176 \mathnet{http://mi.mathnet.ru/izv422} \crossref{https://doi.org/10.4213/im422} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1957920} \zmath{https://zbmath.org/?q=an:1088.68052} \transl \jour Izv. Math. \yr 2003 \vol 67 \issue 1 \pages 145--159 \crossref{https://doi.org/10.1070/IM2003v067n01ABEH000422} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000185513200008} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33748500069} 

• http://mi.mathnet.ru/eng/izv422
• https://doi.org/10.4213/im422
• http://mi.mathnet.ru/eng/izv/v67/i1/p159

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Ambainis A., Schulman L.J., Ta-Shma A., Vazirani U., Wigderson A., “The quantum communication complexity of sampling”, SIAM J. Comput., 32:6 (2003), 1570–1585
2. Buhrman H., Rohrig H., “Distributed quantum computing”, Mathematical foundations of computer science, Lecture Notes in Comput. Sci., 2747, Springer, Berlin, 2003, 1–20
3. Aaronson S., Ambainis A., “Quantum search of spatial regions (extended abstract)”, 44th Annual IEEE Symposium on Foundations of Computer Science, Proceedings, Annual IEEE Symposium on Foundations of Computer Science, 2003, 200–209
4. Klauck H., “Quantum and approximate privacy”, Theory Comput. Syst., 37:1 (2004), 221–246
5. Lowe B., Piwinger B., Rasch T., “Classical and New Paradigms of Computation and Their Complexity Hierarchies - Papers of the Conference “Foundations of the Formal Sciences III” - Preface”, Classical and New Paradigms of Computation and their Complexity Hierarchies, Trends in Logic - Studia Logica Library, 23, 2004, VII
6. Zhang Shengyu, “Promised and distributed quantum search”, Computing and combinatorics, Lecture Notes in Comput. Sci., 3595, Springer, Berlin, 2005, 430–439
7. Huang Wei, Shi Yaoyun, Zhang Shengyu, Zhu Yufan, “The communication complexity of the Hamming distance problem”, Inform. Process. Lett., 99:4 (2006), 149–153
8. Nayak A., Salzman J., “Limits on the ability of quantum states to convey classical messages”, J. ACM, 53:1 (2006), 184–206
9. Klauck H., Nayak A., Ta-Shma A., Zuckerman D., “Interaction in quantum communication”, IEEE Trans. Inform. Theory, 53:6 (2007), 1970–1982
10. Iwama K., Nishimura H., Raymond R., Yamashita Sh., “Unbounded-error one-way classical and quantum communication complexity”, Automata, Languages and Programming, Proceedings, Lecture Notes in Computer Science, 4596, 2007, 110–121
11. Shi Yaoyun, Zhu Yufan, “Tensor norms and the classical communication complexity of nonlocal quantum measurement”, SIAM J. Comput., 38:3 (2008), 753–766
12. Sherstov A.A., “The Pattern Matrix Method for Lower Bounds on Quantum Communication”, STOC'08: Proceedings of the 2008 Acm International Symposium on Theory of Computing, 2008, 85–94
13. Aaronson S., Wigderson A., “Algebrization: A New Barrier in Complexity Theory”, STOC'08: Proceedings of the 2008 Acm International Symposium on Theory of Computing, 2008, 731–740
14. Montanaro A., Nishimura H., Raymond R., “Unbounded-Error Quantum Query Complexity”, Algorithms and Computation, Proceedings, Lecture Notes in Computer Science, 5369, 2008, 919–930
15. Aaronson S., “The Polynomial Method in Quantum and Classical Computing”, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Annual IEEE Symposium on Foundations of Computer Science, 2008, 3–3
16. Sherstov A.A., “The Unbounded-Error Communication Complexity of Symmetric Functions”, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Annual IEEE Symposium on Foundations of Computer Science, 2008, 384–393
17. David M., Pitassi T., Viola E., “Improved Separations between Nondeterministic and Randomized Multiparty Communication”, Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques, Proceedings, Lecture Notes in Computer Science, 5171, 2008, 371–384
18. Lee T., Shraibman A., “Disjointness is hard in the multi-party number-on-the-forehead model”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, 2008, 81–91
19. Sherstov A.A., “Approximate inclusion-exclusion for arbitrary symmetric functions”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, 2008, 112–123
20. Tani S., Nakanishi M., Yamashita Sh., “Multi-party quantum communication complexity with routed messages”, Computing and Combinatorics, Proceedings, Lecture Notes in Computer Science, 5092, 2008, 180–190
21. François Le Gall, “Exponential Separation of Quantum and Classical Online Space Complexity”, Theory Comput. Syst., 45:2 (2009), 188–202
22. Linial N., Shraibman A., “Lower bounds in communication complexity based on factorization norms”, Random Structures Algorithms, 34:3 (2009), 368–394
23. Sherstov A. A., “Separating $\mathsf{AC}^0$ from depth-2 majority circuits”, SIAM J. Comput., 38:6 (2009), 2113–2129
24. Lee Troy, Shraibman Adi, “Disjointness is hard in the multiparty number-on-the-forehead model”, Comput. Complexity, 18:2 (2009), 309–336
25. Tani S., Nakanishi M., Yamashita Sh., “Multi-party quantum communication complexity with routed messages”, IEICE Transactions on Information and Systems, E92D:2 (2009), 191–199
26. Zhang Zhiqiang, Shi Yaoyun, “Communication complexities of symmetric XOR functions”, Quantum Inf. Comput., 9:3-4 (2009), 255–263
27. Shi Yaoyun, Zhu Yufan, “Quantum communication complexity of block-composed functions”, Quantum Inf. Comput., 9:5-6 (2009), 444–460
28. Zhang Sh., “On the Tightness of the Buhrman-Cleve-Wigderson Simulation”, Algorithms and Computation, Proceedings, Lecture Notes in Computer Science, 5878, 2009, 434–440
29. Lee T., Schechtman G., Shraibman A., “Lower bounds on quantum multiparty communication complexity”, Proceedings of the 24th Annual IEEE Conference on Computational Complexity, Annual IEEE Conference on Computational Complexity, 2009, 254–262
30. Lee T., Shraibman A., “An approximation algorithm for approximation rank”, Proceedings of the 24th Annual IEEE Conference on Computational Complexity, Annual IEEE Conference on Computational Complexity, 2009, 351–357
31. Kaplan M., Laplante S., “Kolmogorov Complexity and Combinatorial Methods in Communication Complexity”, Theory and Applications of Models of Computation, Lecture Notes in Computer Science, 5532, 2009, 261–270
32. Buhrman H., Cleve R., Massar S., de Wolf R., “Nonlocality and communication complexity”, Reviews of Modern Physics, 82:1 (2010), 665–698
33. Sherstov A.A., “On quantum-classical equivalence for composed communication problems”, Quantum Information & Computation, 10:5-6 (2010), 435–455
34. Klivans A.R., Sherstov A.A., “Lower Bounds for Agnostic Learning via Approximate Rank”, Computational Complexity, 19:4 (2010), 581–604
35. Marc Kaplan, Sophie Laplante, “Kolmogorov complexity and combinatorial methods in communication complexity”, Theoretical Computer Science, 2010
36. Lee T., Zhang Sh., “Composition Theorems in Communication Complexity”, Automata, Languages and Programming, Lecture Notes in Computer Science, 6198, no. I, 2010, 475–489
37. Ashley Montanaro, Harumichi Nishimura, Rudy Raymond, “Unbounded-error quantum query complexity”, Theoretical Computer Science, 2011
38. Alexander A. Sherstov, “The unbounded-error communication complexity of symmetric functions”, Combinatorica, 2011
39. Alexander A. Sherstov, “The Pattern Matrix Method”, SIAM J. Comput, 40:6 (2011), 1969
40. Paul Beame, Trinh Huynh, “Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremathAC^0$”, SIAM J. Comput, 41:3 (2012), 484
41. Briet J., Buhrman H., Lee T., Vidick T., “Multipartite Entanglement in Xor Games”, Quantum Inform. Comput., 13:3-4 (2013), 334–360
42. Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen, “The NOF Multiparty Communication Complexity of Composed Functions”, comput. complex, 2014
43. Sherstov A.A., “Communication Complexity Theory: Thirty-Five Years of Set Disjointness”, Mathematical Foundations of Computer Science 2014, Pt I, Lecture Notes in Computer Science, 8634, eds. CsuhajVarju E., Dietzfelbinger M., Esik Z., Springer-Verlag Berlin, 2014, 24–43
44. Braverman M., Garg A., Ko Y.K., Mao J., Touchette D., “Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness”, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) (Berkeley, CA, USA), IEEE, 2015, 773–791
45. Montanaro A., “the Quantum Complexity of Approximating the Frequency Moments”, Quantum Inform. Comput., 16:13-14 (2016), 1169–1190
46. Lee T., Leonardos N., Saks M., Wang F., “Hellinger volume and number-on-the-forehead communication complexity”, J. Comput. Syst. Sci., 82:6 (2016), 1064–1074
47. Goos M., Lovett Sh., Meka R., Watson T., Zuckerman D., “Rectangles Are Nonnegative Juntas”, SIAM J. Comput., 45:5 (2016), 1835–1869
48. Sherstov A.A., “The Multiparty Communication Complexity of Set Disjointness”, SIAM J. Comput., 45:4, SI (2016), 1450–1489
49. Gruska J., Qiu D., Zheng Sh., “Generalizations of the distributed Deutsch–Jozsa promise problem”, Math. Struct. Comput. Sci., 27:3 (2017), 311–331
50. Kothari P.K., Meka R., Raghavendra P., “Approximating Rectangles By Juntas and Weakly-Exponential Lower Bounds For Lp Relaxations of Csps”, Stoc'17: Proceedings of the 49Th Annual Acm Sigact Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, eds. Hatami H., McKenzie P., King V., Assoc Computing Machinery, 2017, 590–603
51. Sherstov A.A., “On Multiparty Communication With Large Versus Unbounded Error”, Theory Comput., 14 (2018), 22
52. Ben-David Sh., Bouland A., Garg A., Kothari R., “Classical Lower Bounds From Quantum Upper Bounds”, 2018 IEEE 59Th Annual Symposium on Foundations of Computer Science (Focs), Annual IEEE Symposium on Foundations of Computer Science, ed. Thorup M., IEEE Computer Soc, 2018, 339–349
53. Laplante S., Lauriere M., Nolin A., Roland J., Senno G., “Robust Bell Inequalities From Communication Complexity”, Quantum, 2 (2018)
54. Le Gall F., Magniez F., “Sublinear-Time Quantum Computation of the Diameter in Congest Networks”, Podc'18: Proceedings of the 2018 Acm Symposium on Principles of Distributed Computing, Assoc Computing Machinery, 2018, 337–346
55. Kol G., Moran Sh., Shpilka A., Yehudayoff A., “Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound”, Comput. Complex., 28:1 (2019), 1–25
•  Number of views: This page: 568 Full text: 134 References: 25 First page: 3