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_{ab})$$

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}}$.

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 🔗

Using principles of the CHSH inequality one can play a spectacular logical game. The game can be summarized as follows. The game envisions two players receiving random bits $A$ and $B$ (for Alice and Bob). They then need to return - independent of each other - new bits $A’$ and $B’$, such that the following formula evaluates to true:

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

Analyzing the possible combination leads us to conclude that the best classical strategy can never exceed 75% win rate. Zero is produced in the multiplication test 3 out of 4 times, so if Alice and Bob return $A’$ and $B’$ values that are both $0$ or both $1$ they would match that.

This is all very logical and there is just no way they can reliably exceed this win rate.

It turns out that thanks to the weirdness of quantum mechanics, and by relying on entanglement between a pair of qubits, Alice and Bob can actually win the game more often than 3 out of 4 times!

Let us now discuss how the quantum strategy would work. The shared pair of qubits for Alice and Bob will be our good old friend $\ket{\Psi^+}$. The strategy for Alice will then 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$

On the other hand, the strategy for Bob will 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.

What is the reason for such strategy choices? As soon as Alice measures her qubit, Bob’s qubit would collapse to the opposite value if they both measure in the same basis. However, if Bob measures in a different basis, his measurement outcomes will be probabilistic. In the most extreme variant, if he measures in a basis that is creating maximal uncertainty with respect to the basis Alice chose, he would receive completely random results - a classical 0 in 50% of cases, and a classical 1 in the other 50%.

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. But where does the strange basis choice for Bob come from?

The reason why this would work, is 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 in a two dimensional plane:, which depending on the rotation angle can take the form of

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

or

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

In either case, the win probability, based on the Born rule, is always calculated as $cos^2(\frac{\pi}{8})$ which is ~85%.

Q# implementation 🔗

Let’s now proceed to writing the CHSH game code in Q#. 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.

@EntryPoint()
operation Main() : Unit {
    let runs = 1000;
    mutable classicalWins = 0;
    mutable quantumWins = 0;
    for (i in 0..runs) {
        let aliceRefereeBit = DrawRandomBool(0.5);
        let bobRefereeBit = DrawRandomBool(0.5);

        let classicalChosenBits = RunClassicalStrategy(aliceRefereeBit, bobRefereeBit);
        if ((aliceRefereeBit and bobRefereeBit) == Xor(classicalChosenBits))
        {
            set classicalWins += 1;
        }

        let quantumChosenBits = RunQuantumStrategy(aliceRefereeBit, bobRefereeBit);
        if ((aliceRefereeBit and bobRefereeBit) == Xor(quantumChosenBits))
        {
            set quantumWins += 1;
        }
    }

    let classicalWinRate = IntAsDouble(classicalWins) / IntAsDouble(runs);
    let quantumWinRate = IntAsDouble(quantumWins) / IntAsDouble(runs);
    Message($"Classical win probability: {DoubleAsString(classicalWinRate * 100.0)}");
    Message($"Quantum win probability: {DoubleAsString(quantumWinRate * 100.0)}");
}

For each iteration in the 1000 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.

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 we can hardcode its output as a pair of $true$ or a pair of $false$ bits.

function RunClassicalStrategy(aliceBit : Bool, bobBit : Bool) : (Bool, Bool) {
    // return (1,1) irrespective of input bits
    return (true, true);
}

The quantum strategy implementation is as follows:

operation RunQuantumStrategy(aliceBit : Bool, bobBit : Bool) : (Bool, Bool) {
    using ((aliceQubit, bobQubit) = (Qubit(), Qubit())) {
        InitBellState(aliceQubit, bobQubit);
        return (AliceMeasurement(aliceBit, aliceQubit), not BobMeasurement(bobBit, bobQubit));
    }
}

The operation $RunQuantumStrategy$ creates the Bell state $\ket{\Psi^-}$ and returns booleans representing the result of Alice’s and Bob’s measurements. The preparation of the entangled Bell pair is the same as in the previous post:

operation InitBellState(q1 : Qubit, q2: Qubit) : Unit is Adj {
    X(q1);
    X(q2);
    H(q1);
    CNOT(q1, q2);
}

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.

operation RunQuantumStrategy(aliceBit : Bool, bobBit : Bool) : (Bool, Bool) {
    using ((aliceQubit, bobQubit) = (Qubit(), Qubit())) {
        InitBellState(aliceQubit, bobQubit);

        let shouldAliceMeasureFirst = DrawRandomBool(0.6);
        if (shouldAliceMeasureFirst) {
            return (AliceMeasurement(aliceBit, aliceQubit), not BobMeasurement(bobBit, bobQubit));
        } 
        else 
        {
            let bobResult = not BobMeasurement(bobBit, bobQubit);
            let aliceResult = AliceMeasurement(aliceBit, aliceQubit);
            return (aliceResult, bobResult);
        }
    }
}

Let’s now discuss the implementation of Alice’s quantum strategy.

operation AliceMeasurement(bit : Bool, q : Qubit) : Bool {
    let rotationAngle = bit ? (-2.0 * PI() / 4.0) | 0.0;
    Ry(rotationAngle, q);
    return MResetZ(q) == One;
}

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.

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:

operation AliceMeasurement(bit : Bool, q : Qubit) : Bool {
    let result = Measure([bit ? PauliX | PauliZ], [q]) == One;
    Reset(q);
    return result;
}

Bob’s strategy implementation is shown in the snippet below.

operation BobMeasurement(bit : Bool, q : Qubit) : Bool {
    // if bit = 0, measure in computational basis rotated by -π/8
    // if bit = 1, measure in computational basis rotated by π/8
    // this ensures win probability equal to cos²(π/8)
    let rotationAngle = bit ? (2.0 * PI() / 8.0) | (-2.0 * PI() / 8.0);
    Ry(rotationAngle, q);
    return MResetZ(q) == One;  
}

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$.

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:

Classical win probability: 75.1708984375
Quantum win probability: 85.546875

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!