6.8 Remarks and exercises

6.8.1 XOR games

The setup of the CHSH inequality that we have described can instead be imagined as a two-player all-or-nothing game between Alice and Bob, so let’s study this type of game more generally.

Alice and Bob each start with an integer prompt a and b (respectively), with 1\leqslant a,b\leqslant n. This integer can come from anywhere: they could pick it themselves, or it could be given to them. Having seen this integer, a round of the game consists of them returning an answer, x and y (respectively), of length m bits to an oracle. Both the prompt and the answer are kept secret, so that only the corresponding player knows them.
They win if the winning condition computed by the oracle is 1, and lose if it is 0. The winning condition is given by \begin{cases} 1 & \text{if }g_A(x,a,b) = g_B(y,a,b) \\0 & \text{if }g_A(x,a,b) \neq g_B(y,a,b) \end{cases} where g_A and g_B are deterministic one-bit-valued functions whose output values are equally likely to be 0 or 1 (i.e. they return the value 0 for exactly half of the possible input triples).
There exists a quantum strategy that always wins. It uses sets of m measurements on a maximally entangled state, and the measurement operators for all possible settings either commute or anticommute with one another. The measurements are specified by observables that are traceless (i.e. their trace is equal to 0) and square to the identity.
The best possible classical strategy fails f of the time, for some fraction f.

6.8.2 XOR games for quantum key distribution

We can use the setup from Exercise 6.8.1 as the basis for a quantum key distribution scheme: a process that allows two people to produce a shared random string known only to them.

For the i-th round of the game, Alice and Bob randomly (and privately) select their prompts a_i and b_i, which they then use to play one round of the game, giving answers x_i and y_i. They keep a note of all their prompts and answers, as well as the result of the winning condition for each round. After many rounds, Alice and Bob publicly announce all their prompts \{a_1,\ldots,a_n\} and \{b_1,\ldots,b_n\}.

This means that Alice, for example, now knows the following:¹³⁹

both sets of prompts \{a_1,\ldots,a_n\} and \{b_1,\ldots,b_n\}
her answers \{x_1,\ldots,x_n\}
the values of i\in\{1,\ldots,n\} for which g_A(x_i,a_i,b_i)=g_B(y_i,a_i,b_i), i.e. the numbers i_1,\ldots,i_k of the rounds that they won.

This is enough information (given that we have run enough rounds) for Alice to determine g_A and Bob to determine g_B. The two of them can then each compute the k-bit string g_A(x_{i_1},a_{i_1},b_{i_1})\ldots g_A(x_{i_k},a_{i_k},b_{i_k}) = g_B(x_{i_1},a_{i_1},b_{i_1})\ldots g_B(x_{i_k},a_{i_k},b_{i_k}) which gives their shared key. Now they just need to deal with eavesdropping.

By publicly selecting a random selection of rounds and announcing the results of their putative g_A and g_B for these rounds, they can check whether or not their values are coherent with the result of the winning conditions determined by the oracle.¹⁴⁰

If everything is coherent with the results, then they can be sure (if they have played enough rounds and compared enough results) that there was no eavesdropping.
If the fraction of tests that are coherent with the results is less than f, then they must assume that somebody has been eavesdropping, and they should cease communication.
Anywhere in between these two cases, they can quantify how much an eavesdropper might know, and then run some method of privacy amplification to further exclude the eavesdropper (at the cost of shortening the key).

6.8.3 XOR games for randomness expansion

Consider again the scenario of Exercise 6.8.1. Explain how Alice by herself can treat this as a single-player game and use it as the basis for a randomness expansion scheme.¹⁴¹

6.8.4 Prescribed binary randomness

Find a quantum circuit¹⁴² that can act as a random source that outputs 0 with probability (2+\sqrt{2})/4 and 1 with probability (2-\sqrt{2})/4.

6.8.5 Unbiasing bias

Suppose you have a source that produces random bits, but operates with a bias: it outputs 0 with probability p and 1 with probability 1-p, for some fixed 0<p<1.

Find a method such that, given two outputs from this source, you successfully obtain a single unbiased random bit (i.e. as if the source had p=1/2) with probability 2p(1-p).

6.8.6 Proving Tsirelson’s inequality

Let A_i, B_i, and \|-\| be as in Section 6.5.

Prove that (A_1\otimes(B_1-B_2)+A_2\otimes(B_1+B_2))^2 = 4(\mathbf{1}\otimes\mathbf{1}) + [A_1,A_2]\otimes[B_1,B_2].
Prove that \|[A_1,A_2]\| \leqslant 2 (and the same argument should also apply to \|[B_1,B_2]\|).

6.8.7 Detector loophole

Say we have a detector with efficiency \eta, and an otherwise perfect CHSH test with \langle S\rangle=2\sqrt{2}.

With what probability do both detections succeed? With what probability does exactly one detection fail? With what probability do both detectors fail?
Imagine that one detector successfully measures a qubit of a Bell state, while the other detector fails and notifies us of this fact. If we replace the reading of the failed detector by +1, what is the average value of the outcome?
Now imagine that both detections fail, and both readings are replaced by +1. What is the average value of the outcome?
Using the above, show that the critical detector efficiency for being able to rely on the outcome of the CHSH test is given by¹⁴³ \eta = 2(\sqrt{2}-1).

6.8.8 Locality loophole

Imagine that Alice and Bob are not very far from each other, and that they are going to perform a CHSH test using devices given to them by Eve, who has tampered with the devices and knows both of the measurement settings. How can Eve make Alice and Bob believe that they are sharing Bell pairs when, in reality, they are not?

To really get into the details of locality, we need to use some tools from special relativity: the theory of how non-accelerating observers measure times and distances. The main assertion of special relativity is that nothing can travel faster than the speed of light. These next exercises will be much easier if you have already seen things such as Minkowski diagrams before, but do not worry if you haven’t.

We are going to plot a Minkowski diagram of the CHSH test scenario. This is a plot of physical position along the horizontal axis¹⁴⁴ against time on the vertical axis. We place one event — let’s pick Alice choosing her measurement setting and getting a measurement result — at the origin. Include on this diagram all the “places” (a pair consisting of a space coordinate and a time coordinate) that can receive a message about what measurement setting Alice chose, appealing to the main assertion of special relativity. This set of places is called the future of the event.
Add to the Minkowski diagram all the places that can send a message that could influence Alice’s outcomes. This set of places is called the past of the event.
If an event (such as Bob choosing a measurement setting and getting a result) occurs in a region that is in neither the future nor the past of the event at the origin, what influence can these two events have over one another? If Bob’s event is at a distance L along the x-axis from the origin, then what is the maximal permissible time difference between the two events?¹⁴⁵
If we wish to be really careful, then we should separate out the four events:
1. Alice chooses a measurement setting
2. Alice gets a measurement result
3. Bob chooses a measurement setting
4. Bob gets a measurement result.
Draw a Minkowski diagram that includes all four events. Assuming that Alice and Bob are stationary, use this diagram to more explicitly describe the timing constraints of when each event should happen relative to one another if we wish to avoid the locality loophole.

6.8.9 Free-will loophole

Assume that Eve, the manufacturer of the devices performing the CHSH test, knows what settings Alice and Bob are going to use. Explain how Eve can have faked the outputs, making the predetermined, while still seeming to be producing results consistent with quantum violation of the CHSH inequality.¹⁴⁶
Say that Eve only knows a fraction p of the random outcomes (separately for both Alice and Bob). What is the maximum value of p that still allows \langle S\rangle=2\sqrt{2}? What about merely allowing \langle S\rangle>2? (Assume that, whenever at least one random number is known, both devices know that value, and also know that they don’t know the other value, but that one device will learn it when Alice or Bob chooses the measurement setting).
Imagine that Alice has a string of length k of (apparently) randomly chosen bits. She believes that Eve knows a fraction p of these bits. In an attempt to thwart Eve’s attempts at eavesdropping, Alice computes the addition modulo 2 of all k bits, resulting in a single bit. What is the probability that Eve can know this final value?

Bob knows the same, but instead of Alice’s answers \{x_1,\ldots,x_n\} he knows his own \{y_1,\ldots,y_n\}.↩︎
For example, if they know that they lost round i, then it should be the case that g_A(x_i,a_i,b_i)\neq g_B(y_i,a_i,b_i).↩︎
Hint: unlike in Exercise 6.8.2, Alice no longer needs to choose a random subset of rounds to check the winning condition for: she can check all of them.↩︎
Hint: what is \cos^2(\pi/4)?↩︎
Hint: if both detections succeed, then we can achieve \langle S\rangle=2\sqrt{2}; the previous questions calculate \langle S\rangle in the other possible cases; so what is the sum of these values, weighted by their probabilities of occurring?↩︎
To make things easy, we assume that space is one-dimensional: Alice and Bob live on a line.↩︎
Hint: we already said in Section 6.7 that the maximal permissible time difference should be L/c, so prove this.↩︎
Depending on how you answered Exercise 6.8.8, you might be able to use exactly the same idea here.↩︎