Buhrman Harry, Czekaj Łukasz, Grudka Andrzej, Horodecki Michał, Horodecki Paweł, Markiewicz Marcin, Speelman Florian, Strelchuk Sergii
Algorithms and Complexity Unit, Centrum Wiskunde & Informatica, 1098 XG Amsterdam, The Netherlands; Department of Computer Science, University of Amsterdam, 1012 WX Amsterdam, The Netherlands; QuSoft, 1098 XG Amsterdam, The Netherlands;
Faculty of Mathematics, Physics and Informatics, Gdańsk University, 80-952 Gdańsk, Poland;
Proc Natl Acad Sci U S A. 2016 Mar 22;113(12):3191-6. doi: 10.1073/pnas.1507647113. Epub 2016 Mar 8.
We obtain a general connection between a large quantum advantage in communication complexity and Bell nonlocality. We show that given any protocol offering a sufficiently large quantum advantage in communication complexity, there exists a way of obtaining measurement statistics that violate some Bell inequality. Our main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs.
我们获得了通信复杂性方面的巨大量子优势与贝尔非定域性之间的一般联系。我们表明，给定任何在通信复杂性方面提供足够大量子优势的协议，都存在一种获得违反某些贝尔不等式的测量统计量的方法。我们的主要工具是基于端口的量子隐形传态。如果量子与经典通信复杂性之间的差距可以任意增大，那么随着输入和输出数量的增加，贝尔量的量子值与经典值之比将变得无界。
