Quantum information processing is at the crossroads of physics, mathematics and computer science. It is concerned with that we can and cannot do with quantum information that goes beyond the abilities of classical information processing devices. Communication complexity is an area of classical computer science that aims at quantifying the amount of communication necessary to solve distributed computational problems. Quantum communication complexity uses quantum mechanics to reduce the amount of communication that would be classically required. Pseudo-telepathy is a surprising application of quantum information processing to communication complexity. Thanks to entanglement, perhaps the most nonclassical manifestation of quantum mechanics, two or more quantum players can accomplish a distributed task with no need for communication whatsoever, which would be an impossible feat for classical players. After a detailed overview of the principle and purpose of pseudo-telepathy, we present a survey of recent and no-so-recent work on the subject. In particular, we describe and analyse all the pseudo-telepathy games currently known to the authors. this category are the Mermin-GHZ game and the magic square game, described in Sections 3 and 5, respectively. ♦ If implemented successfully, any one of these games would provide extremely convincing evidence that classical physics does not rule the world for anyone who is already convinced that faster-than-light signalling is impossible (and therefore that it is not because Alice and Bob are able to communicate, however covertly, that they win the game systematically). ♦ The theoretical and experimental study of pseudo-telepathy has the potential to provide the first loophole-free demonstration that the physical world cannot be local realistic. ♦ In introducing the broader field of quantum communication complexity in 1993, Andrew Yao asked if quantum mechanics could be used to reduce the amount of communication required to solve some distributed computational tasks, but he could not answer the question [13] . Surprisingly, a pseudo-telepathic version of this question had already been solved ten years previously [14] by Peter Heywood and Michael Redhead 2 -see Section 2. Please consult [15] for a survey of quantum communication complexity and its interplay with pseudo-telepathy. We are now ready to give a formal definition of pseudo-telepathy. For the sake of simplicity, we define it in the context of two players, Alice and Bob. The generalization to multi-party settings is obvious.
Those are called "pseudo-telepathy games" (see REF and the references therein).
Quantum Pseudo-Telepathy
Proceedings of the 8th International Workshop on Algorithms and Data Structures, Volume 2748 of Lecture Notes in Computer Science
Mathematics Physics