CHSH game in detail

CHSH (John Clauser, Michael Horne, Abner Shimony, and Richard Holt) game is another view on the Bell’s inequalities, showing that under the hood our world is not classical. The game is played by Alice and Bob, and proceeds as follows:

a referee generates two independent uniformly chosen random bits (x and y, also called “questions”) and sends x bit to Alice and y bit to Bob
After receiving the questions, Alice and Bob send their answers back to the referee; an answer is one bit too (a for Alice and b for Bob)
Alice and Bob win if $x \cdot y = a \oplus b$ , where $\oplus$ stands for xor operation.

The game is cooperative – Alice and Bob do not play against each other, their goal is to get the highest winning probability together. Before the game starts, Alice and Bob can communicate and decide on the strategy they will use; after the game started, Alice and Bob are not allowed to communicate anymore; Alice doesn’t know what question the referee sent to Bob, and Bob doesn’t know what question the referee sent to Alice.

In the classical world, Alice and Bob have 16 possible deterministic strategies – both Alice and Bob have two possible answers for each of two possible questions, combining them we get $2^2 \cdot 2^2 = 16$ possible strategies. Since the probability of $x \cdot y = 0$ is 75%, it can be easily seen that there exists 75%-winning strategy – Alice and Bob simply ignore the questions and answer identically – either by bit 0 both or by bit 1 both; it seems natural that this is the best strategy, and it is indeed so, as can be formally shown by checking all 16 possible strategies.

In the quantum world, Alice and Bob have additional degree of freedom – before the game starts, they share an entangled bipartite state, for example two-qubit EPR state:

$|\Psi_{AB}\rangle = \frac{1}{\sqrt{2}}(|0\rangle_A\otimes|0\rangle_B + |1\rangle_A\otimes|1\rangle_B)$

Now, Alice and Bob choose the measurement bases according to the questions they receive from the referee, and answer by measuring their qubits in the chosen bases.

Let us denote the basis vectors as $\nu_i(\theta)$ :

Alice uses $\theta_{A0}$ on receiving the question 0, and $\theta_{A1}$ on receiving the question 1; Bob uses $\theta_{B0}$ on receiving the question 0, and $\theta_{B1}$ on receiving the question 1.

If the referee sends questions $x = 0, y = 0$ , Alice and Bob win if they answer identically $a = 0, b = 0$ or $a = 1, b = 1$ . The correspondent probability of winning (given $x = 0, y = 0$ ) is:

$P(win|x=0,y=0) =$
$|\langle_A\nu_0(\theta_{A0})|\otimes\langle_B\nu_0(\theta_{B0})|\Psi_{AB}\rangle|^2 + |\langle_A\nu_1(\theta_{A0})|\otimes\langle_B\nu_1(\theta_{B0})|\Psi_{AB}\rangle|^2$

Substituting $|\nu_i(\theta)\rangle$ we get
$P(win|x=0,y=0) =$
$|(\cos\theta_{A0} \langle_A 0| + \sin\theta_{A0} \langle_A 1|) \otimes (\cos\theta_{B0} \langle_B 0| + \sin\theta_{B0} \langle_B 1|)|\Psi_{AB}\rangle|^2 +$
$|(\sin\theta_{A0} \langle_A 0| - \cos\theta_{A0} \langle_A 1|) \otimes (\sin\theta_{B0} \langle_B 0| - \cos\theta_{B0} \langle_B 1|)|\Psi_{AB}\rangle|^2$

Substituting $|\Psi_{AB}\rangle$ we get
$P(win|x=0,y=0) =$
$\frac{1}{2}|\cos\theta_{A0} \cos\theta_{B0} + \sin\theta_{A0} \sin\theta_{B0}|^2 + \frac{1}{2}|\sin\theta_{A0} \sin\theta_{B0} + \cos\theta_{A0} \cos\theta_{B0}|^2$

Finally,
$P(win|x=0,y=0) = \cos^2 (\theta_{A0} - \theta_{B0})$

The cases $x = 0, y = 1$ and $x = 1, y = 0$ are similar to $x = 0, y = 0$ : Alice and Bob win if they answer identically:

$P(win|x=0,y=1) =$
$|\langle_A\nu_0(\theta_{A0})|\otimes\langle_B\nu_0(\theta_{B1})|\Psi_{AB}\rangle|^2 + |\langle_A\nu_1(\theta_{A0})|\otimes\langle_B\nu_1(\theta_{B1})|\Psi_{AB}\rangle|^2 =$
$|(\cos\theta_{A0} \langle_A 0| + \sin\theta_{A0} \langle_A 1|) \otimes (\cos\theta_{B1} \langle_B 0| + \sin\theta_{B1} \langle_B 1|)|\Psi_{AB}\rangle|^2 +$
$|(\sin\theta_{A0} \langle_A 0| - \cos\theta_{A0} \langle_A 1|) \otimes (\sin\theta_{B1} \langle_B 0| - \cos\theta_{B1} \langle_B 1|)|\Psi_{AB}\rangle|^2$

$P(win|x=0,y=1) = \cos^2 (\theta_{A0} - \theta_{B1})$

$P(win|x=1,y=0) =$
$|\langle_A\nu_0(\theta_{A1})|\otimes\langle_B\nu_0(\theta_{B0})|\Psi_{AB}\rangle|^2 + |\langle_A\nu_1(\theta_{A1})|\otimes\langle_B\nu_1(\theta_{B0})|\Psi_{AB}\rangle|^2=$
$|(\cos\theta_{A1} \langle_A 0| + \sin\theta_{A1} \langle_A 1|) \otimes (\cos\theta_{B0} \langle_B 0| + \sin\theta_{B0} \langle_B 1|)|\Psi_{AB}\rangle|^2 +$
$|(\sin\theta_{A1} \langle_A 0| - \cos\theta_{A1} \langle_A 1|) \otimes (\sin\theta_{B0} \langle_B 0| - \cos\theta_{B0} \langle_B 1|)|\Psi_{AB}\rangle|^2$

$P(win|x=1,y=0) =\cos^2 (\theta_{A1} - \theta_{B0})$

In the last case $x = 1, y = 1$ Alice and Bob win if they answer differently, so:

$P(win|x=1,y=1) =$
$|\langle_A\nu_0(\theta_{A1})|\otimes\langle_B\nu_1(\theta_{B1})|\Psi_{AB}\rangle|^2 + |\langle_A\nu_1(\theta_{A1})|\otimes\langle_B\nu_0(\theta_{B1})|\Psi_{AB}\rangle|^2=$

$|(\cos\theta_{A1} \langle_A 0| + \sin\theta_{A1} \langle_A 1|) \otimes (\sin\theta_{B1} \langle_B 0| - \cos\theta_{B1} \langle_B 1|)|\Psi_{AB}\rangle|^2 +$
$|(\sin\theta_{A1} \langle_A 0| - \cos\theta_{A1} \langle_A 1|) \otimes (\cos\theta_{B1} \langle_B 0| + \sin\theta_{B1} \langle_B 1|)|\Psi_{AB}\rangle|^2=$

$\frac{1}{2}|\cos\theta_{A1} \sin\theta_{B1} - \sin\theta_{A1} \cos\theta_{B1}|^2 + \frac{1}{2}|\sin\theta_{A1} \cos\theta_{B1} - \cos\theta_{A1} \sin\theta_{B1}|^2$

$P(win|x=1,y=1) = \sin^2 (\theta_{A1} - \theta_{B1})$

Putting it all together:

$P(win) = \frac{1}{4}(P(win|x=0,y=0) + P(win|x=0,y=1)+ P(win|x=1,y=0)+ P(win|x=1,y=1)) =$
$\frac{1}{4}(\cos^2 (\theta_{A0} - \theta_{B0})+\cos^2 (\theta_{A0} - \theta_{B1})+\cos^2 (\theta_{A1} - \theta_{B0})+\sin^2 (\theta_{A1} - \theta_{B1}))$

if Alice and Bob choose $\{\theta_{A0}=0, \theta_{A1}=\frac{\pi}{4}, \theta_{B0}=\frac{\pi}{8}, \theta_{B1}=-\frac{\pi}{8}\}$ , then

$P(win) = \frac{3}{4} \cos^2 \frac{\pi}{8} + \frac{1}{4} \sin^2 \frac{3\pi}{8}= \cos^2 \frac{\pi}{8} = \frac{1+cos \frac{\pi}{4}}{2}= \frac{1}{2} + \frac{1}{2\sqrt{2}}\approx 0.85355$

and we obtain the winning probability above 85%, which is significantly better than classical 75%.

8 thoughts on “CHSH game in detail”

sglienke says:

October 26, 2016 at 4:07 pm

Can you please consider changing your font? The bs, ds and us are making my eyes bleed 😉

- Serg says:
  
  October 26, 2016 at 7:02 pm
  
  Changed to some sans serif. Hope it is better now. 🙂
  
mark says:

November 27, 2016 at 10:07 am

How did you choose theta for Alice and Bob?

- Serg says:
  
  November 27, 2016 at 10:34 am
  
  Well I didn’t. I just know that the chosen thetas maximize the winning probability; the proof that the max winning probability is 1/2+1/(2*sqrt(2)) (Tsirelson’s bound) can be found in Watrous lectures – https://cs.uwaterloo.ca/~watrous/CPSC519/LectureNotes/20.pdf
  
Omkar says:

December 20, 2016 at 2:54 pm

Great explanation !! Please keep posting similar things.

Bhanu Prakash says:

December 1, 2019 at 2:42 pm

Thanks for the article!!

Pingback: Kwantowa gra Johna Bella | Nie od razu naukę zbudowano
Tko says:

January 24, 2021 at 7:42 pm

Click to access lecture2.pdf

For a bit more explanation of EPR pair etc.