When players in the Mermin-Peres magic square game use a deterministic strategy, the largest probability of winning is 8/9. If the players share a quantum state, then there is a strategy for winning 100% of the time. The idea is to introduce commuting observables.
Alice produces a row of 3 squares with an even number of red squares. There are four such options: GGG, GRR, RGR, RRG. Similarly, Barbara produces a column of 3 squares with an odd number of red squares. There are also four such options: RRR, RGG, GRG, GGR. Thus, Alice and Barbara each need a 2-qubit state and the system is described by a 4-qubit state.
First, Alice and Barbara share a particular 4-qubit quantum state:
$$ | \psi \rangle = \frac{1}{2} \left( |00 \rangle_{AB} + |11 \rangle_{AB} \right) \otimes \left( |00 \rangle_{AB} + |11 \rangle_{AB} \right). $$
This state vector can be re-written as:
$$ | \psi \rangle = \frac{1}{2} \left( |00 \rangle_{A} |00 \rangle_{B} + |01 \rangle_{A} |01 \rangle_{B} + |10 \rangle_{A} |10 \rangle_{B} + |11 \rangle_{A} |11 \rangle_{B} \right). $$
Note that this state vector is entangled because it cannot be factorized into Alice and Barbara pieces.
Next, consider the following array of 2-qubit operators:
$$ G = \begin{pmatrix} X \otimes I_{2} & I_{2} \otimes X & X \otimes X \\ I_{2} \otimes Z & Z \otimes I_{2} & Z \otimes Z \\ -X \otimes Z & -Z \otimes X & Y \otimes Y \end{pmatrix}. $$
Using the properties of the Pauli matrices,
$$ XY + YX = 0, \qquad YZ + ZY = 0, \qquad ZX + XZ = 0; $$
$$ X^{2} = Y^{2} = Z^{2} = I_{2}; $$
you can check that:
- Any two operators in the same column commute.
- Any two operators in the same row commute.
- The product of the operators in a row is \(I_{4}\).
- The product of the operators in a column is \(-I_{4}\).
Since the three operators in each row or column commute with each other, you can have simultaneous eigen-kets. For the first row, the simultaneous eigen-kets are
$$ |{+}{+}{+} \rangle = |X+ \rangle \otimes |X+ \rangle = \frac{1}{2} \left( |00 \rangle + |01 \rangle + |10 \rangle + |11 \rangle \right); $$
$$ |{+}{-}{-} \rangle = |X+ \rangle \otimes |X- \rangle = \frac{1}{2} \left( |00 \rangle - |01 \rangle + |10 \rangle - |11 \rangle \right); $$
$$ |{-}{+}{-} \rangle = |X- \rangle \otimes |X+ \rangle = \frac{1}{2} \left( |00 \rangle + |01 \rangle - |10 \rangle - |11 \rangle \right); $$
$$ |{-}{-}{+} \rangle = |X- \rangle \otimes |X- \rangle = \frac{1}{2} \left( |00 \rangle - |01 \rangle - |10 \rangle + |11 \rangle \right). $$
For the first column, the simultaneous eigen-kets are
$$ |{+}{+}{-} \rangle = |X+ \rangle \otimes |Z+ \rangle = \frac{1}{\sqrt{2}} \left( |00 \rangle + |10 \rangle \right); $$
$$ |{+}{-}{+} \rangle = |X+ \rangle \otimes |Z- \rangle = \frac{1}{\sqrt{2}} \left( |01 \rangle + |11 \rangle \right); $$
$$ |{-}{+}{+} \rangle = |X- \rangle \otimes |Z+ \rangle = \frac{1}{\sqrt{2}} \left( |00 \rangle - |10 \rangle \right); $$
$$ |{-}{-}{-} \rangle = |X- \rangle \otimes |Z- \rangle = \frac{1}{\sqrt{2}} \left( |01 \rangle - |11 \rangle \right). $$
For the second row, the simultaneous eigen-kets are
$$ |{+}{+}{+} \rangle = |Z+ \rangle \otimes |Z+ \rangle = |00 \rangle; $$
$$ |{-}{+}{-} \rangle = |Z+ \rangle \otimes |Z- \rangle = |01 \rangle; $$
$$ |{+}{-}{-} \rangle = |Z- \rangle \otimes |Z+ \rangle = |10 \rangle; $$
$$ |{-}{-}{+} \rangle = |Z- \rangle \otimes |Z- \rangle = |11 \rangle. $$
For the second column, the simultaneous eigen-kets are
$$ |{+}{+}{-} \rangle = |Z+ \rangle \otimes |X+ \rangle = \frac{1}{\sqrt{2}} \left( |00 \rangle + |01 \rangle \right); $$
$$ |{-}{+}{+} \rangle = |Z+ \rangle \otimes |X- \rangle = \frac{1}{\sqrt{2}} \left( |00 \rangle - |01 \rangle \right); $$
$$ |{+}{-}{+} \rangle = |Z- \rangle \otimes |X+ \rangle = \frac{1}{\sqrt{2}} \left( |10 \rangle + |11 \rangle \right); $$
$$ |{-}{-}{-} \rangle = |Z- \rangle \otimes |X- \rangle = \frac{1}{\sqrt{2}} \left( |10 \rangle - |11 \rangle \right). $$
The third row and the third column are non-trivial because they involve degree-2 Pauli operators. For the third row, the simultaneous eigen-kets are
$$ |{+}{+}{+} \rangle = \frac{1}{2} \left( |00 \rangle - |01 \rangle - |10 \rangle - |11 \rangle \right); $$
$$ |{-}{+}{-} \rangle = \frac{1}{2} \left( |00 \rangle - |01 \rangle + |10 \rangle + |11 \rangle \right); $$
$$ |{+}{-}{-} \rangle = \frac{1}{2} \left( |00 \rangle + |01 \rangle - |10 \rangle + |11 \rangle \right); $$
$$ |{-}{-}{+} \rangle = \frac{1}{2} \left( |00 \rangle + |01 \rangle + |10 \rangle - |11 \rangle \right). $$
Finally, the simultaneous eigen-kets for the third column are
$$ |{+}{+}{-} \rangle = \frac{1}{\sqrt{2}} \left( |00 \rangle + |11 \rangle \right); $$
$$ |{+}{-}{+} \rangle = \frac{1}{\sqrt{2}} \left( |01 \rangle + |10 \rangle \right); $$
$$ |{-}{+}{+} \rangle = \frac{1}{\sqrt{2}} \left( |00 \rangle - |11 \rangle \right); $$
$$ |{-}{-}{-} \rangle = \frac{1}{\sqrt{2}} \left( |01 \rangle - |10 \rangle \right). $$
Note that \(| \psi \rangle\) is a vector in a 16-dimensional space. Alice gets a row number \(m\) and Barbara gets a column number \(n\). There are 9 possible referee outcomes. The probability of winning the game is
$$ p_{\text{win}}(\psi) = \frac{1}{9} \sum_{m = 1}^{3} \sum_{n = 1}^{3} p_{\text{win}}(m, n | \psi). $$
The probability of winning for the \(m\)-th row and the \(n\)-th column involves the different ways that Alice and Barbara agree.
For definiteness, consider the case \((m, n) = (1, 1)\). There are eight possible scenarios where Alice and Barbara agree:
- Alice measures \({+}{+}{+}\) and Barbara measures \({+}{+}{-}\)
- Alice measures \({+}{+}{+}\) and Barbara measures \({+}{-}{+}\)
- Alice measures \({+}{-}{-}\) and Barbara measures \({+}{+}{-}\)
- Alice measures \({+}{-}{-}\) and Barbara measures \({+}{-}{+}\)
- Alice measures \({-}{+}{-}\) and Barbara measures \({-}{+}{+}\)
- Alice measures \({-}{+}{-}\) and Barbara measures \({-}{-}{-}\)
- Alice measures \({-}{-}{+}\) and Barbara measures \({-}{+}{+}\)
- Alice measures \({-}{-}{+}\) and Barbara measures \({-}{-}{-}\)
For scenario 1, the bra that Alice and Barbara use to measure is
\begin{multline*} {}_{A}\langle {+}{+}{+} | \otimes {}_{B}\langle {+}{+}{-} | = \frac{1}{\sqrt{8}} \left( {}_{A}\langle 00 | {}_{B}\langle 00 | + {}_{A}\langle 00 | {}_{B}\langle 10 | + {}_{A}\langle 01 | {}_{B}\langle 00 | + {}_{A}\langle 01 | {}_{B}\langle 10 | \right. \\ \left. {} + {}_{A}\langle 10 | {}_{B}\langle 00 | + {}_{A}\langle 10 | {}_{B}\langle 10 | + {}_{A}\langle 11 | {}_{B}\langle 00 | + {}_{A}\langle 11 | {}_{B}\langle 10 | \right). \end{multline*}
The probability of winning scenario 1 is
$$ |({}_{A}\langle {+}{+}{+}| \otimes {}_{B}\langle {+}{+}{-}|)|\psi \rangle|^{2} = \left| \frac{1}{2 \sqrt{8}} + \frac{1}{2 \sqrt{8}} \right|^{2} = \frac{1}{8}. $$
The probability of winning the other seven scenarios is the same. Thus, the probability of winning this site in the grid is 100%. A similar argument shows that the probability of winning any site in the grid is 100%. Hence, Alice and Bob can always win the game.
