Prerequisite knowledge:
Let's start with a quick recap of how the CHSH game is played: There are 2 players, Alice and Bob, and a referee, Charlie. Alice and Bob are in separate rooms, they cannot communicate. Charlie gives Alice a random bit \(x \in \left\{ 0, 1 \right\}\). He also gives Bob a random bit \(y \in \left\{ 0, 1 \right\}\). Alice must return a bit \(a \in \left\{ 0, 1 \right\}\) and Bob must return a bit \(b \in \left\{ 0, 1 \right\}\). They win if \(x \wedge y = a \oplus b\), where \(\oplus\) denotes the XOR operation.
For example, if Alice gets \(x=1\) and Bob gets \(y=0\), then \(x \wedge y = 1 \wedge 0 = 0\) and the winning combinations are \(a=0, b=0\) and \(a=1, b=1\), because in those cases \(a \oplus b = 0\).
In the classical solution, Alice and Bob can simply always both return 0. Then, they will win all cases, except when they both get a 1 from Charlie. This is a win rate of 75%. As it turns out, they cannot actually do better than that. However, if they share an entangled pair of qubits, they can significantly improve those odds.
We will go through a detailed, step-by-step explanation of the quantum solution in a bit, but first, let me explain why I wrote this article in the first place. After all, there are already quite a few explanations of this on the Internet. The traditional explanations of how this quantum solution works, often use these "rotated hooks" as measuring bases for Alice and Bob:
The equations for Bob's measuring bases (the green arrows) are then as follows:
\[
\begin{aligned}
\left| m_0 \right\rangle &= \cos \frac{\pi}{8} \left| 0 \right\rangle + \sin \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\left| m_1 \right\rangle &= -\sin \frac{\pi}{8} \left| 0 \right\rangle + \cos \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\left| n_0 \right\rangle &= \cos \frac{\pi}{8} \left| 0 \right\rangle - \sin \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\left| n_1 \right\rangle &= \sin \frac{\pi}{8} \left| 0 \right\rangle + \cos \frac{\pi}{8} \left| 1 \right\rangle
\end{aligned}
\]
When I was studying this, the approach wasn't immediately clear to me. Why do we need those rotated hooks? They are supposed to be rotated \( \frac{\pi}{8} \) from each other, but why do they have to be rotated about those specific angles? Can't they be rotated about any other angle? And those equations... what's the pattern there? They don't seem to have any kind of symmetry?
A few weeks before this, I had studied the Bloch Sphere extensively. I thought, you know what? Let's use the Bloch Sphere instead and see what happens! Since we didn't seem to need complex numbers here, I took the projection of the Bloch Sphere along the \( x-z \) axes, basically with \( \phi = 0 \). State vectors in this plane can then be expressed as follows:
\[
\begin{aligned}
\left| v \right\rangle &= \cos \frac{\theta}{2} \left| 0 \right\rangle + e^{i\phi} \sin \frac{\theta}{2} \left| 1 \right\rangle &(\text{Bloch sphere equation}) \\[5pt]
&= \cos \frac{\theta}{2} \left| 0 \right\rangle + \sin \frac{\theta}{2} \left| 1 \right\rangle &(\phi = 0)
\end{aligned}
\]
According to the standard quantum solution to the CHSH game, we need 4 measuring bases that are rotated \( \frac{\pi}{8} \) from each other. We will look at how to use these to solve the game later, but first, let's draw them. As you can see above, the Bloch Sphere equation divides the z-angle by 2. So in order to express 4 measuring bases that are rotated \( \frac{\pi}{8} \) from each other, we need to rotate them \( \frac{\pi}{4} \) from each other on the Bloch Sphere. In the \( x-z \) plane (with \( \phi = 0 \)), this then looks as follows:
\[
\begin{aligned}
\left| 0 \right\rangle &= \cos \frac{0}{2} \left| 0 \right\rangle + \sin \frac{0}{2} \left| 1 \right\rangle
&&= \left| 0 \right\rangle \\[5pt]
\left| 1 \right\rangle &= \cos \frac{\pi}{2} \left| 0 \right\rangle + \sin \frac{\pi}{2} \left| 1 \right\rangle
&&= \left| 1 \right\rangle \\[5pt]
\left| + \right\rangle &= \cos \frac{\frac{1}{2} \pi}{2} \left| 0 \right\rangle + \sin \frac{\frac{1}{2} \pi}{2} \left| 1 \right\rangle
&&= \frac{1}{\sqrt{2}} \left| 0 \right\rangle + \frac{1}{\sqrt{2}} \left| 1 \right\rangle \\[5pt]
\left| - \right\rangle &= \cos \frac{-\frac{1}{2} \pi}{2} \left| 0 \right\rangle + \sin \frac{-\frac{1}{2} \pi}{2} \left| 1 \right\rangle
&&= \frac{1}{\sqrt{2}} \left| 0 \right\rangle - \frac{1}{\sqrt{2}} \left| 1 \right\rangle \\[5pt]
\end{aligned}
\]
Now for Bob's. Let's see if they will be any different than the ones from the "rotated hooks" approach. By the way, if you're working with the Bloch Sphere a lot, this page is your friend!
\[
\begin{aligned}
\left| m_0 \right\rangle &= \cos \frac{\frac{1}{4} \pi}{2} \left| 0 \right\rangle + \sin \frac{\frac{1}{4} \pi}{2} \left| 1 \right\rangle
&&= \cos \frac{\pi}{8} \left| 0 \right\rangle + \sin \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\left| m_1 \right\rangle &= \cos \frac{-\frac{3}{4} \pi}{2} \left| 0 \right\rangle + \sin \frac{-\frac{3}{4} \pi}{2} \left| 1 \right\rangle
&&= \sin \frac{\pi}{8} \left| 0 \right\rangle - \cos \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\left| n_0 \right\rangle &= \cos \frac{-\frac{1}{4} \pi}{2} \left| 0 \right\rangle + \sin \frac{-\frac{1}{4} \pi}{2} \left| 1 \right\rangle
&&= \cos \frac{\pi}{8} \left| 0 \right\rangle - \sin \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\left| n_1 \right\rangle &= \cos \frac{\frac{3}{4} \pi}{2} \left| 0 \right\rangle + \sin \frac{\frac{3}{4} \pi}{2} \left| 1 \right\rangle
&&= \sin \frac{\pi}{8} \left| 0 \right\rangle + \cos \frac{\pi}{8} \left| 1 \right\rangle \\[5pt]
\end{aligned}
\]
That's interesting! The equations for \(\left| m_0 \right\rangle\), \(\left| n_0 \right\rangle\) and \(\left| n_1 \right\rangle\)are the same, but the one for \(\left| m_1 \right\rangle\) is now multiplied by a factor of -1! This is a global phase, so it won't affect any measurement, but it does mean that the equations now look perfectly symmetrical!
(For the astute reader, who notices that \(\theta\) should ideally always be in the range \([0,\pi]\): if you remove the minuses from the \(\theta = -\frac{1}{4} \pi\), \(\theta = -\frac{1}{2} \pi\) and \(\theta = -\frac{3}{4} \pi\) values and calculate those vectors with \(\phi = \pi\) instead, you will see that it will lead to exactly the same outcomes, since \(\cos-\theta = \cos\theta\), \(\sin-\theta = -\sin\theta\) and \(e^{i\pi} = -1\). I thought I'd keep it simple by leaving the complex numbers out of this article.)
By moving all bases to the Bloch Sphere, we have obtained a perfectly even and symmetrical distribution of basis vectors, with perfectly symmetrical equations. This is going to help a lot in understanding why the quantum solution to the CHSH game works. But before we get there, let's have a look at the actual quantum strategy.
The Quantum Strategy for the CHSH Game
In the Quantum Strategy, Alice and Bob share an entangled pair of qubits. More precisely, they share a Bell Pair: \(\left| \psi \right\rangle = \frac{1}{\sqrt{2}} \left| 00 \right\rangle + \frac{1}{\sqrt{2}} \left| 11 \right\rangle\). We have 4 bases for measuring a qubit: \(\{\left| 0 \right\rangle, \left| 1 \right\rangle\}\) and \(\{\left| + \right\rangle, \left| - \right\rangle\}\) for Alice and \(\{\left| m_0 \right\rangle, \left| m_1 \right\rangle\}\) and \(\{\left| n_0 \right\rangle, \left| n_1 \right\rangle\}\) for Bob. These bases are orthogonal, which is illustrated by the fact that their vectors lie on opposite ends of the Bloch Sphere.
The trick is, that Alice and Bob use their input bit (resp. \(x\) and \(y\)) to determine which basis they will use for measuring their half of the entangled pair. They will then use the result of their measurement to determine their output bit (resp. \(a\) and \(b\)). They will do this according to the following schema, where the colors illustrate what the value of their output bit will be:
\[
\begin{aligned}
x = 0\!:\quad &\text{Alice measures in} & \{ &\bbox[#b3fff0, 3px]{\left| 0 \right\rangle}, & &\bbox[#ecb3ff, 3px]{\left| 1 \right\rangle} \} \\
x = 1\!:\quad &\text{Alice measures in} & \{ &\bbox[#b3fff0, 3px]{\left| + \right\rangle}, & &\bbox[#ecb3ff, 3px]{\left| - \right\rangle} \} \\
& & &\downarrow & &\downarrow \\
&\text{Alice returns} &a =\ &\bbox[#b3fff0, 3px]{0} & &\bbox[#ecb3ff, 3px]{1} \\[20pt]
y = 0\!:\quad &\text{Bob measures in} & \{ &\bbox[#b3ffb3, 3px]{\left| m_0 \right\rangle}, & &\bbox[#ffcccc, 3px]{\left| m_1 \right\rangle} \} \\
y = 1\!:\quad &\text{Bob measures in} & \{ &\bbox[#b3ffb3, 3px]{\left| n_0 \right\rangle}, & &\bbox[#ffcccc, 3px]{\left| n_1 \right\rangle} \} \\
& & &\downarrow & &\downarrow \\
&\text{Bob returns} &b =\ &\bbox[#b3ffb3, 3px]{0} & &\bbox[#ffcccc, 3px]{1}
\end{aligned}
\]
There are four possible cases, because both \(x\) and \(y\) can be 0 or 1. We will explore two of these cases in detail, the other two will be left as an exercise for the reader. After exploring the two cases, we will have a look at why this strategy actually works.
Case 1
Let's test the first case! In this case, \(x = 0\) and \(y = 0\), so \(x \wedge y = 0\). \(a \oplus b\) must then also be 0. This is true if \(a = b = 0\) or \(a = b = 1\).
Since \(x = 0\), Alice will measure in the \(\{\left| 0 \right\rangle, \left| 1 \right\rangle\}\) basis and since \(y = 0\), Bob will measure in the \(\{\left| m_0 \right\rangle, \left| m_1 \right\rangle\}\) basis. This means that we either want Alice to get \(\left| 0 \right\rangle\) and Bob to get \(\left| m_0 \right\rangle\), or Alice to get \(\left| 1 \right\rangle\) and Bob to get \(\left| m_1 \right\rangle\).
The probability of the first one, Alice getting \(\left| 0 \right\rangle\) and Bob getting \(\left| m_0 \right\rangle\), is calculated as follows:
\[
\begin{aligned}
\left\|
(\left\langle 0 \right| \otimes \left\langle m_0 \right|) \left| \psi \right\rangle
\right\|^{2} &=
\left\|
\left(
\begin{bmatrix}
\overline{1} & \overline{0}
\end{bmatrix}
\otimes
\begin{bmatrix}
\overline{\cos \frac{\pi}{8}} & \overline{\sin \frac{\pi}{8}}
\end{bmatrix}
\right)
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\begin{bmatrix}
\cos \frac{\pi}{8} & \sin \frac{\pi}{8} & 0 & 0
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\frac{1}{\sqrt{2}}\cos \frac{\pi}{8}
\right\|^{2} \\[5pt]
&= \frac{1}{2}\cos^2 \frac{\pi}{8}
\end{aligned}
\]
The probability of the second one, Alice getting \(\left| 1 \right\rangle\) and Bob getting \(\left| m_1 \right\rangle\), is calculated as follows:
\[
\begin{aligned}
\left\|
(\left\langle 1 \right| \otimes \left\langle m_1 \right|) \left| \psi \right\rangle
\right\|^{2} &=
\left\|
\left(
\begin{bmatrix}
\overline{0} & \overline{1}
\end{bmatrix}
\otimes
\begin{bmatrix}
\overline{\sin \frac{\pi}{8}} & \overline{-\cos \frac{\pi}{8}}
\end{bmatrix}
\right)
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\begin{bmatrix}
0 & 0 & \sin \frac{\pi}{8} & -\cos \frac{\pi}{8}
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
-\frac{1}{\sqrt{2}}\cos \frac{\pi}{8}
\right\|^{2} \\[5pt]
&= \frac{1}{2}\cos^2 \frac{\pi}{8}
\end{aligned}
\]
They win if either will happen, which, by summing the two separate values, has probability:
\[
\frac{1}{2}\cos^2 \frac{\pi}{8} \ +\ \frac{1}{2}\cos^2 \frac{\pi}{8} \ =\ \cos^2 \frac{\pi}{8} \ \approx\ 0.85 \ =\ 85\%
\]
This is significantly better than the win rate of 75% for the classical solution, although that 75% was for all cases combined, not just one case, so let's move on!
Case 2
For the second case, we take \(x = 1\) and \(y = 1\), so \(x \wedge y = 1\). \(a \oplus b\) must then also be 1. This is true if \(a = 0\) and \(b = 1\) or if \(a = 1\) and \(b = 0\).
Since \(x = 1\), Alice will measure in the \(\{\left| + \right\rangle, \left| - \right\rangle\}\) basis and since \(y = 1\), Bob will measure in the \(\{\left| n_0 \right\rangle, \left| n_1 \right\rangle\}\) basis. This means that we either want Alice to get \(\left| + \right\rangle\) and Bob to get \(\left| n_1 \right\rangle\), or Alice to get \(\left| - \right\rangle\) and Bob to get \(\left| n_0 \right\rangle\).
The probability of the first one, Alice getting \(\left| + \right\rangle\) and Bob getting \(\left| n_1 \right\rangle\), is calculated as follows:
\[
\begin{aligned}
\left\|
(\left\langle + \right| \otimes \left\langle n_1 \right|) \left| \psi \right\rangle
\right\|^{2} &=
\left\|
\left(
\begin{bmatrix}
\overline{\frac{1}{\sqrt{2}}} & \overline{\frac{1}{\sqrt{2}}}
\end{bmatrix}
\otimes
\begin{bmatrix}
\overline{\sin \frac{\pi}{8}} & \overline{\cos \frac{\pi}{8}}
\end{bmatrix}
\right)
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\begin{bmatrix}
\frac{1}{\sqrt{2}}\sin \frac{\pi}{8} & \frac{1}{\sqrt{2}}\cos \frac{\pi}{8} & \frac{1}{\sqrt{2}}\sin \frac{\pi}{8} & \frac{1}{\sqrt{2}}\cos \frac{\pi}{8}
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\frac{1}{2}\sin \frac{\pi}{8} + \frac{1}{2}\cos \frac{\pi}{8}
\right\|^{2} \\[5pt]
&= \frac{1}{4}\sin^2 \frac{\pi}{8} \ +\ \frac{1}{2} \sin\frac{\pi}{8} \cos\frac{\pi}{8} \ +\ \frac{1}{4}\cos^2 \frac{\pi}{8}
\end{aligned}
\]
The probability of the second one, Alice getting \(\left| - \right\rangle\) and Bob getting \(\left| n_0 \right\rangle\), is calculated as follows:
\[
\begin{aligned}
\left\|
(\left\langle - \right| \otimes \left\langle n_0 \right|) \left| \psi \right\rangle
\right\|^{2} &=
\left\|
\left(
\begin{bmatrix}
\overline{\frac{1}{\sqrt{2}}} & \overline{-\frac{1}{\sqrt{2}}}
\end{bmatrix}
\otimes
\begin{bmatrix}
\overline{\cos \frac{\pi}{8}} & \overline{-\sin \frac{\pi}{8}}
\end{bmatrix}
\right)
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\begin{bmatrix}
\frac{1}{\sqrt{2}}\cos \frac{\pi}{8} & -\frac{1}{\sqrt{2}}\sin \frac{\pi}{8} & -\frac{1}{\sqrt{2}}\cos \frac{\pi}{8} & \frac{1}{\sqrt{2}}\sin \frac{\pi}{8}
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}
\end{bmatrix}
\right\|^{2} \\[5pt]
&= \left\|
\frac{1}{2}\cos \frac{\pi}{8} + \frac{1}{2}\sin \frac{\pi}{8}
\right\|^{2} \\[5pt]
&= \frac{1}{4}\cos^2 \frac{\pi}{8} \ +\ \frac{1}{2} \cos\frac{\pi}{8} \sin\frac{\pi}{8} \ +\ \frac{1}{4}\sin^2 \frac{\pi}{8}
\end{aligned}
\]
They win if either will happen, which, by summing the two separate values, has the following probability (again, keep this one at hand!):
\[
\begin{aligned}
&\frac{1}{2}\cos^2 \frac{\pi}{8} \ +\ \cos\frac{\pi}{8} \sin\frac{\pi}{8} \ +\ \frac{1}{2}\sin^2 \frac{\pi}{8} \\[5pt]
=\ &\frac{1}{2}\left( \cos^2 \frac{\pi}{8} + \sin^2 \frac{\pi}{8} \right) \ +\ \cos\frac{\pi}{8} \sin\frac{\pi}{8} \\[5pt]
=\ &\frac{1}{2} \ +\ \cos\frac{\pi}{8} \sin\frac{\pi}{8} \\[5pt]
=\ &\frac{1}{2} \ +\ \frac{1}{2}\sin\left( \frac{\pi}{8} + \frac{\pi}{8} \right) \ -\ \frac{1}{2}\sin\left( \frac{\pi}{8} - \frac{\pi}{8} \right) \\[5pt]
=\ &\frac{1}{2} \ +\ \frac{1}{2}\sin\frac{\pi}{4} \ -\ \frac{1}{2}\sin 0 \\[5pt]
=\ &\frac{1}{2} \ +\ \frac{1}{2}\cos\frac{\pi}{4} \\[5pt]
=\ &\frac{1 + \cos\left( 2 \cdot \frac{\pi}{8} \right)}{2} \\[5pt]
=\ &\cos^2 \frac{\pi}{8} \ \approx\ 0.85 \ =\ 85\%
\end{aligned}
\]
Success again! It turns out that the other two cases also resolve to a win rate of \( \cos^2 \frac{\pi}{8} \), meaning that \( \cos^2 \frac{\pi}{8} \) is actually the overall win rate for all cases combined. So, why is this?
Why does this work?
To see why the Quantum Strategy always gives the same probability for each of the cases, let's have a look at the outcomes that we want for each case:
\[
\begin{aligned}
&\text{For}\ x = 0, y = 0, \text{we want outcome}
\left\{ \left| 0 \right\rangle, \left| m_0 \right\rangle \right\}\ \text{or}
\left\{ \left| 1 \right\rangle, \left| m_1 \right\rangle \right\} \\[5pt]
&\text{For}\ x = 0, y = 1, \text{we want outcome}
\left\{ \left| 0 \right\rangle, \left| n_0 \right\rangle \right\}\ \text{or}
\left\{ \left| 1 \right\rangle, \left| n_1 \right\rangle \right\} \\[5pt]
&\text{For}\ x = 1, y = 0, \text{we want outcome}
\left\{ \left| + \right\rangle, \left| m_0 \right\rangle \right\}\ \text{or}
\left\{ \left| - \right\rangle, \left| m_1 \right\rangle \right\} \\[5pt]
&\text{For}\ x = 1, y = 1, \text{we want outcome}
\left\{ \left| + \right\rangle, \left| n_1 \right\rangle \right\}\ \text{or}
\left\{ \left| - \right\rangle, \left| n_0 \right\rangle \right\} \\[5pt]
\end{aligned}
\]
Now have a look at all of these desired outcomes on the Bloch Sphere. Their vectors are always right next to each other! Because Alice's and Bob's qubits are entangled, the closer the measuring bases are to each other, the higher the probability that the outcomes are close to each other as well. This maximizes the probability that Alice and Bob will indeed measure a result that will win them the game. The Bloch Sphere makes this much more obvious than the "rotated hooks".
Moreover, it is also clear that a win rate of \( \cos^2 \frac{\pi}{8} \) is indeed the maximum win rate that is achievable when Alice and Bob share an entangled pair (as is proven by Tsirelson's bound). This is because there is no other way to distribute 4 bases on the Bloch Sphere that is more optimal than this one. Move two vectors of a desired outcome closer to each other, and two other ones will move away from each other. You can't do better than the perfectly symmetrical distribution.
Conclusion
Playing the CHSH game on the Bloch Sphere gives us a symmetrical distribution of measuring bases, along with symmetrical equations for those bases. It provides an intuitive insight into why the Quantum Strategy works and why it is indeed the most optimal strategy possible.
This approach has helped me understand the CHSH game a lot better. I hope it will be useful to others as well!