We demonstrate that the largest 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 is at least $\frac{4}{35}$, improving on the gap of $\frac{1}{9}$ achieved by the Mermin-Peres magic square game. We do so by explicitly constructing a nonlocal game with classical value $\frac{31}{35}$ using the full symmetry of the 2-qubit Pauli group.
We demonstrate that the largest 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 is at least 354, improving on the gap of 91 achieved by the Mermin-Peres magic square game. We do so by explicitly constructing a nonlocal game with classical value 3531 using the full symmetry of the 2-qubit Pauli group.
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.
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−ε needs entanglement entropy ε−1+o(1), hence local dimension 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/ε)) suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in 1/ε. 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 ε, 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 ε is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH(n) games need Θ(min(n,1/ε)) ebits, and the linear system game of Slofstra and Vidick needs local dimension Θ(ε−1/2).
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≥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≥3 is a consequence of monogamy.
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 ε is the least one-way distillable entanglement of the original state of a strategy of loss at most ε. 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/ε) for every α=21∑ilogmiqi with qi≥2 a power of two dividing mi, a dense set containing all positive rationals and some transcendentals, such as 21log62; a configuration-lamp game demands ε−1+o(1); Pauli lamps on the points of Houghton's three rays give demand between ε−0.0690 and ε−1/4. If group relations hold exactly and Alice matches Bob to error e, demand counts qubits addressable by short words: Θ(1/e), Θ(e−k) for integers k≥1, or 2Θ(1/e). Conditional on our attainment and tail bounds, the I3322 optimum needs bounded usable entanglement.
This paper considers a special class of nonlocal games (G,ψ), where G is a two-player one-round game, and ψ is a bipartite state independent of G. In the game (G,ψ), the players are allowed to share arbitrarily many copies of ψ. The value of the game (G,ψ), denoted by ω∗(G,ψ), is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states ψ. For a noisy maximally entangled state ψ, a two-player one-round game G and an arbitrarily small precision ϵ>0, this paper proves an upper bound on the number of copies of ψ for the players to win the game with a probability ϵ close to ω∗(G,ψ). A noisy maximally entangled state is a two-qudit state with both marginals being completely mixed states and the maximal correlation being less than 1. In particular, it includes $(1-\epsilon)|\Psi_m\rangle\langle\Psi_m|+\epsilon\frac{\mathbbm{1}_m}{m}\otimes\frac{\mathbbm{1}_m}{m}$ for ϵ>0, where ∣Ψm⟩=m1∑i=0m−1∣m,m⟩ is an m-dimensional maximally entangled state. Hence, it is feasible to approximately compute ω∗(G,ψ) to an arbitrary precision. Recently, a breakthrough result by Ji et al. showed that it is undecidable to approximate the values of nonlocal games to a constant precision, when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that MIP∗=RE. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications. (A corrected version is attached.)
We identify a structural mechanism by which perfect play in a nonlocal game requires and self-tests a specific non-maximally entangled state. To this end, we construct a Flagged Magic-Square game by extending the standard Magic-Square game with an additional ``flag'' outcome and two additional questions for each player. The game admits a perfect strategy using a state with Schmidt coefficients proportional to (1,2,2,2,2). We give a direct algebraic proof that maximally entangled strategies have winning probability bounded away from one, independently of dimension. Moreover, the game self-tests this state, providing an example of a two-party pseudo-telepathy game that certifies a specific non-maximally entangled state. Our construction illustrates how adding suitable constraints to a rigid measurement geometry can enforce specific Schmidt ratios and provides a modular route to further self-tests based on other rigid pseudo-telepathy games.
We establish a general game-to-channel reduction that transfers separations in the game model to one-shot zero-error communication over classical channels. Applied to the Flagged Magic-Square game, it yields a classical channel for which entanglement permits the zero-error transmission of ten messages in a single use, whereas any finite-dimensional maximally entangled resource permits at most nine. Thus, maximally entangled states are not a universally optimal entanglement resource for zero-error communication over classical noisy channels.