Introduction to quantum computing with Q# – Part 13, CHSH Game

Last time we had an in-depth look at the original Bell’s inequality, and we wrote some Q# code that allowed us to quickly empirically test the predictions of quantum mechanics in that area.

In today’s post, we will continue with a generalization of Bell’s inequalities, called Clauser-Horne-Shimony-Holt inequality (in short CHSH), and discuss a simple game based on that. In the process, we will arrive at a remarkable conclusions – we will learn that for a certain class of simple boolean logic problems, they can be solved more efficiently when adopting a quantum strategy compared to a classical “common sense” approach.

CHSH inequality

The CHSH equality was introduced in the 1969 paper Proposed Experiment to Test Local Hidden-Variable Theories. It was a generalization of the idealistic Bell’s model, which could be experimentally tested. The inequality was, given four orthogonal vector pairs $\vec{a}, \vec{a’}$ and $\vec{b}, \vec{b’}$:

$$|C(\vec{a},\vec{b}) – C(\vec{a},\vec{b’})| + |C(\vec{a’},\vec{b}) + C(\vec{a’},\vec{b})| \leq 2$$

It is outside of the scope of this post to derive the inequality, though there are plenty of excellent resources for that – including the original paper. Here we will simply take it as a quantum mechanical axiom. We already established in the previous part that the quantum mechanical mean value for the correlation between two vector is equal to the cosine of the angle between them:

$$C(\vec{a},\vec{b}) = -cos(\theta_{})$$

Given this, we can actually write the quantum mechanical prediction for the above inequality as:

$$|-cos(\theta) + cos(3\theta)| + |-cos(\theta) – cos(\theta)| \leq 2$$

If we now assume that the angle between $\vec{a}$, $\vec{a’}$, $\vec{b}$ and $\vec{b’}$ is always constant to $\theta = \frac{\pi}{4} = 45^\circ$, we get an obvious violation of the inequality:

$$2\sqrt{2}\nleq 2$$

because $cos(\frac{\pi}{4}) = \frac{1}{\sqrt{2}}$ and $cos(\frac{3\pi}{4}) = -\frac{1}{\sqrt{2}}$.

This obtained value – a violation of the inequality by a factor of $\sqrt{2}$ – is actually called a Tsirelson bound and represents the maximal violation of the CHSH inequality. It is interesting to note that it is not identical to the original Bell’s inequality which we discussed last time, and which gets violated by a factor of $1.5$. For an in-depth discussion on the differences between experimental violation results of the original Bell’s inequality as well as the Clauser-Horne-Shimony-Holt inequality, I recommend the paper Maximal violation of Bell’s inequality in the case of real experiments by Mohammad Ardehali.

CHSH Logical Game

The stunning predictions of quantum mechanics stand out when performing a simple logical game based on the CHSH inequality. The origin of the game is unclear, but it’s been suggested that it comes from the series of lecture by Tsirelson in the 1990s.

The game can be summarized as follows. Alice and Bob receive from an impartial referee a random bit each, denoted by $A$ (Alice) and $B$ (Bob). They then proceed to randomly select a bit on their own, denoted by $A’$ and $B’$ respectively. The goal of the game is for them to satisfy the following formula, without communicating with each other during the game (they can, however, agree on the strategy upfront):

$$A \cdot B = A’ \oplus B’$$

In other words Alice should select the most optimal values of $A’$, without knowing $B$, and Bob should select best possible value of $B’$, without knowing $A$. Let’s break down the classical possibilities for this. The randomly generated bits could have the following values, and thus products:

  • $A = 0$ and $B = 0$, so $A \cdot B = 0$
  • $A = 0$ and $B = 1$, so $A \cdot B = 0$
  • $A = 1$ and $B = 0$, so $A \cdot B = 0$
  • $A = 1$ and $B = 1$, so $A \cdot B = 1$

On the other hand, the XOR logic options for the bits Alice and Bob will select can be as follows:

  • $A’ = 0$ and $B’ = 0$, so $A’ \oplus B’ = 0$
  • $A’ = 0$ and $B’ = 1$, so $A’ \oplus B’ = 1$
  • $A’ = 1$ and $B’ = 0$, so $A’ \oplus B’ = 1$
  • $A’ = 1$ and $B’ = 1$, so $A’ \oplus B’ = 0$

The most optimal classical strategy for Alice and Bob is blatantly simple. Since $A \cdot B$ produces $0$ in 75% of cases, they should aim at producing $0$ out of their $A’ \oplus B’$ operation too. This means that they should always output $0$ or always $1$, regardless of the input valus of $A$ and $B$ – as long as they both stick to the same value all the time. This will ensure that $A’ \oplus B’$ always results in $0$, and since we already established that $A \cdot B$ gives $0$ in 3 out of 4 cases, they will also win the game 75% of the time. This is the best they can do classically.

Remarkably, as it turns out, due to entanglement and the EPR correlations, quantum strategy can lead to a higher winning probability, namely ~85%. Let’s now outline the quantum approach, based on the entangled pair of qubits shared by Alice and Bob. Note that as we already discussed in this series, entanglement cannot be used for communication, and thus the rules of the game are not violated. The trick of the quantum approach is for Alice and Bob to use the quantum correlations to use the EPR pair to help them select $A’$ and $B’$ bits. This is facilitated by a scheme based on different measurement bases – carefully chosen in such a way that they can tilt the winning probability to their favor.

The shared pair of qubits for Alice and Bob will be our good old friend $\ket{\Psi^-}$:

$$\ket{\Psi^-} = \frac{1}{\sqrt{2}}(\ket{01} – \ket{10})$$

The strategy for Alice will be as follows:

  • if $A = 0$ she will measure her part of the entangled pair in the computational basis (Pauli Z) basis $\{\ket{0}$,$\ket{1}\}$
  • if $A = 1$ she will measure her part of the entangled pair in the Hadamard (Pauli X) basis $\{\ket{+}$,$\ket{-}\}$
  • if Alice’s measurement produces $\ket{0}$ or $\ket{+}$, she will return $A’ = 0$
  • if Alice’s measurement produces $\ket{1}$ or $\ket{-}$, she will return $A’ = 1$

As a consequence of her measurement, Bob’s part of the entangled pair will collapse to the opposite value that Alice measured, if only he used the exact same basis. The problem is – of course – he doesn’t know which one would be better, and here is where the unusual features of quantum correlations come into play. Remember that we mentioned before in this series that superposition is basis-dependent, that is a qubit in a definite state in one basis, can be in a superposition in a different basis. Superposition doesn’t also have to be uniform, and for a single qubit, it can always be represented as a linear combination of the orthogonal basis states:

$$\ket{\Psi} = \alpha\ket{0} + \beta\ket{1}$$

As such, for example, we can make sure to arrange Bob’s measurement basis in such a way that $\alpha$ is as large as possible when Alice measured her qubit, and use that knowledge to optimally select $A’$ and $B’$.

We know from earlier parts that measuring in the X basis a qubit that has a definite state $\ket{0}$ or $\ket{1}$ (Z basis), results in getting $\ket{+}$ (classical $0$) or $\ket{-}$ (classical $1$) 50% of time each. The reason for this should be visible on the illustration above. A quantum state that we previously expressed as $\alpha\ket{0} + \beta\ket{1}$ can actually be also expressed as a linear combination using angles:

$$\ket{\Psi} = -sin(\theta)\ket{0} + cos(\theta)\ket{1}$$

For the X basis, we know that it is shifted against the Z basis by

$$\theta = \frac{\pi}{4} = 45^\circ$$

which leads us to

$$\ket{\Psi} = -\frac{\sqrt{2}}{2}\ket{0} + \frac{\sqrt{2}}{2}\ket{1}$$

and based on the Born rule, the probabilities of getting $\ket{0}$ is $|\alpha|^2 = \frac{1}{2}$ and $\ket{1}$ is $|\beta|^2 = \frac{1}{2}$ – exactly according to the expectation we had.

With this in mind, the most optimal value for Bob in the CHSH game is to use the Z basis rotated by $\theta = \frac{\pi}{8} = 22.5^\circ$ clockwise and anti clockwise.

Let’s unpack this. The strategy would then be:

  • if $B = 0$ Bob will measure his part of the entangled pair in the computational basis (Pauli Z) basis $\{\ket{0}$,$\ket{1}\}$ rotated by $-\frac{\pi}{8}$
  • if $B = 1$ Bob will measure his part of the entangled pair in the computational basis (Pauli Z) basis $\{\ket{0}$,$\ket{1}\}$ rotated by $\frac{\pi}{8}$
  • if Bob’s measurement produces $\ket{0}$ he will return $B’ = 1$
  • if Bob’s measurement produces $\ket{1}$ he will return $B’ = 0$

A word of explanation is in order here. The reason why Bob doesn’t produce $B’ = 0$ when measuring $\ket{0}$ (and similar symmetry for the other case) is because the two qubits or correlated negatively (remember we started with $\ket{\Psi^-}$). In many textbook examples the initial Bell state used to illustrate CHSH inequality is $\ket{\Phi^+}$, where the orthogonal qubit states and classical bit values align perfectly between both parties. However, such state is a lot more difficult to produce experimentally so we used $\ket{\Psi^-}$ instead.

Now, the reason why such quantum strategy works, is because the win probability is always calculated as $cos^2(\frac{\pi}{8})$ which is ~85%. Why is that? Let’s look at one of the possible cases (the others are similar).

Imagine that Alice receives $A = 0$, measures $\ket{0}$ and therefore after measurement outputs $A’ = 0$. This collapses Bob’s qubit to $\ket{1}$, since they are – in an opposite way – correlated. In order for them to win the game, Bob needs to output $B’ = 0$ too. We have two possibilities from here. Either Bob receives $B = 0$, measures in the Z basis rotated by $-\frac{\pi}{8}$ where he will get $\ket{1}$ with 85% probability $cos^2(\frac{\pi}{8})$, thus producing $B’ = 0$. Alternatively, Bob gets $B = 1$, which means he measures in the Z basis rotated by $\frac{\pi}{8}$, where he again obtains $\ket{1}$ with 85% probability $cos^2(\frac{\pi}{8})$ producing $B’ = 0$. In either case, the win probability is tied to $cos^2(\frac{\pi}{8})$ and we could easily calculate it for all the other permutations.

The CHSH game discussed here is just one example of the wider category of the so-called “non-local” games – where quantum mechanics, due to its nonlocal correlations can produce winning strategies higher than classical approach. An excellent overview of other such games can be found in the Consequences and Limits of Nonlocal Strategies paper by Cleve, Hoyer, Toner and Watrous. The paper also discusses the Tsirelson bound, which, as mentioned, places bounds on the correlation between quantum mechanical objects and which provides a limit by which entangled particles can violate the Bell inequalities.

Q# implementation

Let’s now verify our theoretical discourse with the CHSH implementation written in Q#. If our reasoning is correct, we should indeed see a classical strategy providing ~75% winning rate, with the quantum strategy outperforming it with its ~85% success rate.

We will structure the code in a similar fashion to our code sample from part 12, that is, we will use a self-contained Q# program. It makes sense to run the sample a larger number of times, to see how the results develop over many runs and see them converge towards 85% (after all, quantum mechanics is probabilistic); in this case, 4096 seems like an appropriate samples size.

The entry point to our application is shown below.

For each iteration in the 4096 samples, we will draw two random referee bits $A$ and $B$ for Alice and Bob and then execute the classical strategy and a quantum strategy. The result of each strategies is then compared to the drawn bits using the aforementioned $A \cdot B = A’ \oplus B’$ formula. QDK actually comes with a built-in function $Xor(a : Bool, b : Bool)$ in the $Microsoft.Quantum.Logical$ namespace that comes in very handy here. As the strategies get executed, we keep running totals in two mutable integer variables. At the end of the entry point operation, we simply calculate the win percentages for each strategy and print them out to the console.

This should all be clear up to this point – the next step is to provide the implementations for both classical and quantum CHSH game strategies. Classical strategy is very simple – as we mentioned earlier, returning $A’ = 1$ and $B’ = 1$ or $A’ = 0$ and $B’ = 0$ gives 75% success rate. In our example, we choose the former approach.

Finally, we should have a look at the implementation of the quantum strategy, which is shown next.

The operation $RunQuantumStrategy$ allocates two qubits, initializes the Bell state $\ket{\Psi^-}$ and returns booleans representing the result of Alice’s and Bob’s measurements. Notice that because of the negative correlation between the two qubits in the Bell state, we will negate Bob’s result; this is in line with our earlier discussion on the subject. The preparation of the entangled Bell pair is the same as in the previous post:

Before we dive into the really interesting part of the Q# implementation, and those would be the steps which Alice and Bob need to go through, a word about the order of measurement. In our initial code, we arranged things in a way that Alice always performs her measurement before Bob. While there is nothing particularly wrong about that, one might object that this may be somehow unfair, as in reality in the CHSH game the participants should be spatially separated and would not communicate with each other – so their procedures of returning the classical bits $A’$ and $B’$ may also not be sequential (first Alice, then Bob). To address that, we can easily include a randomization factor, that will force e.g. Alice to return her bit first 60% of time, and Bob to return his first the remaining 40% of time. The updated code that incorporates that idea is shown next.

Let’s now discuss the implementation of Alice’s quantum strategy – the simpler one of the two.

As we mentioned, Alice will measure in the Z basis when her bit $A = 0$, and in the X basis when $A = 1$. Since the X basis is the Z basis rotated around the Y axis by $-\frac{\pi}{4}$, we can write her strategy as measurement along the Z axis, and a conditional rotation with $Ry(theta : Double, qubit : Qubit)$ Q# operation. Due to the fact the our orthogonal vectors are $90^\circ$ apart, but on the Bloch sphere they’d be $180^\circ$ apart, we need to multiply the angle we deduced from looking at the vectors’ geometry by a factor of 2. This is the reason we rotate not by $-PI() / 4.0$ but by $(-2.0 * PI() / 4.0)$.

Turns out, in Q# this code is unnecessarily complicated, because, as we already learnt in earlier parts of this series, QDK has built-in operations for Pauli Z, Pauli X and Pauli Y measurements. Therefore, our code can be simplified to:

Finally, let’s explore Bob’s strategy in Q#. It is shown in the snippet below.

Since we initially approached Alice’s strategy with the usage of $Ry$ rotation, and only then switched to the built-in feature of measuring in Pauli X basis, Bob’s implementation should be easy to follow. That is, of course, due to the fact that all that Bob needs to do is to determine the rotation angle: $\frac{\pi}{8}$ or $-\frac{\pi}{8}$, depending on the value of $B$.

This is everything we needed for our code sample. At this point we can execute the program and, hopefully, marvel at the amazing features of quantum computing. The output of this sample application should be similar to the following:

This is exactly what we expected based on the theoretical understanding of the problem. Indeed – by just using the entangled qubit pair among them, without any classical communication, the CHSH game receives a 10% boost over the best logical classical winning scenario. Something quite remarkable. Imre and Balazs ended their discussion about CHSH and Bell’s inequalities with a quote that also seems to be a perfect way for us to finish with:

(…) we assumed that logic is an appropriate tool for reasoning. Unfortunately Gödel proved that any logic system (except if we strongly limited it) will contain statements which are neither false nor true but simply unprovable.

Summary

We already established earlier in this series that entanglement can be viewed as a resource, and the CHSH game is yet another example of using entanglement to achieve something that is not possible classically. Nielsen and Chuang had a similar observation in their monumental book:

The bigger picture is that Bell’s inequality teaches us that entanglement is a fundamentally new resource in the world that goes essentially beyond classical resources; iron to the classical world’s bronze age. A major task of quantum computation and quantum information is to exploit this new resource to do information processing tasks impossible or much more difficult with classical resources.

We will continue our quantum computing adventures in part 14 very soon!