Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

The impossibility of pseudotelepathy without quantum entanglement

Viktor Galliard, Alain Tapp, Stefan Wolf

Published Jan 1, 2003• 23 citations
Publisher

Abstract

In a pseudotelepathy game, communication can be entirely replaced by quantum entanglement. We provide, for the first proposed arid simplest two-player game of this type, the proof that communication is indeed necessary to win with certainty if no quantum entanglement is shared by the players. This completes the game's analysis and shows its "pseudotelepathic" properties.

DOI
10.1109/isit.2003.1228474

Related papers

The Impossibility of Pseudo-Telepathy Without Quantum Entanglement

Viktor Galliard, Stefan Wolf, Alain Tapp

Imagine that Alice and Bob, unable to communicate, are both given a 16-bit string such that the strings are either equal, or they differ in exactly 8 positions. Both parties are then supposed to output a 4-bit string in such a way that these short strings are equal if and only if the original longer strings given to them were equal as well. It is known that this task can be fulfilled without failure and without communication if Alice and Bob share 4 maximally entangled quantum bits. We show that, on the other hand, they CANNOT win the same game with certainty if they only share classical bits, even if it is an unlimited number. This means that for fulfilling this particular distributed task, quantum entanglement can completely replace communication. This phenomenon has been called pseudo-telepathy. The results of this paper complete the analysis of the first proposed game of this type between two players.

arXiv:quant-ph/0211011•Nov 4, 2002•23 citations

On the power of multipartite entanglement for pseudotelepathy

Gilles Brassard, Xavier Coiteux-Roy, Rémi Ligez

As early as 1935, Schrödinger recognized entanglement as ``not one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought''. Indeed, most remarkable phenomena in quantum information science, such as quantum computing and quantum teleportation, spring from clever uses of entanglement. Among them, pseudotelepathy enables two or more players to win systematically at some cooperative games with no need for communication between them, a restriction that would make the task impossible in a classical world. We investigate the power of multipartite entanglement for pseudotelepathy. Some known games that can be won with tripartite entanglement cannot be won with bipartite entanglement, but they can be won with bipartite nonsignalling resources such as the so-called Popescu--Rohrlich nonlocal box. We exhibit a five-player game that can be won with tripartite entanglement, but not with arbitrary bipartite nonsignalling resources even in the presence of arbitrary five-partite classical resources. This illustrates both the power of bipartite nonsignalling resources (over bipartite entanglement) and the even superior power of tripartite entanglement.

quant-pharXiv:2603.17956•Proceedings of the National Academy of Sciences•Mar 19, 2026•0 citations

Minimum entangled state dimension required for pseudo-telepathy

Gilles Brassard, 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$}.

arXiv:quant-ph/0412136•Quantum Information and Computation•Jul 1, 2005•36 citations

Two Party Pseudo Telepathy Games

Indranil Chakrabarty

In this work we have introduced two party pseudo telepathy games with respective winning conditions. One cannot win these games deterministically by any kind of classical protocols. Interestingly we find out that in quantum world, these winning conditions can be achieved if the players share an entangled state. We also introduced a game which is impossible to win if the players are form classical world, (both probabilistically and deterministically) yet there exists a perfect quantum strategy by following which, one can attain the winning condition of the game.

•Dec 28, 2006•1 citation

Two theorems of Jhon Bell and Communication Complexity

Guruprasad Kar

John Bell taught us that quantum mechanics can not be reproduced by non-contextual and local Hidden variable theory. The impossibility of replacing quantum mechanics by non-contextual Hidden Variable Theory can be turned to a impossible coloring pseudo-telepathy game to be played by two distant players. The game can not be won without communication in the classical world. But if the players share entangled state (quantum correlation) the game can be won deterministically using no communication. This again shows that though quantum correlation can not be used for communication, two parties can not simulate quantum correlation without classical communication. The motivation of the article is to present the earlier works on Hidden Variable Theory and recently developed pseudo-telepathy problem in a simpler way, which may be helpful for the beginners in this area.

arXiv:quant-ph/0504191•Apr 26, 2005•2 citations

Quantum Computation and Pseudotelepathic Games

Jeffrey Bub

A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game).

arXiv:1005.2449•Philosophy of Science•Oct 1, 2008•4 citations
In a pseudotelepathy game, communication can be entirely replaced by quantum entanglement. We provide, for the first proposed arid simplest two-player game of this type, the proof that communication is indeed necessary to win with certainty if no quantum entanglement is shared by the players. This completes the game's analysis and shows its "pseudotelepathic" properties.
Imagine that Alice and Bob, unable to communicate, are both given a 16-bit string such that the strings are either equal, or they differ in exactly 8 positions. Both parties are then supposed to output a 4-bit string in such a way that these short strings are equal if and only if the original longer strings given to them were equal as well. It is known that this task can be fulfilled without failure and without communication if Alice and Bob share 4 maximally entangled quantum bits. We show that, on the other hand, they CANNOT win the same game with certainty if they only share classical bits, even if it is an unlimited number. This means that for fulfilling this particular distributed task, quantum entanglement can completely replace communication. This phenomenon has been called pseudo-telepathy. The results of this paper complete the analysis of the first proposed game of this type between two players.
As early as 1935, Schrödinger recognized entanglement as ``not one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought''. Indeed, most remarkable phenomena in quantum information science, such as quantum computing and quantum teleportation, spring from clever uses of entanglement. Among them, pseudotelepathy enables two or more players to win systematically at some cooperative games with no need for communication between them, a restriction that would make the task impossible in a classical world. We investigate the power of multipartite entanglement for pseudotelepathy. Some known games that can be won with tripartite entanglement cannot be won with bipartite entanglement, but they can be won with bipartite nonsignalling resources such as the so-called Popescu--Rohrlich nonlocal box. We exhibit a five-player game that can be won with tripartite entanglement, but not with arbitrary bipartite nonsignalling resources even in the presence of arbitrary five-partite classical resources. This illustrates both the power of bipartite nonsignalling resources (over bipartite entanglement) and the even superior power of tripartite entanglement.
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×33 \times 33×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×2×22 \times 2 \times 22×2×2}.
In this work we have introduced two party pseudo telepathy games with respective winning conditions. One cannot win these games deterministically by any kind of classical protocols. Interestingly we find out that in quantum world, these winning conditions can be achieved if the players share an entangled state. We also introduced a game which is impossible to win if the players are form classical world, (both probabilistically and deterministically) yet there exists a perfect quantum strategy by following which, one can attain the winning condition of the game.
John Bell taught us that quantum mechanics can not be reproduced by non-contextual and local Hidden variable theory. The impossibility of replacing quantum mechanics by non-contextual Hidden Variable Theory can be turned to a impossible coloring pseudo-telepathy game to be played by two distant players. The game can not be won without communication in the classical world. But if the players share entangled state (quantum correlation) the game can be won deterministically using no communication. This again shows that though quantum correlation can not be used for communication, two parties can not simulate quantum correlation without classical communication. The motivation of the article is to present the earlier works on Hidden Variable Theory and recently developed pseudo-telepathy problem in a simpler way, which may be helpful for the beginners in this area.
A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game).