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

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

Tony Lau

quant-phSubmitted Mar 21, 2026• Announced Mar 24, 2026• 0 citations• Revised Aug 31, 2026 (v2)
v1 · Mar 21, 2026v2 · Aug 31, 2026
arXivHTMLPDF

Abstract

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}$.

Comments
24 pages, 10 figures, 4 tables

Related papers

An explicit nonlocal game of quantum value one that needs exponential entanglement

Nidhal Mghirbi, Seth Douglas

How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with $1687$ equations in $1993$ variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability $1-\varepsilon$ needs entanglement entropy $\varepsilon^{-1+o(1)}$, hence local dimension $\exp(\varepsilon^{-1+o(1)})$. The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension $\exp(C\varepsilon^{-1}\log(1/\varepsilon))$ suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in $1/\varepsilon$. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision $\sqrt\varepsilon$, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of $\varepsilon$ is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH$(n)$ games need $\Theta(\min(n,1/\varepsilon))$ ebits, and the linear system game of Slofstra and Vidick needs local dimension $\Theta(\varepsilon^{-1/2})$.

•Oct 27, 2026•2 citations

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa +1 more

Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” 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 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 $\frac{1}{2}$ by at most $O((\log n)/\sqrt{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 the game to be won with probability $1/(\log n)^2$, while the best winning probability without entanglement is $1/n$. This near-linear ratio is almost 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. An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity, pages 157--166, 2011.

arXiv:1012.5043•Theory of Computing•Jan 1, 2012•33 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•48 citations

Quantitative comparison of quantum pseudo-telepathy games and Bell inequalities

Gábor Homa, András Bodor, József Zsolt Bernád

Abstract Quantum pseudo-telepathy games, such as the Mermin–Peres magic square and the doily game (DG), theoretically allow players to win with unit probability when using entangled quantum strategies. We quantitatively characterize the quantum advantage in these games and compare it with violations of two Bell inequalities: the Clauser–Horne–Shimony–Holt and the Collins–Gisin inequalities. The analysis is restricted to two families of two-qubit states: modified Werner states and Bell-diagonal states. For each case, we identify and quantify the regions of quantum state space that exhibit either a quantum advantage or a Bell inequality violation, relative to the set of all entangled states. Within these families, the DG encompasses a larger fraction of entangled states than the Mermin–Peres magic square game, although both cover significantly smaller regions of entangled states compared to those where Bell inequalities are violated. Although both approaches are fundamentally linked to quantum contextuality, our analysis of the examined two-qubit state families suggests that Bell inequalities are more effective at revealing entanglement, even if pseudo-telepathy games offer a more intuitive and conceptually appealing perspective.

arXiv:2509.18033•Journal of Physics A Mathematical and Theoretical•Jan 27, 2026•1 citation

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

The price of precision: usable entanglement in nonlocal games and the geometry of groups

Seth Douglas, Nidhal Mghirbi

In a nonlocal game of quantum value one that no finite-dimensional strategy wins, near-perfect play needs growing dimension, which separable states can have. We ask how much usable entanglement it needs: the demand at loss $\varepsilon$ is the least one-way distillable entanglement of the original state of a strategy of loss at most $\varepsilon$. For synchronous games with tested diagonals and for constraint-variable consistency games, demand diverges exactly when no finite-dimensional strategy is perfect; then, for any number of Bell pairs and any fidelity below one, every sufficiently good mixed strategy yields that many at that fidelity by local isometries. For rational synchronous or binary constraint games, a loss guaranteeing this is computable under a promise, but boundedness of demand is undecidable among games of value one. Demand is at least logarithmic if near-winners have a sign relation and an even dilation mirrored by both players, as in a game from Abels' group. For agreement games the directions agree up to a factor three in loss, optimal among Bob-fixed deterministic local symmetrizations. The geometry of the group behind a game, not its presentation, sets the rates. Fixed games demand $\alpha\log(1/\varepsilon)$ for every $\alpha=\frac12\sum_i\log_{m_i}q_i$ with $q_i\ge2$ a power of two dividing $m_i$, a dense set containing all positive rationals and some transcendentals, such as $\frac12\log_62$; a configuration-lamp game demands $\varepsilon^{-1+o(1)}$; Pauli lamps on the points of Houghton's three rays give demand between $\varepsilon^{-0.0690}$ and $\varepsilon^{-1/4}$. If group relations hold exactly and Alice matches Bob to error $e$, demand counts qubits addressable by short words: $\Theta(1/e)$, $\Theta(e^{-k})$ for integers $k\ge1$, or $2^{\Theta(1/e)}$. Conditional on our attainment and tail bounds, the $I_{3322}$ optimum needs bounded usable entanglement.

•Oct 27, 2026•3 citations
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​.
How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with 168716871687 equations in 199319931993 variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability 1−ε1-\varepsilon1−ε needs entanglement entropy ε−1+o(1)\varepsilon^{-1+o(1)}ε−1+o(1), hence local dimension exp⁡(ε−1+o(1))\exp(\varepsilon^{-1+o(1)})exp(ε−1+o(1)). The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension exp⁡(Cε−1log⁡(1/ε))\exp(C\varepsilon^{-1}\log(1/\varepsilon))exp(Cε−1log(1/ε)) suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in 1/ε1/\varepsilon1/ε. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision ε\sqrt\varepsilonε​, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of ε\varepsilonε is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH(n)(n)(n) games need Θ(min⁡(n,1/ε))\Theta(\min(n,1/\varepsilon))Θ(min(n,1/ε)) ebits, and the linear system game of Slofstra and Vidick needs local dimension Θ(ε−1/2)\Theta(\varepsilon^{-1/2})Θ(ε−1/2).
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” 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 strategy using a maximally entangled state with local dimension nnn (e.g., log⁡n\log nlogn EPR-pairs), while we show that the winning probability of any classical strategy differs from 12\frac{1}{2}21​ by at most O((log⁡n)/n)O((\log n)/\sqrt{n})O((logn)/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 nnn-dimensional entanglement allows the game to be won with probability 1/(log⁡n)21/(\log n)^21/(logn)2, while the best winning probability without entanglement is 1/n1/n1/n. This near-linear ratio is almost 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. An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity, pages 157--166, 2011.
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.
Abstract Quantum pseudo-telepathy games, such as the Mermin–Peres magic square and the doily game (DG), theoretically allow players to win with unit probability when using entangled quantum strategies. We quantitatively characterize the quantum advantage in these games and compare it with violations of two Bell inequalities: the Clauser–Horne–Shimony–Holt and the Collins–Gisin inequalities. The analysis is restricted to two families of two-qubit states: modified Werner states and Bell-diagonal states. For each case, we identify and quantify the regions of quantum state space that exhibit either a quantum advantage or a Bell inequality violation, relative to the set of all entangled states. Within these families, the DG encompasses a larger fraction of entangled states than the Mermin–Peres magic square game, although both cover significantly smaller regions of entangled states compared to those where Bell inequalities are violated. Although both approaches are fundamentally linked to quantum contextuality, our analysis of the examined two-qubit state families suggests that Bell inequalities are more effective at revealing entanglement, even if pseudo-telepathy games offer a more intuitive and conceptually appealing perspective.
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.
In a nonlocal game of quantum value one that no finite-dimensional strategy wins, near-perfect play needs growing dimension, which separable states can have. We ask how much usable entanglement it needs: the demand at loss ε\varepsilonε is the least one-way distillable entanglement of the original state of a strategy of loss at most ε\varepsilonε. For synchronous games with tested diagonals and for constraint-variable consistency games, demand diverges exactly when no finite-dimensional strategy is perfect; then, for any number of Bell pairs and any fidelity below one, every sufficiently good mixed strategy yields that many at that fidelity by local isometries. For rational synchronous or binary constraint games, a loss guaranteeing this is computable under a promise, but boundedness of demand is undecidable among games of value one. Demand is at least logarithmic if near-winners have a sign relation and an even dilation mirrored by both players, as in a game from Abels' group. For agreement games the directions agree up to a factor three in loss, optimal among Bob-fixed deterministic local symmetrizations. The geometry of the group behind a game, not its presentation, sets the rates. Fixed games demand αlog⁡(1/ε)\alpha\log(1/\varepsilon)αlog(1/ε) for every α=12∑ilog⁡miqi\alpha=\frac12\sum_i\log_{m_i}q_iα=21​∑i​logmi​​qi​ with qi≥2q_i\ge2qi​≥2 a power of two dividing mim_imi​, a dense set containing all positive rationals and some transcendentals, such as 12log⁡62\frac12\log_6221​log6​2; a configuration-lamp game demands ε−1+o(1)\varepsilon^{-1+o(1)}ε−1+o(1); Pauli lamps on the points of Houghton's three rays give demand between ε−0.0690\varepsilon^{-0.0690}ε−0.0690 and ε−1/4\varepsilon^{-1/4}ε−1/4. If group relations hold exactly and Alice matches Bob to error eee, demand counts qubits addressable by short words: Θ(1/e)\Theta(1/e)Θ(1/e), Θ(e−k)\Theta(e^{-k})Θ(e−k) for integers k≥1k\ge1k≥1, or 2Θ(1/e)2^{\Theta(1/e)}2Θ(1/e). Conditional on our attainment and tail bounds, the I3322I_{3322}I3322​ optimum needs bounded usable entanglement.