Alice and Bob share a 2-qubit state. That is, a ket \(| \psi \rangle\) of the form
$$| \psi \rangle = a_{00} | 00 \rangle + a_{01} | 01 \rangle + a_{10} | 10 \rangle + a_{11} | 11 \rangle. $$
Just like before, Alice and Bob each get a random bit. Alice gets \(a\) and Bob gets \(b\). They each use their bit to make a choice of a basis to make a measurement. The basis is ortho-normal, so for Alice it should have the form
$$ |A_{0}(\alpha) \rangle = \cos{(\alpha)} | 0 \rangle + \sin{(\alpha)} | 1 \rangle, \qquad |A_{1}(\alpha) \rangle = \sin{(\alpha)} | 0 \rangle - \cos{(\alpha)} | 1 \rangle; $$
and similarly for Bob:
$$ |B_{0}(\beta) \rangle = \cos{(\beta)} | 0 \rangle + \sin{(\beta)} | 1 \rangle, \qquad |B_{1}(\beta) \rangle = \sin{(\beta)} | 0 \rangle - \cos{(\beta)} | 1 \rangle. $$
If \(a = 0\), then \(\alpha = \alpha_{0}\); otherwise \(\alpha = \alpha_{1}\). Similarly, \(b = 0\), then \(\beta = \beta_{0}\); otherwise \(\beta = \beta_{1}\).
For future reference, here I record the tensor products:
$$ |A_{0}(\alpha) B_{0}(\beta) \rangle = \cos{(\alpha)} \cos{(\beta)} |00 \rangle + \cos{(\alpha)} \sin{(\beta)} |01 \rangle + \sin{(\alpha)} \cos{(\beta)} |10 \rangle + \sin{(\alpha)} \sin{(\beta)} |11 \rangle $$
$$ |A_{0}(\alpha) B_{1}(\beta) \rangle = \cos{(\alpha)} \sin{(\beta)} |00 \rangle - \cos{(\alpha)} \cos{(\beta)} |01 \rangle + \sin{(\alpha)} \sin{(\beta)} |10 \rangle - \sin{(\alpha)} \cos{(\beta)} |11 \rangle $$
$$ |A_{1}(\alpha) B_{0}(\beta) \rangle = \sin{(\alpha)} \cos{(\beta)} |00 \rangle + \sin{(\alpha)} \sin{(\beta)} |01 \rangle - \cos{(\alpha)} \cos{(\beta)} |10 \rangle - \cos{(\alpha)} \sin{(\beta)} |11 \rangle $$
$$ |A_{1}(\alpha) B_{1}(\beta) \rangle = \sin{(\alpha)} \sin{(\beta)} |00 \rangle - \sin{(\alpha)} \cos{(\beta)} |01 \rangle - \cos{(\alpha)} \sin{(\beta)} |10 \rangle + \cos{(\alpha)} \cos{(\beta)} |11 \rangle $$
There are four possible outcomes for the bits \((a, b)\) that the referee produces:
$$ (0, 0), \qquad (0, 1), \qquad (1, 0), \qquad (1, 1). $$
Recall that the game is won if the following condition is met:
$$ \operatorname{AND}(a, b) = \operatorname{XOR}(x, y). $$
Let me check each of the possible referee outcomes.
If \((a, b) = (0, 0)\), then \(\operatorname{AND}(a, b) = 0\). In order for \(\operatorname{XOR}(x, y) = 0\) you need either \(x = y = 0\), or \(x = y = 1\). Thus, the probability of winning in this case has two contributions:
$$ p_{\text{win}}(0, 0) = \left| \langle A_{0}(\alpha_{0})B_{0}(\beta_{0}) | \psi \rangle \right|^{2} + \left| \langle A_{1}(\alpha_{0})B_{1}(\beta_{0}) | \psi \rangle \right|^{2}. $$
That is, Alice projects along \(|A_{0}(\alpha_{0})\rangle\) if \(x=0\) or along \(|A_{1}(\alpha_{0})\rangle\) if \(x=1\). Similarly, Bob projects along \(|B_{0}(\beta_{0})\rangle\) if \(y=0\) or along \(|B_{1}(\beta_{0})\rangle\) if \(y=1\).
If \((a, b) = (0, 1)\), then \(\operatorname{AND}(a, b) = 0\). In order for \(\operatorname{XOR}(x, y) = 0\) you need either \(x = y = 0\), or \(x = y = 1\). Thus, the probability of winning in this case has two contributions:
$$ p_{\text{win}}(0, 1) = \left| \langle A_{0}(\alpha_{0})B_{0}(\beta_{1}) | \psi \rangle \right|^{2} + \left| \langle A_{1}(\alpha_{0})B_{1}(\beta_{1}) | \psi \rangle \right|^{2}. $$
If \((a, b) = (1, 0)\), then \(\operatorname{AND}(a, b) = 0\). In order for \(\operatorname{XOR}(x, y) = 0\) you need either \(x = y = 0\), or \(x = y = 1\). Thus, the probability of winning in this case has two contributions:
$$ p_{\text{win}}(1, 0) = \left| \langle A_{0}(\alpha_{1})B_{0}(\beta_{0}) | \psi \rangle \right|^{2} + \left| \langle A_{1}(\alpha_{1})B_{1}(\beta_{0}) | \psi \rangle \right|^{2}. $$
If \((a, b) = (1, 1)\), then \(\operatorname{AND}(a, b) = 1\). In order for \(\operatorname{XOR}(x, y) = 1\) you need either \(x = 0\) and \(y = 1\), or \(x = 1\) and \(y = 1\). Thus, the probability of winning in this case has two contributions:
$$ p_{\text{win}}(1, 1) = \left| \langle A_{0}(\alpha_{1})B_{1}(\beta_{1}) | \psi \rangle \right|^{2} + \left| \langle A_{1}(\alpha_{1})B_{0}(\beta_{1}) | \psi \rangle \right|^{2}. $$
The total probability to win is given by adding each of the above terms with an appropriate weight:
$$ p_{\text{win}}(\psi) = \frac{1}{4} \left[ p_{\text{win}}(0, 0) + p_{\text{win}}(0, 1) + p_{\text{win}}(1, 0) + p_{\text{win}}(1, 1) \right]. $$
Bell States
If the quantum state \(| \psi \rangle\) is one of the four Bell states
$$ | \Phi^{+} \rangle = \frac{1}{\sqrt{2}} \left( |00\rangle + |11\rangle \right), \quad | \Phi^{-} \rangle = \frac{1}{\sqrt{2}} \left( |00\rangle - |11\rangle \right), \quad | \Psi^{+} \rangle = \frac{1}{\sqrt{2}} \left( |01\rangle + |10\rangle \right), \quad | \Psi^{-} \rangle = \frac{1}{\sqrt{2}} \left( |01\rangle - |10\rangle \right); $$
then the probabilities above greatly simplify.
First, consider \(| \psi \rangle = | \Phi^{+} \rangle\). Then
$$ p_{\text{win}}(0, 0) = \cos^{2}{(\alpha_{0} - \beta_{0})}, \qquad p_{\text{win}}(0, 1) = \cos^{2}{(\alpha_{0} - \beta_{1})}, $$
$$ p_{\text{win}}(1, 0) = \cos^{2}{(\alpha_{1} - \beta_{0})}, \qquad p_{\text{win}}(1, 1) = \sin^{2}{(\alpha_{1} - \beta_{1})}; $$
and thus the probability of winning the game is
$$ p_{\text{win}}(\Phi^{+}) = \frac{1}{4} \left[ \cos^{2}{(\alpha_{0} - \beta_{0})} + \cos^{2}{(\alpha_{0} - \beta_{1})} + \cos^{2}{(\alpha_{1} - \beta_{0})} + \sin^{2}{(\alpha_{1} - \beta_{1})} \right]. $$
For the particular values
$$ \begin{pmatrix} \alpha_{0} & \alpha_{1} & \beta_{0} & \beta_{1} \end{pmatrix} = \begin{pmatrix} 0 & \dfrac{\pi}{4} & \dfrac{\pi}{8} & -\dfrac{\pi}{8} \end{pmatrix}; $$
then
$$ p_{\text{win}}(\Phi^{+}) = \frac{1}{2} + \frac{1}{\sqrt{8}} \approx 0.853553390593274. $$
Apparently, this is the largest possible value for the probability of winning. Currently, I am unable to prove this.
Next, consider the case \(| \psi \rangle = | \Phi^{-} \rangle\). Then
$$ p_{\text{win}}(0, 0) = \cos^{2}{(\alpha_{0} + \beta_{0})}, \qquad p_{\text{win}}(0, 1) = \cos^{2}{(\alpha_{0} + \beta_{1})}, $$
$$ p_{\text{win}}(1, 0) = \cos^{2}{(\alpha_{1} + \beta_{0})}, \qquad p_{\text{win}}(1, 1) = \sin^{2}{(\alpha_{1} + \beta_{1})}; $$
and thus the probability of winning the game is
$$ p_{\text{win}}(\Phi^{-}) = \frac{1}{4} \left[ \cos^{2}{(\alpha_{0} + \beta_{0})} + \cos^{2}{(\alpha_{0} + \beta_{1})} + \cos^{2}{(\alpha_{1} + \beta_{0})} + \sin^{2}{(\alpha_{1} + \beta_{1})} \right]. $$
You can see that if you take the probability of winning for \(| \psi \rangle = | \Phi^{+} \rangle\) and replace
$$ \beta_{0} \rightarrow -\beta_{0}, \qquad \beta_{1} \rightarrow -\beta_{1}; $$
then you get the same expression for the probability of winning for \(| \psi \rangle = | \Phi^{-} \rangle\). That is, for the particular values
$$ \begin{pmatrix} \alpha_{0} & \alpha_{1} & \beta_{0} & \beta_{1} \end{pmatrix} = \begin{pmatrix} 0 & \dfrac{\pi}{4} & -\dfrac{\pi}{8} & \dfrac{\pi}{8} \end{pmatrix}; $$
the probability of winning for \(| \psi \rangle = | \Phi^{-} \rangle\) is maximized.
Next, consider the case \(| \psi \rangle = | \Psi^{+} \rangle\). Then
$$ p_{\text{win}}(0, 0) = \sin^{2}{(\alpha_{0} + \beta_{0})}, \qquad p_{\text{win}}(0, 1) = \sin^{2}{(\alpha_{0} + \beta_{1})}, $$
$$ p_{\text{win}}(1, 0) = \sin^{2}{(\alpha_{1} + \beta_{0})}, \qquad p_{\text{win}}(1, 1) = \cos^{2}{(\alpha_{1} + \beta_{1})}; $$
and thus the probability of winning the game is
$$ p_{\text{win}}(\Psi^{+}) = \frac{1}{4} \left[ \sin^{2}{(\alpha_{0} + \beta_{0})} + \sin^{2}{(\alpha_{0} + \beta_{1})} + \sin^{2}{(\alpha_{1} + \beta_{0})} + \cos^{2}{(\alpha_{1} + \beta_{1})} \right]. $$
You can see that if you take the probability of winning for \(| \psi \rangle = | \Phi^{-} \rangle\) and replace
$$ \alpha_{0} \rightarrow \alpha_{0} + \frac{\pi}{2}, \qquad \alpha_{1} \rightarrow \alpha_{1} + \frac{\pi}{2}; $$
then you get the same expression for the probability of winning for \(| \psi \rangle = | \Psi^{+} \rangle\). That is, for the particular values
$$ \begin{pmatrix} \alpha_{0} & \alpha_{1} & \beta_{0} & \beta_{1} \end{pmatrix} = \begin{pmatrix} \dfrac{\pi}{2} & \dfrac{3\pi}{4} & -\dfrac{\pi}{8} & \dfrac{\pi}{8} \end{pmatrix}; $$
the probability of winning for \(| \psi \rangle = | \Psi^{+} \rangle\) is maximized.
Next, consider the case \(| \psi \rangle = | \Psi^{-} \rangle\). Then
$$ p_{\text{win}}(0, 0) = \sin^{2}{(\alpha_{0} - \beta_{0})}, \qquad p_{\text{win}}(0, 1) = \sin^{2}{(\alpha_{0} - \beta_{1})}, $$
$$ p_{\text{win}}(1, 0) = \sin^{2}{(\alpha_{1} - \beta_{0})}, \qquad p_{\text{win}}(1, 1) = \cos^{2}{(\alpha_{1} - \beta_{1})}; $$
and thus the probability of winning the game is
$$ p_{\text{win}}(\Psi^{-}) = \frac{1}{4} \left[ \sin^{2}{(\alpha_{0} - \beta_{0})} + \sin^{2}{(\alpha_{0} - \beta_{1})} + \sin^{2}{(\alpha_{1} - \beta_{0})} + \cos^{2}{(\alpha_{1} - \beta_{1})} \right]. $$
You can see that if you take the probability of winning for \(| \psi \rangle = | \Phi^{+} \rangle\) and replace
$$ \alpha_{0} \rightarrow \alpha_{0} + \frac{\pi}{2}, \qquad \alpha_{1} \rightarrow \alpha_{1} + \frac{\pi}{2}; $$
then you get the same expression for the probability of winning for \(| \psi \rangle = | \Psi^{-} \rangle\). That is, for the particular values
$$ \begin{pmatrix} \alpha_{0} & \alpha_{1} & \beta_{0} & \beta_{1} \end{pmatrix} = \begin{pmatrix} \dfrac{\pi}{2} & \dfrac{3\pi}{4} & \dfrac{\pi}{8} & -\dfrac{\pi}{8} \end{pmatrix}; $$
the probability of winning for \(| \psi \rangle = | \Psi^{-} \rangle\) is maximized.
Thus, there is a strategy to win the game with a probability larger than the classical 75%.
Reference
This blog post helped me understand how to relate the bits given by the referee to the choices made by Alice and Bob.
