Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity

被引：0
作者：
Gavinsky, Dmitry [1 ]
机构：
[1] Czech Acad Sci, Inst Math, Prague 11567, Czech Republic
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2021年 / 67卷 / 10期
基金：
新加坡国家研究基金会;
关键词：
Protocols; Switched mode power supplies; Quantum mechanics; Quantum entanglement; Quantum computing; Complexity theory; Random variables; Communication complexity; quantum communication; quantum computing;
D O I：
10.1109/TIT.2021.3050528
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
引用
收藏
页码：6583 / 6605
页数：23
相关论文
共 17 条
[1]   FAST PROBABILISTIC ALGORITHMS FOR HAMILTONIAN CIRCUITS AND MATCHINGS [J].
ANGLUIN, D ;
VALIANT, LG .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) :155-193
[2]  
[Anonymous], 1996, Communication complexity
[3]  
[Anonymous], 1934, Logik der Forschung. Zur Erkenntnistheorie der modernen Naturwissenschaft
[4]  
Bar-Yossef Z., 2004, P 36 ANN ACM S THEOR, P128, DOI [DOI 10.1145/1007352.1007379, 10.1137/060651835, DOI 10.1137/060651835, 10.1145/1007352.1007379]
[5]  
Buhrman H., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P63, DOI 10.1145/276698.276713
[6]   Quantum fingerprinting [J].
Buhrman, H ;
Cleve, R ;
Watrous, J ;
de Wolf, R .
PHYSICAL REVIEW LETTERS, 2001, 87 (16)
[7]   Nonlocality and communication complexity [J].
Buhrman, Harry ;
Cleve, Richard ;
Massar, Serge ;
de Wolf, Ronald .
REVIEWS OF MODERN PHYSICS, 2010, 82 (01) :665-698
[8]  
Chakrabarti A, 2011, ACM S THEORY COMPUT, P51
[9]   Entangled Simultaneity Versus Classical Interactivity in Communication Complexity [J].
Gavinsky, Dmitry .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (07) :4641-4651
[10]   Quantum Versus Classical Simultaneity in Communication Complexity [J].
Gavinsky, Dmitry .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (10) :6466-6483
12