Pseudo-Telepathy Games

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

FIALÍK Ivan

Year of publication 2012
Type Chapter of a book
MU Faculty or unit

Faculty of Informatics

Citation
Description Quantum information processing deals with harnessing laws and phenomena of the quantum world for computation. It especially studies what they enable us to do which goes beyond the abilities of classical information processing. Communication complexity of some distributed computational problems can be reduced with the help of quantum information processing. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. Such problems are often described using a terminology of the game theory and they are usually called pseudo-telepathy games. A pseudotelepathy game is a two party game for which there is no classical winning strategy, but there is a winning strategy based on sharing quantum entanglement by the players. Thus, a pseudotelepathy game can be seen as a distributed problem that can be solved using quantum entanglement without any form of direct communication between the parties. Moreover, pseudotelepathy games can be used to demonstrate that the physical world is not local realistic. After introducing a general model for pseudo-telepathy games, we intend to give a systematic survey of known pseudo-telepathy games and results concerning individual games as well as pseudo-telepathy in general. We also review several important open problems of the theory of pseudo-telepathy games.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.