Beyond Classical Limits: The Magic of the CHSH Game

Most of us have a lot of experiences while playing games: happiness, sadness, fear, confusion, anger, and more. I remember playing one of my favorite games, "Resident Evil 4" on PlayStation 4. It was filled with jump scares, confusion, and tension in a zombie-infested world—experiences I’d never have in real life.

For me, games are like a doorway to another world, allowing us to escape reality and immerse ourselves in a universe full of different experiences. Beyond the fun, games can also teach us valuable lessons, help us build intuition in simulated environments, and even make education enjoyable through engaging gameplay.

While many games aim to entertain and educate, they also challenge us to develop strategies and improve our skills to achieve a high win rate. However, there's one game that stands out for its intriguing challenge. In this blog post, I want to introduce you to a very interesting game. Unlike typical games, no matter what strategies or methods we try, we can never find a way to achieve a 100% win rate in this game.

The CHSH Game

Imagine that there are two players: Alice and Bob. And the game is having three stages:

• Pre-Game: In this stage, the players are allowed to coordinate by creating a plan or strategy to win the game.
• Input: In this stage, the players will have to read an input $X$ for Alice and $Y$ for Bob.
• Ouput: This is the moment of truth that will determine whether Alice and Bob could win the game or not. In this stage, Alice and Bob have to give an output $A$ and $B$ respectively.

These are the complete rules of the CHSH Game:

1. The inputs and outputs are all bits: $X,Y,A,B \in \{0,1\}$
2. The inputs $X$ and $Y$ will be choosen randomly with probability of $\frac{1}{4}$ for each of the four possibilities $(0,0), (0,1), (1,0), (1,1)$.
3. Alice and Bob win when they if only if satisfy this condition: $X . Y = A \otimes B$, otherwise, they lose. $(.)$ is AND condition and $\otimes$ is XOR (Exclusive OR).

So, to win the game, when the inputs is $(1,1)$ Alice and Bob should return different ouputs: $(1,0), (0,1)$ otherwise they should return exactly the same outputs: $(0,0), (1,1)$. Okay, now, I assume that you already understand the rule of the game clearly. Do you have strategy in mind?

Deterministic Strategy

Let's take a look at the table in the preceeding section, there are obvious pattern in the win column that we could use to win the game: The first three rows in win column is giving us a hint that: If Alice and Bob just always giving the same output no matter what's the input, they could have been winning 3 of four possibilities. Which means they could use this strategy to get 3/4 win rate or 75% win rate. They could just throw constant output whether it's a constant 0 or constant 1 as long as they are same ($A = B$).

But really? that's it? $75$? that doesn't seem to be enough. If you isn't satisfied enough with this strategy, you could just try to find another deterministic strategies and trust me, 75% is your limit.

Probabilistic Strategy

Nope.

Every probabilistic strategy can alternatively be viewed as a random selection of a deterministic strategy, just like (as was mentioned in the first lesson) probabilistic operations can be viewed as random selections of deterministic operations. -- IBM Quantum Learning

So, yeah! It sucks! It means that our winning probabilty couldn't get any better with this strategy either.

Quantum Strategy

Okay, let's try the ultimate way to beat the game, to increase our winning probability. Of course, we will use the power of Quantum Computing. We could leverage the concept of entanglement in Quantum Computing in order to increase our winning probability in this game.

Personally, I found this concept is quite hard to understand at first, because the mathematical concept used by this strategy is involving some Trig stuffs and it's quite hard to understand it intuitively if we are not getting used of the Trigonometry concept for quite a while.

I will try to write the simplest and easiest way because I know, some sources out there will leave some part of the math without any explanation that could totally frustating. 😮‍💨 Let's start from the very simple concept first.

Trigonometry

Calm, it's not a complex Trigonometry shit, it's only requires us to understand the basic of Trigonometry. I'm using this this tool to help me understand what happens visually, so just open the tool in new tab just in case you need a help just like me.

Rotation Matrix

I will start the explanation of the strategy by introducing this very beautiful operation matrix:

If you are a software engineer, you could just interpret it as just a simple function named $U$ that receive single parameter $\theta$, and the output of the function is an operation that rotate two dimensional vectors by an angle of $-\theta$ from the origin.

The Strategy

Clean Version

The strategy is quite simple as you can see described in the quantum circuit above. First, Alice and Bob shared a pair of entangled qubits, and then, they will perform one or two operations based on the inputs they received. As I explained in the preceding section about the $U_\theta$ function, we could just think that Alice and Bob will rotate their qubits (vectors) based on received inputs.

For Alice:

While Bob:

By using this "seems to be simple" strategy, we could increase our win rate into ~85%. It's definitely better than the classical strategy that could only give us 75% win rate.

Without knowing the dirty version of the strategy, we could understand this strategy in high level overview. But I bet that it doesn't make you uncomfortable, me either. As an engineer, I have this very uncomfortable feeling that force me to deep dive more to understand what happens under the hood.

It's okay, in the the following sections, we will deep dive into the dirtiest stuff that we need to understand to put this understanding into our head. Let's go!

Dirty Version

Before we see the dirty version of our $U_\theta$ operation, first we need to define a state vector:

It's just a vector written in Bra-Ket notation that receive $\theta$ as parameter, similar to our previous $U_\theta$. As I said before, to help you understand it intuitively, you could use this tool and play around with it. By feeding some parameters, we could get common quantum state vectors:

The $\theta$ parameter is just an angle measured in radians. If you forgot about it, a unit circle is having radians of $2\pi$. To make it clear, you can use this .gif from Wikipedia to help you understand it intuitively:

And we need to understand this simple formula:

This formula reveals the geometric interpretation of the inner product between real unit vectors, as the cosine of the angle between them. -- IBM Quantum Learning

And finally, this is the dirty version of $U_\theta$ as follows:

Study Case

As we know that initially Alice and Bob is sharing two entangled qubits that we could describe it as one of the Bell state:

In this section, we will take one of the study case from all possible inputs of the CHSH game as an example to help you understand how it works from mathematical point of view.

Case 1: $(X,Y) = (0,0)$. Alice performs $U_0$ on her qubit and Bob performs $U_{\pi/8}$ on his qubit. Their combined operation could be expressed as the tensor product of those operations $(U_0 \otimes U_{\pi/8})$. And the application of those operations to current state is:

The probabilities for the four possible answer pairs $(A, B)$:

To calculate the probabilities that $A = B$ and $A \neq B$ we could just aggregate (get the sum for both cases):

So in this case, when (X,Y) = (0,0), Alice and Bob win if $A = B$ with probability:

You can try for the other case with the same steps as we did in this Case 1 and you'll get the same result of winning probability. Awesome right? 😎

Detailed Matrix Calculation

If you are interested in more detailed calculation, I will give you the detailed step-by-step calculation in matrix representation of the first case that I explained in the previous section.

As you can see that in the case when the input is $(X,Y) = (0,0)$, Alice and Bob will apply the operation $(U_0 \otimes U_{\pi/8})$ respectively. More detailed step about the construction of Alice's operation matrix:

$U_0 = \ket{0}\bra{\psi_0} + \ket{1}\bra{\psi_{0 + \pi/2}} \\ = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \left(\begin{pmatrix} cos(0) & 0 \end{pmatrix} + \begin{pmatrix} 0 & sin(0) \end{pmatrix}\right) + \begin{pmatrix} 0 \\ 1 \end{pmatrix} \left(\begin{pmatrix} cos(\pi/2) & 0 \end{pmatrix} + \begin{pmatrix} 0 & sin(\pi/2) \end{pmatrix}\right) \\ = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} cos(0) & sin(0) \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} cos(\pi/2) & sin(\pi/2) \end{pmatrix} \\ = \begin{pmatrix} cos(0) & sin(0) \\ cos(\pi/2) & sin(\pi/2) \end{pmatrix} \\ = \begin{pmatrix} cos(0) & sin(0) \\ -sin(0) & cos(0) \end{pmatrix} \\ = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

It's equals to the identity matrix which will not do any kind of transformation to the state vector. While Bob's operation matrix is:

$U_{\pi/8} = \begin{pmatrix} cos(\pi/8) & sin(\pi/8) \\ -sin(\pi/8) & cos(\pi/8) \end{pmatrix} \\ = \begin{pmatrix} \frac{\sqrt{2 + \sqrt{2}}}{2} & \frac{\sqrt{2 - \sqrt{2}}}{2} \\ \frac{\sqrt{2 - \sqrt{2}}}{2} & \frac{\sqrt{2 + \sqrt{2}}}{2} \end{pmatrix}$

So, the value of the tensor product between their operation matrix is:

$(U_0 \otimes U_{\pi/8}) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes \begin{pmatrix} \frac{\sqrt{2 + \sqrt{2}}}{2} & \frac{\sqrt{2 - \sqrt{2}}}{2} \\ \frac{\sqrt{2 - \sqrt{2}}}{2} & \frac{\sqrt{2 + \sqrt{2}}}{2} \end{pmatrix} \\ = \begin{pmatrix} \frac{\sqrt{2 + \sqrt{2}}}{2} & \frac{\sqrt{2 - \sqrt{2}}}{2} & 0 & 0 \\ \frac{\sqrt{2 - \sqrt{2}}}{2} & \frac{\sqrt{2 + \sqrt{2}}}{2} & 0 & 0 \\ 0 & 0 & \frac{\sqrt{2 + \sqrt{2}}}{2} & \frac{\sqrt{2 - \sqrt{2}}}{2} \\ 0 & 0 & \frac{\sqrt{2 - \sqrt{2}}}{2} & \frac{\sqrt{2 + \sqrt{2}}}{2} \end{pmatrix}$

So applying this tensor product of the operations to Alice and Bob entangled qubits would give us this result:

$(U_0 \otimes U_{\pi/8})\ket{\phi^+} = \begin{pmatrix} \frac{\sqrt{2 + \sqrt{2}}}{2} & \frac{\sqrt{2 - \sqrt{2}}}{2} & 0 & 0 \\ \frac{\sqrt{2 - \sqrt{2}}}{2} & \frac{\sqrt{2 + \sqrt{2}}}{2} & 0 & 0 \\ 0 & 0 & \frac{\sqrt{2 + \sqrt{2}}}{2} & \frac{\sqrt{2 - \sqrt{2}}}{2} \\ 0 & 0 & \frac{\sqrt{2 - \sqrt{2}}}{2} & \frac{\sqrt{2 + \sqrt{2}}}{2} \end{pmatrix} \cdot \frac{1}{\sqrt{2}}\begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} \\ = \frac{1}{\sqrt{2}} \begin{pmatrix} (\frac{\sqrt{2 + \sqrt{2}}}{2} \cdot 1) + (\frac{\sqrt{2 - \sqrt{2}}}{2} \cdot 0) + (0 \cdot 0) + (0 \cdot 1) \\ (\frac{\sqrt{2 - \sqrt{2}}}{2} \cdot 1) + (\frac{\sqrt{2 + \sqrt{2}}}{2} \cdot 0) + (0 \cdot 0) + (0 \cdot 1) \\ (0 \cdot 1) + (0 \cdot 0) + (\frac{\sqrt{2 + \sqrt{2}}}{2} \cdot 0) + (\frac{\sqrt{2 - \sqrt{2}}}{2} \cdot 1) \\ (0 \cdot 1) + (0 \cdot 0) + (\frac{\sqrt{2 - \sqrt{2}}}{2} \cdot 0) + (\frac{\sqrt{2 + \sqrt{2}}}{2} \cdot 1) \\ \end{pmatrix} \\ = \frac{1}{\sqrt{2}} \begin{pmatrix} \frac{\sqrt{2 + \sqrt{2}}}{2} \\ \frac{\sqrt{2 - \sqrt{2}}}{2} \\ \frac{\sqrt{2 - \sqrt{2}}}{2} \\ \frac{\sqrt{2 + \sqrt{2}}}{2} \end{pmatrix} = \begin{pmatrix} \frac{\sqrt{2 + \sqrt{2}}}{2 \sqrt{2}} \\ \frac{\sqrt{2 - \sqrt{2}}}{2 \sqrt{2}} \\ \frac{\sqrt{2 - \sqrt{2}}}{2 \sqrt{2}} \\ \frac{\sqrt{2 + \sqrt{2}}}{2 \sqrt{2}} \end{pmatrix}$

And to get the probability, we need just need to get the value of absolute square for each probability magnitudes, so we get:

As you can see that the result is the same compared to our previous calculation using Bra-Ket notation. Now, you've got the matrix calculation in detail, but to make it more intuitive, I would suggest you to follow me further to see the Geometric representation of this.

Geometric Representation

In this section, we will see what actually happens in Case 1: $(X,Y) = (0,1)$ geometrically. This is useful to sharpen our intuitive understanding to this problem.

First, let's remember a vector that we've defined in previous section:

As we know that dependending on the input, Alice will define an orthonormal basis of vectors (remember the matrix $U_\theta$). For the case when $X = 0$, we can visualize it as follows:

While Bob, for the case when $Y = 0$, we can visualize it as follows:

Combining both, we get something like this in our visualization:

The color of the vectors represent the answers of Alice and Bob: green for 0, and blue for 1. As you can see that the "distance" in radians for both blue and green vectors between Alice and Bob is same $\pi/8$.

By this, we could get the probability that Alice and Bob will answer the same output is:

while the probability that Alice and Bob will answer different output is:

By understanding "The Magic of the CHSH Game" it opens up our eyes to see another proof that Quantum Computing could definitely beats Classical Computing.

And FYI, in context of Quantum Physics, The CHSH game is also known as a pivotal concept in quantum mechanics that offers a clear and accessible way to demonstrate the limitations of hidden variable theories and the profound implications of quantum entanglement.

Thanks for reading this article! If you are interested to discuss this topic with me, just drop your comment below! 🍻