What is the quantum strategy required to win the Magic Squares game

Question

This question is about the Magic Squares game. Links here, here and link here in which two players try to win a game. It's a cooperative game - either the team wins or the team loses. It is claimed that without a shared quantum state, they lose at least 1/9 of the time. The rules of the game are as follows: There is a 3 by 3 grid, and Alice lays down zeros and/or ones on one of the rows. Bob lays down zeros and ones on one of the columns. The referee tells Alice what row to put her digits in and tells Bob what column to put his digits in.

Alice's row has to have an even number of ones and BOb's column has to have an odd number of ones.

There is one square in common between Alice's row and Bob's column. In order to win, Alice's digit there has to match Bob's digit there. If they are different, the players lose.

The question is: can Alice and Bob use a shared quantum state prepared before the game starts to win 100% of the time and, if so, what measurements and quantum operations do they perform?

Answer 1

Instead of $0$s and $1$s, suppose the labels of the column/rows are $+1$ and $-1$ respectively. Then if the rows are labelled $(1,1,1)$ (instead of $(0,0,0)$) and the columns are labelled $(1,1,-1)$ (instead of $(0,0,1)$) so that the parity of the $1$s and $-1$s is consistent with the parity of the previously labelled $0$s and $1$s.

In this case, the following predetermined observables can be used to win the game with probability one. $$\begin{matrix} I\otimes Z & Z\otimes I & Z\otimes Z \\ X\otimes I & I\otimes X & X\otimes X \\ X\otimes Z & Z\otimes X & Y\otimes Y\\ \end{matrix},$$ where $X$, $Y$ and $Z$ are the familiar $2\times 2$ Pauli matrices.

To see why this works, remark that the product of the observables along each of the first 2 rows and columns is $I\otimes I=I$ because $Z^2=X^2=I$.

For the last row and column recall that $Y=iZX$ and $i^2=-1$, and since $X$ and $Z$ anticommute ($XZ=-ZX$) we see that the product along the 3rd column is $-I\otimes I=-I$. On the other hand, the product along the 3rd row is $I\otimes I=I$ since $XZiZX=iI$ and the $ZXiZX=-iI$ from the anticommuting $ZX$ cancels out with the $i^2=-1$ once combined in the tensor product, as desired.

The perfect quantum strategy for the game consists of using a maximally entangled state along with Alice and Bob both employing the observables outlined above. If you want to see why these observables give consistent answers on overlapping cells, check out How can one show that Alice's and Bob's answers agree at the intersection cells of Mermin-Peres' "magic square"?.