I want to use this addendum to discuss the CHSH game, which is another cool example of quantum pseudo-telepathy but one that's a little less strong than the GHZ game since victory is not guaranteed.
The CHSH game was formulated by Clauser, Horne, Shimony, and Holt in 1969. Clauser was a Columbia professor, Holt was a Harvard professor, and Horne and Shimony were BU professors.
The setup is somewhat similar to the GHZ game, but with only two players, Alice and Bob, who are cooperating against a referee. The referee chooses two bits $x$ and $y$ which can be either $0$ or $1$, and gives $x$ to Alice and $y$ to Bob.
Alice then responds with her own bit $a$ and Bob responds with his own bit $b$. Alice and Bob cannot communicate once they receive their bits.
If $x$ and $y$ are both 1, then Alice and Bob win when $a \neq b$. Otherwise, they win when $a = b$. This win condition is often formulated as $$ a \oplus b = x \land y $$ where $\oplus$ denotes an XOR operation (1 when $a \neq b$ and 0 when $a=b$) and $\land$ denotes an AND operation (1 when $x=y=1$ and 0 otherwise).
A deterministic strategy would assign what bit Alice and Bob should send back based on what bit they receive.
| Player | $0$ | $1$ |
|---|---|---|
| $A$ | $a$ | $c$ |
| $B$ | $b$ | $d$ |
Here, we know that in a solution that always works, $a=b$, $a=d$, $b=c$, and $c \neq d$. However, this set of equivalences is logically impossible. Plugging $a$ into the third and fourth equations shows that $a \neq a$, which means that this ideal strategy cannot exist.
It turns out, like in the GHZ game, that you cannot do better than 75% accuracy using a classical deterministic strategy.
Unlike the GHZ game, though, it also turns out that you cannot guarantee victory using a quantum computer either. But you can do better.
Let's say that Alice and Bob each share a qubit in $|\Phi^{+}\rangle$. Alice measures in the computational basis if she gets a $0$ and measures in the X basis if she gets a $1$. If her qubit collapses to $|0\rangle$ or $|+\rangle$, she gives back a $0$, and if it collapses to $|1\rangle$ or $|-\rangle$, she gives back a $1$.
I want to derive the basis Bob should measure in to ensure the highest probability, since it is pretty unusual compared to the bases we've measured in for the other problems we've looked at.
Remember that for two qubits $|\alpha\rangle$ and $|\beta\rangle$, their "correlation" should be $\langle \alpha | \beta \rangle$, which is essentially just the dot product $\alpha \cdot \beta$. Since $\alpha \cdot \beta = |\alpha||\beta|\cos\theta = \cos\theta$, where $\theta$ is the angle between $\alpha$ and $\beta$, the probability that $\alpha = \beta$ is
$$ \frac{1+(\alpha \cdot \beta)}{2} = \frac{1+\cos{\theta}}{2} = \cos^2 \frac{\theta}{2}. $$We know that Alice is measuring along the z-axis (i.e. along $|0\rangle$ and $|1\rangle$; I will take the former) when she gets a $0$ and along the x-axis (i.e. along $|+\rangle$ or $|-\rangle$; I will again take the former) when she gets a $1$.
Let's say Bob measures along $\beta_0$ when he gets a $0$ and $\beta_1$ when he gets a $1$. We want to maximize $\langle 0 | \beta_0\rangle$, $\langle 0 | \beta_1\rangle$, and $\langle + | \beta_0\rangle$, and minimize $\langle + | \beta_1\rangle$.
Try to play with the demo below and see if you can find the configuration that achieves this setup the best it can.
In fact, it is the starting configuration I gave you, where
$$ |\beta_0\rangle = \frac{|0\rangle+|+\rangle}{\sqrt{2}} \qquad |\beta_1\rangle = \frac{|1\rangle+|+\rangle}{\sqrt{2}} $$This is not exactly precise, as these states are not normalized. But it is the best intuition I can think of to express why Bob's basis is the way it is.
Let's make this rigorous. When we normalize and generalize what we've written, it turns out that if Bob gets a $0$, he should measure in the basis $\{|s_0\rangle, |s_1\rangle\}$, which is
$$ \left\{\cos\left(\frac{\pi}{8}\right)|0\rangle+\sin\left(\frac{\pi}{8}\right)|1\rangle, -\sin\left(\frac{\pi}{8}\right)|0\rangle+\cos\left(\frac{\pi}{8}\right)|1\rangle\right\} $$and if he gets a $1$, he should measure in the basis $\{|t_0\rangle, |t_1\rangle\}$, which is
$$ \left\{\cos\left(\frac{\pi}{8}\right)|0\rangle-\sin\left(\frac{\pi}{8}\right)|1\rangle, \sin\left(\frac{\pi}{8}\right)|0\rangle+\cos\left(\frac{\pi}{8}\right)|1\rangle\right\} $$As an example, let's say that Alice and Bob both get a $0$. The probability of them winning is around 85% regardless if Alice measures $|0\rangle$ or $|1\rangle$.
$$ |\langle 0 | s_0\rangle|^2 = \cos^2 \frac{\pi}{8} \approx 0.8536 \qquad |\langle 1 | s_1\rangle|^2 = \cos^2 \frac{\pi}{8} \approx 0.8536 $$Similarly, if Alice and Bob both get a $1$, the probability is the same.
$$ |\langle + | t_1\rangle|^2 = \cos^2 \frac{\pi}{8} \approx 0.8536 \qquad |\langle - | t_0\rangle|^2 = \cos^2 \frac{\pi}{8} \approx 0.8536 $$The probability remains the same when their bits differ, since $|\langle 0 | t_0\rangle|^2 = |\langle 1 | t_1\rangle|^2 = |\langle + | s_0\rangle|^2 = |\langle - | s_1\rangle|^2 \approx 0.8536$.
Therefore, this quantum approach always gives Alice and Bob an approximately 85% chance of winning, which is a bit better than the best classical approach at 75%.
This is maybe a bit more honest as to the type of quantum advantages you normally see when working with quantum algorithms. Problems like the GHZ game are the exception, not the norm.