Quantum Versus Classical Simultaneity in Communication Complexity
Quantum Versus Classical Simultaneity in Communication Complexity
复制标题
通信复杂性中的量子与经典同时性
DOI：
10.1109/tit.2019.2918453
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
Dmitry Gavinsky
中科院分区：
文献类型：
--
作者：
Dmitry Gavinsky
本文研究了双方通信环境下的两个问题：功能复杂性。首先，总结了量子通信在三种最常见的通信“布局”：双向交互通信、单向通信和同步消息传递（SMP）中具有质的优势的研究路线。我演示了一个函数问题<inline-formula> < text -math notation="LaTeX"> $ { \widetilde {cEq}_{T}}$ </ text -math></inline-formula>，其通信复杂度在量子版本的SMP中为<inline-formula> < text -math notation="LaTeX"> $O\left ({(\log n)^{2}}\right )$ </ text -math></inline-formula>，在经典（随机）版本的SMP中为<inline-formula> < text -math notation="LaTeX"> $\tilde \Omega \left ({ \sqrt {n}}\right )$ </ text -math></inline-formula>。其次，本文有助于理解量子通信中最弱的通常被研究的机制-具有量子信息且没有共享随机性的smp（后者的限制可以被视为使量子模型“尽可能弱”的某种人为方式）的能力。我们的函数<inline-formula> < text -math notation="LaTeX"> $ { \widetilde {cEq}_{T}}$ </ text -math></inline-formula>在这种情况下也有一个有效的解，这意味着即使缺乏共享随机性，量子SMP也可以比具有共享随机性的经典SMP指数强。
This paper addresses two problems in the context of two-party communication complexity of functions. First, it concludes the line of research which can be viewed as demonstrating qualitative advantage of quantum communication in the three most common communication “layouts”: two-way interactive communication, one-way communication and simultaneous message passing (SMP). I demonstrate a functional problem <inline-formula> <tex-math notation="LaTeX">$ { \widetilde {cEq}_{T}}$ </tex-math></inline-formula>, whose communication complexity is <inline-formula> <tex-math notation="LaTeX">$O\left ({(\log n)^{2}}\right )$ </tex-math></inline-formula> in the quantum version of the SMP and <inline-formula> <tex-math notation="LaTeX">$\tilde \Omega \left ({ \sqrt {n}}\right )$ </tex-math></inline-formula> in the classical (randomized) version of SMP. Second, this paper contributes to understanding the power of the weakest commonly studied regime of quantum communication–SMP with quantum messages and without shared randomness (the latter restriction can be viewed as a somewhat artificial way of making the quantum model “as weak as possible”). Our function <inline-formula> <tex-math notation="LaTeX">$ { \widetilde {cEq}_{T}}$ </tex-math></inline-formula> has an efficient solution in this regime as well, which means that even lacking shared randomness, quantum SMP can be exponentially stronger than its classical counterpart with shared randomness.