We shall call the two players 2 players Alice and Bob. We will also have Charlie as a referee that decides if Alice and Bob wins the game. They can decide on any strategy before the game commences but they cannot communicate with each other once the game starts.
To begin, Charlie picks two uniformly random bits $x$ and $y$, and gives $x$ to Alice and $y$ to Bob. Alice answers the referee with bit $a$, while Bob replies with bit $b$. After getting $a$ and $b$, Charlie checks whether
$a \oplus b = xy \mod{2}$,
that is, that the XOR of the output bits $a$ and $b$ is equal to the AND of input bits $x$ and $y$. If so, then Alice and Bob win the game.
So for Alice and Bob to win, their output bits need to satisfy the following conditions:
$x$ $y$ Alice and Bob win if
0 0 $a = b$
0 1 $a = b$
1 0 $a = b$
1 1 $a = b \oplus 1$
Now let us compare classical and quantum strategies for playing the game. A classical strategy is any method for Alice to output $a$ given $x$, and similarly for Bob to output $b$ given $y$ that uses only classical information and no communication between them (which is why Bob does not know $x$ and Alice does not know $y$). A quantum strategy allows Alice and Bob to use a shared quantum state and perform measurements on it to decide their output bits.
The interesting question to ask here is whether a quantum strategy allows Alice and Bob to win the CHSH game with a higher success rate than any classical strategy. For this, we need to find and compare the optimal winning strategies in each situation.
For classical strategies, Alice and Bob may try to output 0 or 1 with some probability, depending on the value of $x$ or $y$, respectively. However, it can be shown that these probabilistic strategies can always be achieved by some deterministic strategy that outputs a a specific value. That is, Alice can always do better by just mapping $x$ to a particular value for $a$ and same for Bob mapping $y$ to a particular value for $b$.
If we know that deterministic strategies are best, then it is straightforward to check that the best winning probability is $\frac{3}{4} = 75 \%$, which can be achieved by the trivial strategy of outputting $a = b = 0$, whatever $x$ and $y$ may be.
Is there a quantum strategy that does better? Indeed there is and we will describe it here. First, Alice and Bob need to share the entangled two-qubit state
$|S\rangle = \left( |0,0\rangle + |1,1\rangle \right) / \sqrt{2}$,
where the first qubit belongs to Alice and the second qubit belongs to Bob.
To know what $a$ and $b$ values to output, Alice and Bob perform measurements on their share of $|S\rangle$. Here we mention the measurement bases they need to use, where the first state in each basis corresponds to outputting 0, and the second state corresponds to outputting 1.
Alice $x$ measure in basis
0 $|0 \rangle, |1 \rangle$
1 $|+\rangle, |-\rangle$
Bob $y$ measure in basis
0 $|u_{0} \rangle , |u_{1} \rangle$
1 $|v_{0} \rangle , |v_{1} \rangle$
where we have
$|+\rangle = \left( |0\rangle + |1\rangle \right) / \sqrt{2}, \quad |-\rangle = \left( |0\rangle - |1\rangle \right) / \sqrt{2}$,
$|u_{0}\rangle = \cos{u} |0\rangle + \sin{u} |1\rangle, \quad |u_{1}\rangle = -\sin{u} |0\rangle + \cos{u} |1\rangle $,
$|v_{0}\rangle = \cos{v} |0\rangle + \sin{v} |1\rangle, \quad |v_{1}\rangle = -\sin{v} |0\rangle + \cos{v} |1\rangle $
for $u = \pi/8$ and $v = -u$.
The bases are shown in the figure below, where $|0\rangle$ and $|1\rangle$ correspond to vectors on the horizontal and vertical axis of the plane, respectively.
 | |
|
To compute the winning probability for this quantum strategy, we compute the probability for getting $a = b$ when $x$ and $y$ are not both 1, and the probability of getting $a \oplus b = 1$ when $x = y = 1$. For this, it is useful to know that
$|S\rangle = \left( |+,+\rangle + |-,-\rangle \right) / \sqrt{2}$.
The calculation is tedious but straightforward so we will just show a few details:
$xy$ Pr[win | $xy$ ]
00 $ | \langle 0, u_0 | S \rangle |^2 + | \langle 1, u_1 | S \rangle |^2 = 2 | \cos u / \sqrt{2} |^2 = \cos^2{u}$
01 $ | \langle 0, v_0 | S \rangle |^2 + | \langle 1, v_1 | S \rangle |^2 = 2 | \cos v / \sqrt{2} |^2 = \cos^2{v} = \cos^2{u}$
10 $| \langle +, u_0 | S \rangle |^2 + | \langle -, u_1 | S \rangle |^2 = 2 | ( \cos u + \sin u) / 2 |^2 = (1 + \sin{2u})/2 = cos^2{u} $
11 $ | \langle +, v_1 | S \rangle |^2 + | \langle -, v_0 | S \rangle |^2 = 2 | ( \cos v - \sin v) / 2 |^2 = (1 - \sin{2v})/2 = \cos^2{u} $
where we used $\cos(-u) = \cos u, \sin(-u) = - \sin u$, and $\cos{2u} = \sin{2u}$ for $u = \pi/8$. Because each combination of $x$ and $y$ is equally likely, we obtain $\mathrm{Pr[win]} = \cos^2{\pi/8}$.
Since $\cos^2{\pi/8}= 0.8536 > 0.75$, this optimal quantum strategy is better than the optimal classical strategy by over 10%.
 |
| A summary of the CHSH game. Alice and Bob receive input bits $x$ and $y$ from Charlie. Their goal is to answer with output bits $a$ and $b$ such that $a \oplus b = x \cdot y$. Alice and Bob cannot communicate during the game but they can decide on a strategy beforehand. In the quantum version of the game, Alice and Bob are allowed to share a quantum state and make measurements on it. Shown above is the optimal quantum strategy, where $|\psi\rangle$ is a maximally entangled two-qubit state, and the circles below Alice and Bob depict what measurement each should perform for input bit 0 or 1. |
John Watrous, Bell inequalities and nonlocality (2016).
Mark Wilde, CHSH game, Bell's theorem, and Tsirelson's bound (2015).
Should the definition of |−⟩ have a - in front of the |0⟩?
ReplyDeleteThis reply is way too late but indeed it should have a minus sign. The correction has been made. Thanks.
ReplyDelete