The game you can’t win

Try it

Each row must multiply to +1, each column to −1.

The magic square
+1	+1	+1	row needs +1has +1
+1	+1	+1	row needs +1has +1
+1	+1	+1	row needs +1has +1
needs −1has +1	needs −1has +1	needs −1has +1

Shown: every entry +1. All three rows are satisfied and all three columns fail.

Why no filling works

Multiply all nine entries together. Grouping them by rows, you get the product of the three row products: (+1)(+1)(+1) = +1. Grouping the same nine entries by columns, you get (−1)(−1)(−1) = −1. The same number cannot be both. So at least one of the six rules always fails, however the square is filled, and some fillings fail exactly one.

The same square, as a game

Now split it between two players, Alice and Bob, who may agree on a plan beforehand but cannot talk once the game starts. A referee picks a row at random and asks Alice to fill it, and picks a column at random and asks Bob to fill it. Alice’s three entries must multiply to +1, Bob’s to −1, and they must agree on the one cell where the row meets the column.

A fixed plan amounts to Alice filling the square row by row and Bob filling it column by column. If their two fillings obeyed their rules and agreed in every cell, they would form one square obeying all six rules, which is impossible. So on at least one of the nine row-and-column pairs they break a rule or disagree. No classical plan, shared randomness included, wins more than 8 times in 9.

With entanglement they win every time. Give Alice and Bob two Bell pairs, so that each holds two qubits and their four qubits are in the state $| Φ^{+} ⟩ \otimes | Φ^{+} ⟩$ . Each cell of the square holds an observable on two qubits, with outcomes +1 or −1. Here $X, Y, Z$ are the Pauli matrices, and $X Z$ means $X \otimes Z$ , an $X$ on the first qubit and a $Z$ on the second:

The Mermin–Peres square
$X I$	$I X$	$X X$
$I Z$	$Z I$	$Z Z$
$- X Z$	$- Z X$	$Y Y$

The three observables in any row commute and multiply to $+ I$ ; those in any column commute and multiply to $- I$ . Alice measures the three observables of her row on her two qubits, Bob those of his column on his. Because the observables in a row commute, Alice’s three outcomes multiply to +1 every time; Bob’s multiply to −1. And because each Bell pair is maximally entangled and every observable in the square equals its own transpose, Alice and Bob always obtain the same outcome for the shared cell. They win with probability one, using four dimensions each.

The square is due to Mermin and to Peres (1990); as a two-player game it is standard in the study of nonlocal games. This page explains it as background; it is not a result of ours.

From here to our work

The magic square is won perfectly in finite dimension. Some games are not. Our papers study games of quantum value one, winnable with probability as close to one as you like, that no finite-dimensional strategy wins perfectly. Then perfection is a limit, and approaching it has a price: the dimension needed to lose at most $ε$ grows without bound as $ε$ shrinks.

Our base game is built from Mančinska’s flagged magic-square game. It is won perfectly only in infinite dimension, and losing at most $ε$ needs local dimension $10 \log_{2} (1 / ε) + O (\log \log (1 / ε))$ . The paper
A game with 243 question pairs is won perfectly only with type III algebras, such as those of quantum field theory, and its finite-dimensional price is $\exp (Θ (ε^{- 1 / 2}))$ . The result
An explicit game needs local dimension $\exp (ε^{- 1 + o (1)})$ . The paper
And for some games the growth rate of the price is a number no algorithm can compute from the rules. The result