Notes - Quantum Information HT24, The GHZ game

This is a game involving four players: Alice, Bob, Charlie and a referee.

1. Alice, Bob and Charlie are allowed to meet before the game to decide their strategy, but after the game starts, they are not allowed to communicate with each other.
2. The referee sends one bit to each player: $a$ to Alice, $b$ to Bob, and $c$ to Charlie. They each respond with a bit: $x$ for Alice, $y$ for Bob and $z$ for Charlie.
3. Either the referee sends the bit $0$ to everyone, or sends it to one player.
4. The players respond with bits $x$, $y$ and $z$ respectively.
5. They win if:
   • The referee sent the $0$ to everyone, and $x \oplus y \oplus z = 0$
   • The referee only sent $0$ to one player, and $x \oplus y \oplus z = 1$

(if there exists a randomised strategy for classical players to win with certainty, then they must win with certainty for all values of the randomness, hence there exists a deterministic strategy that wins with certainty).

In a deterministic strategy, Alice, Bob and Charlie’s responses are boolean functions of their inputs, say $f$, $g$ and $h$. By the rules of the game, this implies that we need the following four boolean equations satisfied:

\[\begin{aligned} f(0) \oplus g(0) \oplus h(0) &= 0 \\\\ f(0) \oplus g(1) \oplus h(1) &= 1 \\\\ f(1) \oplus g(0) \oplus h(0) &= 1 \\\\ f(1) \oplus g(1) \oplus h(0) &= 1 \end{aligned}\]

But, taking the sum of everything on the right hand side, and taking the sum of everything on the right hand side (mod 2), we see that this would imply

\[0 = 1\]

which means the system of equations is inconsistent. Hence no classical strategy can win with certainty.

The strategy:

Given a set of bits $(x = m, y = n, z = \ell)$, each player measures in $\{ \vert +\rangle, \vert -\rangle\}$ if their bit is $0$ and $\{ \vert {+y}\rangle, \vert {-y}\rangle\}$ if their bit is $1$. They respond with $0$ if they get outcome $0$ and with $1$ if they get outcome $1$.

• $ \vert {+y}\rangle = \frac{1}{\sqrt 2} ( \vert 0\rangle + i \vert 1\rangle)$
• $ \vert {-y}\rangle = \frac{1}{\sqrt 2} ( \vert 0\rangle -i \vert 1\rangle)$.
• (one way to remember this is that they either use the $x$-basis or the $y$-basis)

Proof that this works:

First consider the case where $a = b = c = 0$. Then

\[\begin{aligned} &p(x = m, y = n, z = \ell \mid a = 0, b = 0, c = 0) \\\\ = &\left| \left(\frac{\langle 0| +(-1)^m \langle 1|}{\sqrt 2} \otimes \frac{\langle 0| +(-1)^n \langle 1|}{\sqrt 2} \otimes \frac{\langle 0| +(-1)^\ell \langle 1|}{\sqrt 2} \right) \left( \frac{|0\rangle \otimes |0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle \otimes |1\rangle}{\sqrt 2} \right) \right|^2 \\\\ = &\left| \frac{1 + (-1)^{m + n + \ell}\\,}{4} \right|^2 \end{aligned}\]

which is zero if $m + n + \ell$ is odd, or equivalently if $m \oplus n \oplus \ell = 1$, so this never happens and we always have $m \oplus n \oplus \ell = 0$ in this case.

For the case where just one player recieves a $0$, we can without loss of generality assume the situation is $a = 0, b = 1, c = 1$. Then we get:

\[\begin{aligned} &p(x = m, y = n, z = \ell \mid a = 0, b = 1, c = 1) \\\\ = &\left| \left(\frac{\langle 0| +(-1)^m \langle 1|}{\sqrt 2} \otimes \frac{\langle 0| -i(-1)^n \langle 1|}{\sqrt 2} \otimes \frac{\langle 0| -i(-1)^\ell \langle 1|}{\sqrt 2} \right) \left( \frac{|0\rangle \otimes |0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle \otimes |1\rangle}{\sqrt 2} \right) \right|^2 \\\\ = &\left| \frac{1 - (-1)^{m + n + \ell}\\,}{4} \right|^2 \end{aligned}\]

which is zero if $m + n + \ell$ is even, so we also see that $m \oplus n \oplus \ell = 1$ in all circumstances.

Hence in all cases the players answer correctly.