# Notes - Quantum Information HT24, The GHZ game

### Flashcards

Give the 4 rules of the GHZ game.

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

- 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.
- 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.
- Either the referee sends the bit $0$ to everyone, or sends it to one player.
- The players respond with bits $x$, $y$ and $z$ respectively.
- 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$

Suppose Alice, Bob, Charlie and a referee are playing the GHZ game with classical resources. For background, the rules of the GHZ game are:

- 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.
- The referee sends one bit to each player: $a$ to Alice, $b$ to Bob, and $c$ to Charlie.
- Either the referee sends the bit $0$ to everyone, or sends it to one player.
- The players respond with bits $x$, $y$ and $z$ respectively.
- 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$

Quickly prove that Alice, Bob and Charlie cannot win with certainty using only classical resources.

- 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.
- The referee sends one bit to each player: $a$ to Alice, $b$ to Bob, and $c$ to Charlie.
- Either the referee sends the bit $0$ to everyone, or sends it to one player.
- The players respond with bits $x$, $y$ and $z$ respectively.
- 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.

Suppose Alice, Bob, Charlie and a referee are playing the GHZ game. For background, the rules of the GHZ game are:

- 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.
- The referee sends one bit to each player: $a$ to Alice, $b$ to Bob, and $c$ to Charlie.
- Either the referee sends the bit $0$ to everyone, or sends it to one player.
- The players respond with bits $x$, $y$ and $z$ respectively.
- 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$

Describe a quantum strategy using the GHZ state

\[|\text{GHZ}\rangle := \frac{1}{\sqrt 3} (|0\rangle \otimes |0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle \otimes |1\rangle)\]
and quickly prove that this strategy works.

- 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.
- The referee sends one bit to each player: $a$ to Alice, $b$ to Bob, and $c$ to Charlie.
- Either the referee sends the bit $0$ to everyone, or sends it to one player.
- The players respond with bits $x$, $y$ and $z$ respectively.
- 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$

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.