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.
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−ε, the players' shared state is O(poly(nε))-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(poly(nε)) close to the "ideal" strategy when acting on the shared state.
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.
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 91, achieved by the Mermin-Peres magic square game. A larger gap of 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 91. We then demonstrate that 91 is not optimal by explicitly constructing a new nonlocal game with gap 354.
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.
Exact value and rigidity of the 2×3 magic rectangle
The 2×3 magic rectangle is a nonlocal game in which two players match entries subject to incompatible parity constraints. Its quantum value was suggested by numerical bounds and known quantum random access codes. We prove that this value is (1+2/3)/2 and classify all optimal strategies in arbitrary finite local dimensions, allowing general measurements: up to local isometries and ancillary systems, each contains a maximally entangled pair of four-dimensional systems with fixed measurements on the local state supports. The same value holds for commuting-operator strategies and for the almost-quantum relaxation, confirming the Adamson--Wallden conjecture for this rectangle. For finite-dimensional magic-square strategies, the largest score compatible with perfect prediction of Alice's complete first row by an adversary with quantum side information is one third plus two thirds of the rectangle value. We classify the strategies attaining this threshold with perfect prediction and give linear-order upper and lower bounds on one minus the best compatible guessing probability above it. The rectangle value is also the optimal average success probability of finite-dimensional three-bit random access codes that hide the full input parity, and we classify all optimal codes.
We present a strong parallel repetition theorem for the entangled value of multi-player, one-round free games (games where the inputs come from a product distribution). Our result is the first parallel repetition theorem for entangled games involving more than two players. Furthermore, our theorem applies to games where the players are allowed to output (possibly entangled) quantum states as answers. More specifically, let G be a k-player free game, with entangled value val∗(G)=1−ε. We show that the entangled value of the n-fold repetition of G, val∗(G⊗n), is at most (1−ε)Ω(n/k2). In the traditional setting of k=2 players, our parallel repetition theorem is optimal in terms of its dependence on ε and n. For an arbitrary number of players, our result is nearly optimal: for all k, we exhibit a k-player free game G and n>1 such that val∗(G⊗n)≥val∗(G)n/k. Hence, exponent of the repeated game value cannot be improved beyond Ω(n/k). Our parallel repetition theorem improves on the prior results of [Jain, et al. 2014] and [Chailloux, Scarpa 2014] in a number of ways: (1) our theorem applies to a larger class of games (arbitrary number of players, quantum outputs); (2) we demonstrate that strong parallel repetition holds for the entangled value of free games: i.e., the base of the repeated game value is 1−ε, rather than 1−ε2; and (3) there is no dependence of the repeated game value on the input and output alphabets of G. In contrast, it is known that the repeated game value of classical free games must depend on the output size. Thus our results demonstrate a seperation between the behavior of entangled games and classical games.
Device-independent self-testing allows a verifier to certify that potentially malicious parties hold on to a specific quantum state, based only on the observed correlations. Parallel self-testing has recently been explored, aiming to self-test many copies (i.e. a tensor product) of the target state concurrently. In this work, we show that n EPR pairs can be self-tested in parallel through n copies of the well known CHSH game. We generalise this result further to a parallel self-test of n tilted EPR pairs with arbitrary angles, and finally we show how our results and calculations can also be applied to obtain a parallel self-test of 2n EPR pairs via n copies of the Mermin-Peres magic square game.