2011/12/13 by Andris Ambainis, Artūrs Bačkurs, Ambainis, Andris +11
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1112.2856
14 pages
arxiv created 2011/12/13 · openalex publication_date 2011/12/13 · arxiv updated 2011/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input xi to the ith player who then responds by sending an answer ai to the referee. The players win if the answers ai satisfy a condition that may depend on the inputs xi. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study of non-local games in a worst-case scenario when the referee's probability distribution is unknown and study several non-local games in this scenario.