2009/01/08 by Gavinsky, Dmytro · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.0901.0956
openalex publication_date 2009/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(1) by players without entanglement, even if they are allowed to exchange up to k bits in interactive communication for certain k∈Ω(n1/4). These two results give almost the strongest possible (and the strongest known) indication of nonlocal properties of two-party entanglement.