Quantum Advantages of Communication Complexity from Bell Nonlocality

Entropy

Zhih-Ahn Jia¹  Yu-Chun Wu¹  Guang-Can Guo¹  Lu Wei² 

[1] CAS Key Laboratory of Quantum Information, School of Physical Sciences, University of Science and Technology of China, Hefei 230026, China;School of the Gifted Young, University of Science and Technology of China, Hefei 230026, China;

关键词: Bell nonlocality;    entanglement;    communication complexity;   

DOI  :  10.3390/e23060744

来源: DOAJ

【 摘 要 】

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 that encodes the information of each edge can be constructed; then, using this target function, we can construct a CC function, and by pre-sharing entangled states, its success probability exceeds that of the arbitrary classical strategy. The non-signaling protocol based on the Popescu–Rohrlich box is also discussed, and the success probability in this case reaches one.

【 授权许可】

Unknown