Classical Interaction Cannot Replace Quantum Nonlocality

Abstract

We present a two-player communication task that can be solved by a protocol of polylogarithmic cost in the simultaneous message passing model with classical communication and shared entanglement, but requires exponentially more communication in the classical interactive model. Our second result is a two-player nonlocality game with input length $n$ and output of polylogarithmic length, that can be won with probability 1-o(1) by players sharing polylogarithmic amount of entanglement. On the other hand, the game is lost with probability $\Omega (1)$ by players without entanglement, even if they are allowed to exchange up to k bits in interactive communication for certain $k\in \Omega (n^{1/4})$. These two results give almost the strongest possible (and the strongest known) indication of nonlocal properties of two-party entanglement.

References in corpus (1)

• Combinatorics and Quantum Nonlocality

Cited by in corpus (4)

• Non-locality and Communication Complexity
• The communication complexity of non-signaling distributions
• Better Non-Local Games from Hidden Matching
• Tripartite probability distributions and communication complexity