Entangled simultaneity versus classical interactivity in communication complexity

0525502 - MÚ 2021 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: communication complexity * quantum communication * quantum computing
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 2.501, rok: 2020
Způsob publikování: Omezený přístup
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.
Trvalý link: http://hdl.handle.net/11104/0309618