## 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 andb (respectively), with1\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 andy (respectively), of lengthm 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 is1 , and lose if it is0 . 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} whereg_A andg_B are deterministic one-bit-valued functions whose output values are equally likely to be0 or1 (i.e. they return the value0 for exactly half of the possible input triples).There exists a

*quantum*strategy that always wins. It uses sets ofm measurements on a maximally entangled state, and the measurement operators for all possible settings either commute or anti-commute with one another. The measurements are specified by observables that are traceless (i.e. their trace is equal to0 ) and square to the identity.The best possible classical strategy fails

f of the time, for some fractionf .

### 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

This means that Alice, for example, now knows the following:^{137}

- 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 whichg_A(x_i,a_i,b_i)=g_B(y_i,a_i,b_i) , i.e. the numbersi_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

By publicly selecting a random selection of rounds and announcing the results of their putative ^{138}

- 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.^{139}

### 6.8.4 Prescribed binary randomness

Find a quantum circuit^{140} that can act as a random source that outputs

### 6.8.5 Unbiasing bias

Suppose you have a source that produces random bits, but operates with a bias: it outputs

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

### 6.8.6 Proving Tsirelson’s inequality

Let

- 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

- 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
^{141}\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^{142}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 thex -axis from the origin, then what is the maximal permissible time difference between the two events?^{143}If we wish to be really careful, then we should separate out the four events:

- Alice chooses a measurement setting
- Alice gets a measurement result
- Bob chooses a measurement setting
- 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.

^{144}Say that Eve only knows a fraction

p of the random outcomes (separately for both Alice and Bob). What is the maximum value ofp 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 fractionp of these bits. In an attempt to thwart Eve’s attempts at eavesdropping, Alice computes the addition modulo 2 of allk 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 thatg_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.↩︎