Quantum Pseudo-Telepathy

Michael G. Main

Gilles Brassard A, Anne Broadbent, Alain Tapp

Shan Gao

Alfred Gradenwitz

Viktor Galliard, Stefan Wolf

Quantum entanglement allows for a phenomenon called pseudo-telepathy. This can be used to devise a simple experiment demonstrating the existence of quantum entanglement, provided that the parameters are chosen such that it is impossible to win the game without entanglement or communication (or telepathy). We describe a close connection between pseudo-telepathy and graph coloring and use this to correct previous beliefs on the possibility of doing pseudo-telepathy.

Gilles Brassard A, André Allan Méthot, Alain Tapp

Pseudo-telepathy provides an intuitive way of looking at Bell's inequalities, in which it is often obvious that feats achievable by use of quantum entanglement would be classically impossible. A~two-player pseudo-telepathy game proceeds as follows: Alice and Bob are individually asked a question and they must provide an answer. They are \emph{not} allowed any form of communication once the questions are asked, but they may have agreed on a common strategy prior to the execution of the game. We~say that they \emph{win} the game if the questions and answers fulfil a specific relation. A~game exhibits \emph{pseudo-telepathy} if there is a quantum strategy that makes Alice and Bob win the game for all possible questions, provided they share prior entanglement, whereas it would be impossible to win this game systematically in a classical setting. In~this paper, we show that any two-player pseudo-telepathy game requires the quantum players to share an entangled quantum system of dimension at least~\mbox{$3 \times 3$}. This is optimal for two-player games, but the most efficient pseudo-telepathy game possible, in terms of total dimension, involves \emph{three} players who share a quantum system of dimension~\mbox{$2 \times 2 \times 2$}.