What states are valid GHZ-game states?

Question

The GHZ game involves three non-communicating players, Alice, Bob, and Carol. They each receive a bit, $r,s,t$ with the guarantee that $r\oplus s\oplus t=0$ (i.e. with the guarantee that there are an even number of 1s). Their goal is to output $a,b,c$ respectively so $a\oplus b\oplus c=r\vee s\vee t$. The winning conditions are summarized in the table below:

$rst$	$a\oplus b\oplus c$
000	0
011	1
101	1
110	1

A strategy which works is for them to share the entangled state $$\frac{1}{\sqrt{2}}\left(|000\rangle+|111\rangle\right).$$ If they see a $0$, they apply the $X$-gate. If they see a $1$, they apply a $Y$-gate. It can be shown that this is a winning strategy since after applying the respective gates, we end up with a superposition of states with the required parities.

However, they could have also done this with the state $$\frac{1}{2}\left(|000\rangle-|011\rangle-|101\rangle-|110\rangle\right),$$ and applying a Hadamard on $r,s,t=1$ and doing nothing otherwise.

I am aware that in order to determine when a three qubit state $|\psi\rangle$ can yield a winning strategy has something to do with correlations they satisfy, but I have no idea what this means really. What I know is that the gate Alice applies to the state $|\psi\rangle$ is a function of the bit $r$ she receives. Call it $M_r$. Similarly, the gates Bob, Carol apply can be called $M_s,M_t$. Thus the net effect on the state is $M_{rst}=M_r\otimes M_s\otimes M_t$. The goal is that this gate should be such that $$M_{rst}|\psi\rangle$$ should result in a superposition state where the parity of each state is even in the event $r=s=t=0$ and in a superposition state where the parity of each state should be odd in the other events. But how can I use this to impose restrictions on the allowed "GHZ states" $|\psi\rangle$ if $M_r,M_s,M_t$ are just arbitrary gates?

Answer 1

In general, property that you are describing is called "rigidity". Many non-local games have rigidity conditions, such as the CHSH game, magic square game, etc. It is a theorem of the form: "for any strategy that achieves the optimal probability for a game, they must share a resource state that is equivalent to $|\psi\rangle$". The rules of the game state that they may share any state, but the rigidity property of some games forces the players to only use certain states if they want to win.

Here, "equivalent" means that, roughly speaking, there is a way to convert their state into a GHZ state without any communication during the game. As an example, suppose they started with the state in your question:

$$\frac{1}{2}(|000\rangle - |011\rangle - |101\rangle - |110\rangle)$$

There is an alternate strategy that instead says: "first apply the Hadamard gate your own qubit, then apply the GHZ state strategy". The first step does not depend at all on the inputs $r, s, t$ that they are given, and only has single qubit gates, so it does not require any communication.

In that sense, the two strategies you've listed are essentially the same, just in a different basis. For the GHZ game, there is essentially only one winning strategy, which is to use a state that is equivalent to a GHZ state.