Počet záznamů: 1
Entangled simultaneity versus classical interactivity in communication complexity
- 1.
SYSNO ASEP 0525502 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Entangled simultaneity versus classical interactivity in communication complexity Tvůrce(i) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID Zdroj.dok. IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers - ISSN 0018-9448
Roč. 66, č. 7 (2020), s. 4641-4651Poč.str. 11 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova communication complexity ; quantum communication ; quantum computing Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GBP202/12/G061 GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 000544995900038 EID SCOPUS 85086762372 DOI 10.1109/TIT.2020.2976074 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2021 Elektronická adresa http://dx.doi.org/10.1109/TIT.2020.2976074
Počet záznamů: 1