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]  
Bar-Yossef Ziv, 2004, P 36 S THEORY COMPUT, P128, DOI DOI 10.1145/1007352.1007379
[3]  
Buhrman H., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P63, DOI 10.1145/276698.276713
[4]   Quantum fingerprinting [J].
Buhrman, H ;
Cleve, R ;
Watrous, J ;
de Wolf, R .
PHYSICAL REVIEW LETTERS, 2001, 87 (16)
[5]   Nonlocality and communication complexity [J].
Buhrman, Harry ;
Cleve, Richard ;
Massar, Serge ;
de Wolf, Ronald .
REVIEWS OF MODERN PHYSICS, 2010, 82 (01) :665-698
[6]  
Chakrabarti A, 2011, ACM S THEORY COMPUT, P51
[7]   Entangled Simultaneity Versus Classical Interactivity in Communication Complexity [J].
Gavinsky, Dmitry .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (07) :4641-4651
[8]   Quantum Versus Classical Simultaneity in Communication Complexity [J].
Gavinsky, Dmitry .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (10) :6466-6483
[9]   EXPONENTIAL SEPARATION FOR ONE-WAY QUANTUM COMMUNICATION COMPLEXITY, WITH APPLICATIONS TO CRYPTOGRAPHY [J].
Gavinsky, Dmitry ;
Kempe, Julia ;
Kerenidis, Iordanis ;
Raz, Ran ;
De Wolf, Ronald .
SIAM JOURNAL ON COMPUTING, 2008, 38 (05) :1695-1708
[10]  
Gavinsky D, 2008, ACM S THEORY COMPUT, P95
12