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:1007.2952 · International Journal of Foundations of Computer Science

SEPARATION BETWEEN CLASSICAL AND QUANTUM WINNING STRATEGIES FOR THE MATCHING GAME

Ivan Fialík

Published Dec 1, 2008• 1 citation
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. 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.

DOI
10.1142/s0129054108006388

Related papers

Unitary Noise and the Mermin-GHZ 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. 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.

arXiv:1006.1411•Electronic Proceedings in Theoretical Computer Science•Jun 9, 2010•3 citations

Quantum Pseudo-Telepathy

Gilles Brassard, 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•124 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

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

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

Gilles Brassard, 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•47 citations

Programming Telepathy: Implementing Quantum Non-Locality Games

Anya Tafliovich, Eric C. R. Hehner

Quantum pseudo-telepathy is an intriguing phenomenon which results from the application of quantum information theory to communication complexity. To demonstrate this phenomenon researchers in the field of quantum communication complexity devised a number of quantum non-locality games. The setting of these games is as follows: the players are separated so that no communication between them is possible and are given a certain computational task. When the players have access to a quantum resource called entanglement, they can accomplish the task: something that is impossible in a classical setting. To an observer who is unfamiliar with the laws of quantum mechanics it seems that the players employ some sort of telepathy; that is, they somehow exchange information without sharing a communication channel. This paper provides a formal framework for specifying, implementing, and analysing quantum non-locality games.

arXiv:0707.1527•Jul 11, 2007•2 citations
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.
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.
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.
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}.
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.
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.
Quantum pseudo-telepathy is an intriguing phenomenon which results from the application of quantum information theory to communication complexity. To demonstrate this phenomenon researchers in the field of quantum communication complexity devised a number of quantum non-locality games. The setting of these games is as follows: the players are separated so that no communication between them is possible and are given a certain computational task. When the players have access to a quantum resource called entanglement, they can accomplish the task: something that is impossible in a classical setting. To an observer who is unfamiliar with the laws of quantum mechanics it seems that the players employ some sort of telepathy; that is, they somehow exchange information without sharing a communication channel. This paper provides a formal framework for specifying, implementing, and analysing quantum non-locality games.