论文标题
通信复杂性的量子优势来自钟声
Quantum advantages of communication complexity from Bell nonlocality
论文作者
论文摘要
沟通游戏是研究物理理论局限性的关键工具。通信复杂性（CC）问题是一个典型的例子，为此，几个分布式方试图共同计算具有有限经典通信的给定功能。在这项工作中，我们提出了一种以图理论方式从贝尔测试中构建CC问题的方法。从实验兼容性图和相应的贝尔测试功能开始，可以构建编码每个边缘信息的目标函数，然后使用此目标函数，我们可以构建一个CC函数，通过预共享纠缠状态，成功的概率将超过任意经典策略的成功概率。还讨论了基于Popescu-Rohrlich框的非信号协议，在这种情况下的成功概率将达到一个。
Communication games are crucial tools for investigating the limitations of physical theories. The communication complexity (CC) problem is a typical example, for which several distributed parties attempt to jointly calculate a given function with limited classical communications. In this work, we present a method to construct CC problems from Bell tests in a graph-theoretic way. Starting from an experimental compatibility graph and the corresponding Bell test function, a target function which encodes the information of each edge can be constructed, then using this target function we could construct an CC function for which by pre-sharing entangled states, the success probability will exceed that for arbitrary classical strategy. The non-signaling protocol based on Popescu-Rohrlich box is also discussed, and the success probability in this case would reach one.
