Entangled simultaneity versus classical interactivity in communication complexity

0525502 - MÚ 2021 RIV US eng J - Journal Article
Gavinsky, Dmitry
Entangled simultaneity versus classical interactivity in communication complexity.
IEEE Transactions on Information Theory. Roč. 66, č. 7 (2020), s. 4641-4651. ISSN 0018-9448. E-ISSN 1557-9654
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : communication complexity * quantum communication * quantum computing
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 2.501, year: 2020
Method of publishing: Limited access
http://dx.doi.org/10.1109/TIT.2020.2976074

In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked whether there existed a function with an efficient quantum one-way protocol, but still no efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function $Shape$ that can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.
Permanent Link: http://hdl.handle.net/11104/0309618