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:2610.06534

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

Itamar Lorian, J. E. Avron

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations• Revised Oct 14, 2026 (v2)
v1 · Oct 5, 2026v2 · Oct 14, 2026
arXivHTMLPDF

Abstract

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.

AI Summary

The paper studies an $N$-player extension of the Mermin–Peres magic square game using a $3\times\cdots\times3$ hypercube. A referee samples a cell uniformly and assigns player $n$ the three-cell line through it parallel to axis $n$. Each player outputs signs whose product is $(-1)^n$; winning requires all outputs at the sampled cell to agree. The optimal classical winning probability is $8/9$ for every $N\ge2$. The upper bound follows by partitioning the hypercube into two-dimensional slices along axes with opposite parity, each requiring at least one disagreement. An explicit construction using separate assignments for odd- and even-numbered players attains the bound. The paper also recursively constructs hypercubes of two-qubit Pauli observables with commuting operators and the required product on every line. For the strategy in which all players measure these prescribed observables, it shows that no shared state guarantees victory when $N\ge3$: perfect agreement would require simultaneous stabilization by anticommuting operators. It reports bounds $1/3\le p_{\mathrm{win}}\le3/4$ for this strategy family. The upper-bound argument uses a spectral calculation bounding three-party consensus for two anticommuting observables; the lower bound uses identical local common eigenstates of one commuting row. These bounds concern the prescribed measurement strategy, not unrestricted quantum strategies, which can reproduce the classical strategy. Stated limitations include studying only one hypercube generalization, restricting measurements to qubit Pauli observables rather than general observables or qudits, and leaving the upper bound nonoptimal.

Little sign of AI-generated textOverclaimsStrong assumptionsPossible error

Error found: The full-distribution 3/4 upper bound requires an omitted averaging argument over anticommuting observable pairs, although that argument repairs the proof. Some body and conclusion statements improperly extend results for the prescribed Pauli-measurement strategy to unrestricted quantum strategies, whose optimal winning probability is necessarily at least the classical 8/9.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
12 paged, 4 figures

Related papers

Extending and Characterizing Quantum Magic Games

Arkhipov, Alex

The Mermin-Peres magic square game is a cooperative two-player nonlocal game in which shared quantum entanglement allows the players to win with certainty, while players limited to classical operations cannot do so, a phenomenon dubbed "quantum pseudo-telepathy". The game has a referee separately ask each player to color a subset of a 3x3 grid. The referee checks that their colorings satisfy certain parity constraints that can't all be simultaneously realized. We define a generalization of these games to be played on an arbitrary arrangement of intersecting sets of elements. We characterize exactly which of these games exhibit quantum pseudo-telepathy, and give quantum winning strategies for those that do. In doing so, we show that it suffices for the players to share three Bell pairs of entanglement even for games on arbitrarily large arrangements. Moreover, it suffices for Alice and Bob to use measurements from the three-qubit Pauli group. The proof technique uses a novel connection of Mermin-style games to graph planarity.

arXiv:1209.3819•Sep 18, 2012•24 citations

Beyond the Magic Square Game: Widening the Gap for Two Bell States

Tony Lau

Prior to this work, the largest known gap between the entangled value and the classical value for a one-round two-player nonlocal game with a perfect entangled strategy using two Bell states of entanglement was $\frac{1}{9}$, achieved by the Mermin-Peres magic square game. A larger gap of $\frac{2}{15}$ has been claimed for the related doily game of Kelleher, Roomy, and Holweck (Quant. Inf. Proc., 2024). However, this value assumes that the classical players use identical local strategies, and we show that dropping this assumption reduces the gap back to $\frac{1}{9}$. We then demonstrate that $\frac{1}{9}$ is not optimal by explicitly constructing a new nonlocal game with gap $\frac{4}{35}$.

quant-pharXiv:2603.20748•Mar 24, 2026•0 citations

The Parallel-Repeated Magic Square Game is Rigid

Matthew Coudron, Anand Natarajan

We show that the $n$-round parallel repetition of the Magic Square game of Mermin and Peres is rigid, in the sense that for any entangled strategy succeeding with probability $1 -\varepsilon$, the players' shared state is $O(\mathrm{poly}(n\varepsilon))$-close to $2n$ EPR pairs under a local isometry. Furthermore, we show that, under local isometry, the players' measurements in said entangled strategy must be $O(\mathrm{poly}(n\varepsilon))$ close to the "ideal" strategy when acting on the shared state.

arXiv:1609.06306•Sep 20, 2016•42 citations

Quantum Advantages in Hypercube Game

He, Xiaoyu, Kun Fang, Xiaoming Sun +1 more

We introduce a novel generalization of the Clauser-Horne-Shimony-Holt (CHSH) game to a multiplayer setting, i.e., Hypercube game, where all $m$ players are required to assign values to vertices on corresponding facets of an $m$-dimensional hypercube. The players win if and only if their answers satisfy both parity and consistency conditions. We completely characterize the maximum winning probabilities (game value) under classical, quantum and no-signalling strategies, respectively. In contrast to the original CHSH game designed to demonstrate the superiority of quantumness, we find that the quantum advantages in the Hypercube game significantly decrease as the number of players increase. Notably, the quantum value decays exponentially fast to the classical value as $m$ increases, while the no-signalling value always remains to be one.

arXiv:1806.02642•Jun 7, 2018•2 citations

Quantum magic rectangles: Characterization and application to certified randomness expansion

Sean A. Adamson, Petros Wallden

The authors generalize the magic square game of Mermin and Peres to arbitrary rectangular dimensions, characterize the optimal quantum strategies, and apply these games in the context of quantum-certified randomness expansion.

arXiv:2008.02370•Physical Review Research•Dec 4, 2020•9 citations

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

Michel Boyer

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.

arXiv:quant-ph/0408090•Aug 13, 2004•15 citations
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.
The paper studies an NNN-player extension of the Mermin–Peres magic square game using a 3×⋯×33\times\cdots\times33×⋯×3 hypercube. A referee samples a cell uniformly and assigns player nnn the three-cell line through it parallel to axis nnn. Each player outputs signs whose product is (−1)n(-1)^n(−1)n; winning requires all outputs at the sampled cell to agree.
The optimal classical winning probability is 8/98/98/9 for every N≥2N\ge2N≥2. The upper bound follows by partitioning the hypercube into two-dimensional slices along axes with opposite parity, each requiring at least one disagreement. An explicit construction using separate assignments for odd- and even-numbered players attains the bound.
The paper also recursively constructs hypercubes of two-qubit Pauli observables with commuting operators and the required product on every line. For the strategy in which all players measure these prescribed observables, it shows that no shared state guarantees victory when N≥3N\ge3N≥3: perfect agreement would require simultaneous stabilization by anticommuting operators. It reports bounds 1/3≤pwin≤3/41/3\le p_{\mathrm{win}}\le3/41/3≤pwin​≤3/4 for this strategy family. The upper-bound argument uses a spectral calculation bounding three-party consensus for two anticommuting observables; the lower bound uses identical local common eigenstates of one commuting row.
These bounds concern the prescribed measurement strategy, not unrestricted quantum strategies, which can reproduce the classical strategy. Stated limitations include studying only one hypercube generalization, restricting measurements to qubit Pauli observables rather than general observables or qudits, and leaving the upper bound nonoptimal.
The Mermin-Peres magic square game is a cooperative two-player nonlocal game in which shared quantum entanglement allows the players to win with certainty, while players limited to classical operations cannot do so, a phenomenon dubbed "quantum pseudo-telepathy". The game has a referee separately ask each player to color a subset of a 3x3 grid. The referee checks that their colorings satisfy certain parity constraints that can't all be simultaneously realized. We define a generalization of these games to be played on an arbitrary arrangement of intersecting sets of elements. We characterize exactly which of these games exhibit quantum pseudo-telepathy, and give quantum winning strategies for those that do. In doing so, we show that it suffices for the players to share three Bell pairs of entanglement even for games on arbitrarily large arrangements. Moreover, it suffices for Alice and Bob to use measurements from the three-qubit Pauli group. The proof technique uses a novel connection of Mermin-style games to graph planarity.
Prior to this work, the largest known gap between the entangled value and the classical value for a one-round two-player nonlocal game with a perfect entangled strategy using two Bell states of entanglement was 19\frac{1}{9}91​, achieved by the Mermin-Peres magic square game. A larger gap of 215\frac{2}{15}152​ has been claimed for the related doily game of Kelleher, Roomy, and Holweck (Quant. Inf. Proc., 2024). However, this value assumes that the classical players use identical local strategies, and we show that dropping this assumption reduces the gap back to 19\frac{1}{9}91​. We then demonstrate that 19\frac{1}{9}91​ is not optimal by explicitly constructing a new nonlocal game with gap 435\frac{4}{35}354​.
We show that the nnn-round parallel repetition of the Magic Square game of Mermin and Peres is rigid, in the sense that for any entangled strategy succeeding with probability 1−ε1 -\varepsilon1−ε, the players' shared state is O(poly(nε))O(\mathrm{poly}(n\varepsilon))O(poly(nε))-close to 2n2n2n EPR pairs under a local isometry. Furthermore, we show that, under local isometry, the players' measurements in said entangled strategy must be O(poly(nε))O(\mathrm{poly}(n\varepsilon))O(poly(nε)) close to the "ideal" strategy when acting on the shared state.
We introduce a novel generalization of the Clauser-Horne-Shimony-Holt (CHSH) game to a multiplayer setting, i.e., Hypercube game, where all mmm players are required to assign values to vertices on corresponding facets of an mmm-dimensional hypercube. The players win if and only if their answers satisfy both parity and consistency conditions. We completely characterize the maximum winning probabilities (game value) under classical, quantum and no-signalling strategies, respectively. In contrast to the original CHSH game designed to demonstrate the superiority of quantumness, we find that the quantum advantages in the Hypercube game significantly decrease as the number of players increase. Notably, the quantum value decays exponentially fast to the classical value as mmm increases, while the no-signalling value always remains to be one.
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.