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:quant-ph/0408090

Extended GHZ n-player games with classical probability of winning tending to 0

Michel Boyer

Published Aug 13, 2004• 9 citations
arXivHTMLPDF

Abstract

In 1990, Mermin presented a n player game that is won with certainty using n spin-1/2 particles in a GHZ state whilst no classical strategy (or local theory) can win with probability higher than ${1/2} + \frac{1}{2^{\lceil n/2 \rceil}}$ (which is larger than 1/2). This article first introduces a class of arithmetic games containing Mermin's and gives a quantum algorithm based on a generalized n party GHZ state that wins those games with certainty. It is then proved for a subclass of those games where each player is given a single bit of input that no classical strategy can win with a probability that is asymptotically larger than 1.6 times the inverse of the square root of n, thus giving a new and stronger Bell inequality.

DOI
10.48550/arxiv.quant-ph/0408090

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

The Mermin-Peres Magic Square Game With Three or More Players

Itamar Lorian, J. E. Avron

We present a generalization of the Mermin-Peres magic square game to $N$ players, in which the square is replaced by an $N$-dimensional hypercube. We show that the winning probability of the optimal classical strategy remains $8/9$ for all $N$, while for $N \ge 3$, a generalization of the quantum strategy for $N = 2$ achieves a winning probability between $1/3$ and $3/4$. This loss of quantum advantage for $N \ge 3$ is a consequence of monogamy.

quant-pharXiv:2610.06534•Oct 6, 2026•0 citations

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa +1 more

Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•47 citations

Quantum minority game utilizing various forms of entanglement

Adrian P. Flitney, Lloyd C. L. Hollenberg

The quantum Minority game provides a means of studying the effect of multi-partite entanglement in a game theoretic setting. We study symmetric Nash equilibria and symmetric Pareto optimal strategies arising in a four-player quantum Minority game that uses an initial state that is a superposition of a GHZ state and products of EPR pairs. We find that the payoff curve for the symmetric Pareto optimal strategy is the same as that for the maximal violation of the Mermin-Ardehali-Belinskii-Klyshko inequality for the initial state, indicating a correspondence between quantum game theory and Bell inequalities. We also show that no advantage over the classical Minority game can be obtained when the initial state has only two party entanglement.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Dec 3, 2007•4 citations

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•2 citations

Parallel Repetition for the GHZ Game: A Simpler Proof

Uma Girish, Justin Holmgren, Mittal, Kunal +2 more

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-Ω(1)}$. This was first established by Holmgren and Raz [HR20]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [GHZ89] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [DHVY17] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

arXiv:2107.06156•Jul 13, 2021•0 citations
In 1990, Mermin presented a n player game that is won with certainty using n spin-1/2 particles in a GHZ state whilst no classical strategy (or local theory) can win with probability higher than 1/2+12⌈n/2⌉{1/2} + \frac{1}{2^{\lceil n/2 \rceil}}1/2+2⌈n/2⌉1​ (which is larger than 1/2). This article first introduces a class of arithmetic games containing Mermin's and gives a quantum algorithm based on a generalized n party GHZ state that wins those games with certainty. It is then proved for a subclass of those games where each player is given a single bit of input that no classical strategy can win with a probability that is asymptotically larger than 1.6 times the inverse of the square root of n, thus giving a new and stronger Bell inequality.
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.
We present a generalization of the Mermin-Peres magic square game to NNN players, in which the square is replaced by an NNN-dimensional hypercube. We show that the winning probability of the optimal classical strategy remains 8/98/98/9 for all NNN, while for N≥3N \ge 3N≥3, a generalization of the quantum strategy for N=2N = 2N=2 achieves a winning probability between 1/31/31/3 and 3/43/43/4. This loss of quantum advantage for N≥3N \ge 3N≥3 is a consequence of monogamy.
Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.
The quantum Minority game provides a means of studying the effect of multi-partite entanglement in a game theoretic setting. We study symmetric Nash equilibria and symmetric Pareto optimal strategies arising in a four-player quantum Minority game that uses an initial state that is a superposition of a GHZ state and products of EPR pairs. We find that the payoff curve for the symmetric Pareto optimal strategy is the same as that for the maximal violation of the Mermin-Ardehali-Belinskii-Klyshko inequality for the initial state, indicating a correspondence between quantum game theory and Bell inequalities. We also show that no advantage over the classical Minority game can be obtained when the initial state has only two party entanglement.
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.
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the nnn-fold GHZ game is at most n−Ω(1)n^{-Ω(1)}n−Ω(1). This was first established by Holmgren and Raz [HR20]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [GHZ89] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [DHVY17] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.