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

arXiv:1006.1411 · Electronic Proceedings in Theoretical Computer Science

Unitary Noise and the Mermin-GHZ Game

Ivan Fialík

Published Jun 9, 2010• 2 citations
arXivHTMLPDF

Abstract

Communication complexity is an area of classical computer science which studies how much communication is necessary to solve various distributed computational problems. Quantum information processing can be used to reduce the amount of communication required to carry out some distributed problems. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. Since it is generally very hard to perfectly implement a quantum winning strategy for a pseudo-telepathy game, quantum players are almost certain to make errors even though they use a winning strategy. After introducing a model for pseudo-telepathy games, we investigate the impact of erroneously performed unitary transformations on the quantum winning strategy for the Mermin-GHZ game. The question of how strong the unitary noise can be so that quantum players would still be better than classical ones is also dealt with.

DOI
10.4204/eptcs.25.18

Related papers

Noise and the Mermin-GHZ Game

Ivan Fialík

A pseudo-telepathy game is a game for two or more players for which there is no classical winning strategy, but there is a winning strategy based on sharing quantum entanglement by the players. Since it is generally very hard to perfectly implement a quantum winning strategy for a pseudo-telepathy game, quantum players are almost certain to make errors even though they use a winning strategy. After introducing a model for pseudo-telepathy games, we investigate the impact of several basic noisy quantum channels on the quantum winning strategy for the Mermin-GHZ game. The question of how strong the noise can be so that quantum players would still be better than classical ones is also dealt with.

Electronic Notes in Theoretical Computer Science•Sep 1, 2009•1 citation

SEPARATION BETWEEN CLASSICAL AND QUANTUM WINNING STRATEGIES FOR THE MATCHING GAME

Ivan Fialík

Communication complexity is an area of classical computer science which studies how much communication is necessary to solve various distributed computational problems. Quantum information processing can be used to reduce the amount of communication required to carry out some distributed problems. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. The matching game is the newest member of the family of pseudo-telepathy games. After introducing a general model for pseudo-telepathy games, we focus on the question what the smallest size of inputs is for which the matching game is a pseudo-telepathy game.

arXiv:1007.2952•International Journal of Foundations of Computer Science•Dec 1, 2008•1 citation

Quantum Pseudo-Telepathy

Gilles Brassard A, Anne Broadbent, Alain Tapp

Abstract. 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. 1.

•Jan 1, 2004•123 citations

Recasting Mermin's multi-player game into the framework of pseudo-telepathy

Gilles Brassard A, Anne Broadbent, Alain Tapp

Entanglement is perhaps the most non-classical manifestation of quantum \mbox{mechanics}. Among its many interesting applications to information processing, it can be harnessed to \emph{reduce} the amount of communication required to process a variety of distributed computational tasks. Can it be used to eliminate communication altogether? Even though it cannot serve to signal information between remote parties, there are distributed tasks that can be performed without any need for communication, provided the parties share prior entanglement: this is the realm pseudo-telepathy. One of the earliest uses of multi-party entanglement was presented by Mermin in 1990. Here we recast his idea in terms of pseudo-telepathy: we provide a new computer-scientist-friendly analysis of this game. We prove an upper bound on the best possible classical strategy for attempting to play this game, as well as a novel, matching lower bound. This leads us to considerations on how well imperfect quantum-mechanical apparatus must perform in order to exhibit a behaviour that would be classically impossible to explain. Our results include improved bounds that could help vanquish the infamous detection loophole.

arXiv:quant-ph/0408052•Quantum Information and Computation•Nov 1, 2005•35 citations

Quantum Computer Simulations of Quantum Pseudo-Telepathy (QPT) for the Greenberger-Horne-Zeilinger (GHZ) Game

Thomas H. Yang, Weiguo Yang

Ongoing development and increased accessibility of quantum computing has allowed for broadly replicable demonstrations of previously theoretical formulated quantum games and thought experiments, simulated as well as across different quantum platforms. Quantum pseudo-telepathy (QPT) is one such unintuitive result, where the prior quantum entanglement of states can forego the need for classical communication to successfully complete simultaneously coordinated tasks. The Greenberger-Horne-Zeilinger (GHZ) game is one such demonstration of QPT by posing a particular three-player question game where a quantum strategy utilizing entangled states outperforms the best classical strategy. Through the use of OpenQASM 2.0 and IBM Quantum Platform, the entangled states with winning quantum strategies of the GHZ game are implemented, demonstrating the efficacies of a quantum strategy of 100% probability of winning in contrast to the 75% maximal winning probability of any classical strategy. Potential applications based on this winning quantum strategy of the GHZ game such as zero-knowledge shared authentication are also discussed.

IEEE SoutheastCon•Mar 22, 2025•0 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
Communication complexity is an area of classical computer science which studies how much communication is necessary to solve various distributed computational problems. Quantum information processing can be used to reduce the amount of communication required to carry out some distributed problems. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. Since it is generally very hard to perfectly implement a quantum winning strategy for a pseudo-telepathy game, quantum players are almost certain to make errors even though they use a winning strategy. After introducing a model for pseudo-telepathy games, we investigate the impact of erroneously performed unitary transformations on the quantum winning strategy for the Mermin-GHZ game. The question of how strong the unitary noise can be so that quantum players would still be better than classical ones is also dealt with.
A pseudo-telepathy game is a game for two or more players for which there is no classical winning strategy, but there is a winning strategy based on sharing quantum entanglement by the players. Since it is generally very hard to perfectly implement a quantum winning strategy for a pseudo-telepathy game, quantum players are almost certain to make errors even though they use a winning strategy. After introducing a model for pseudo-telepathy games, we investigate the impact of several basic noisy quantum channels on the quantum winning strategy for the Mermin-GHZ game. The question of how strong the noise can be so that quantum players would still be better than classical ones is also dealt with.
Communication complexity is an area of classical computer science which studies how much communication is necessary to solve various distributed computational problems. Quantum information processing can be used to reduce the amount of communication required to carry out some distributed problems. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. The matching game is the newest member of the family of pseudo-telepathy games. After introducing a general model for pseudo-telepathy games, we focus on the question what the smallest size of inputs is for which the matching game is a pseudo-telepathy game.
Abstract. 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. 1.
Entanglement is perhaps the most non-classical manifestation of quantum \mbox{mechanics}. Among its many interesting applications to information processing, it can be harnessed to \emph{reduce} the amount of communication required to process a variety of distributed computational tasks. Can it be used to eliminate communication altogether? Even though it cannot serve to signal information between remote parties, there are distributed tasks that can be performed without any need for communication, provided the parties share prior entanglement: this is the realm pseudo-telepathy. One of the earliest uses of multi-party entanglement was presented by Mermin in 1990. Here we recast his idea in terms of pseudo-telepathy: we provide a new computer-scientist-friendly analysis of this game. We prove an upper bound on the best possible classical strategy for attempting to play this game, as well as a novel, matching lower bound. This leads us to considerations on how well imperfect quantum-mechanical apparatus must perform in order to exhibit a behaviour that would be classically impossible to explain. Our results include improved bounds that could help vanquish the infamous detection loophole.
Ongoing development and increased accessibility of quantum computing has allowed for broadly replicable demonstrations of previously theoretical formulated quantum games and thought experiments, simulated as well as across different quantum platforms. Quantum pseudo-telepathy (QPT) is one such unintuitive result, where the prior quantum entanglement of states can forego the need for classical communication to successfully complete simultaneously coordinated tasks. The Greenberger-Horne-Zeilinger (GHZ) game is one such demonstration of QPT by posing a particular three-player question game where a quantum strategy utilizing entangled states outperforms the best classical strategy. Through the use of OpenQASM 2.0 and IBM Quantum Platform, the entangled states with winning quantum strategies of the GHZ game are implemented, demonstrating the efficacies of a quantum strategy of 100% probability of winning in contrast to the 75% maximal winning probability of any classical strategy. Potential applications based on this winning quantum strategy of the GHZ game such as zero-knowledge shared authentication are also discussed.
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.