Build a Quantum Computing Simulator from Scratch — Part 1

An AI generated image of a quantum computer chip, powered by DALL-E and Bing Copilot

Introduction

Quantum Computers are on the horizon! Believe it or not, there’s currently a lot of hype and excitement about quantum computing and how in a few years it will be used alongside classical computers to solve useful problems. Many big vendors already have multi-generation quantum computers available in their cloud to run programs on. These programs currently do not solve a lot of big challenges, but the expectation is that as the technology catches on soon, we will run bigger programs on these machines and eventually scary programs like Shor’s algorithm to crack classical encryption!

But that’s in a far future, what can we do today? We can run useful programs on quantum simulators that simulate a quantum computer on a classical computer. In this series of articles, I will be building a toy quantum simulator from scratch to show that it's really not that difficult to build one.

What are we going to build?

There are great quantum simulators from almost every vendor who builds real quantum computers today, the most popular among those (IMHO) being Qiskit. These libraries have support for all sorts of quantum gates and circuits, and they are developed by many developers — both paid and open source. This is not that! This is a very small subset of quantum gates and mechanisms to build circuits using those. In fact, it's so small that it is just one file when we are done!

So then why does it exist?

1. Building something from scratch gives you a lot of knowledge of how the internals actually work. There are a lot of theories in QC that are expressed in mathematical operations. These operations are simulated into the actual quantum circuit on a real hardware, but while writing the code and thinking about those conceptually, it is all a series of mathematical steps. Looking at a code in Qiskit can give you some idea about how it looks externally, but not a lot about how it works internally.
2. Libraries like Qiskit are heavyweight and they require a lot of dependencies to run. I failed many times trying to install Qiskit on a raspberry Pi. A smaller simulator can be made to work on any computer with speed and memory constraints.
3. You have the freedom to make it look like however you want. For example, Qiskit uses a combination of classes and functions for different parts of the library. However, we can pretty much implement the main core of the system by a bunch of functions and function compositions. This, I can’t do in a prebuilt library, but I can do it in my own code.
4. Finally, it's just a lot of fun, so why not!

Convinced? Dive in then!

The language of the system

We will use something different, not Python please! :-D

I really love Python, but I think if we want to build it from scratch it would be nice to use something different, so we don’t get biased by an existing implementation. Being a lifelong Lisp lover, I decided to use a Lisp instead. The mainstream dialects we could use are Common Lisp (the Lisp), Clojure and Racket. Since we would be using a bit of linear algebra and only Racket comes with a “battery included” for Matrices, I went with Racket.

Racket

Racket is a nice ecosystem of languages and libraries with some excellent documentation. It can be downloaded and installed quickly. It comes with Dr. Racket IDE which is more than good enough.

Racket is a dialect of scheme. Its syntax has evolved over the years and there are some differences now between Scheme and Racket. We will be using the Racket dialect but if we have the right libraries, it can be easily converted to Scheme or any other Lisp.

Alright, now let's jump right into it!

Part 1 — From Bits to Qubits

Our computers work with bits. Bits are used for storing binary data. All our software work with binary data and we have been optimizing our computers to work more on binary data and with more speed. We will see that in the quantum domain, we still have the concept of binary data but not exactly as it is in the "classical" domain. So, let's start with our familiar good old classical bit.

Representing classical bits

How do we represent a classical bit? It is easy — either write 0 or 1. That's because a bit can either be in state 0 or 1. In hardware, this could be that a 5 volt charge can represent 1 and 0 volt can represent 0. Current hardware and SSD disks are much more advanced, but the basic concept is the same. What about two bits? Two bits can be in various different combinations of states because if one is 0 the other can be either 0 or 1 and vice versa. So, the possible states are: 00, 01, 10, 11. Mathematically, if we have n bits, there can be 2^n combinations in total.

This is good, but we can represent the same thing in a little different manner, which will be very useful when we go to qubits. This representation does not list out all the combinations individually but rather shows which value among all combinations should be turned on.

Let's look at it in action. For n = 2, we know that we will have 2^2 = 4 combinations. This means if I create a list of 4 elements, I can map an element in the list to one of the combinations. A list like [a, b, c, d] can be used to map like this: a => 00, b => 01, c => 10, d => 11. Note, the order is important and needs to be exactly this. In fact, this is the natural order of the numbers in their decimal form — 0, 1, 2, 3.

But since, at any moment, only one of these 4 combinations can be present, it means out of a, b, c and d only one value can be on at a time and others will be off. So then simplifying the mapping a bit, we say, [1, 0, 0, 0] means 00 since a is on and rest are off. Similarly, [0, 1, 0, 0] means 01; [0, 0, 1, 0] means 10; [0, 0, 0, 1] means 11.

So, that was 2 bits. How about the original single bit? To represent that we now have two lists: bit 0 is [1, 0] and bit 1 is [0, 1].

Nice, but remember math? In math instead of lists we call these vectors. The lists that we created above for representing bit combinations are represented as column vectors in Linear Algebra. What's a column vector? It is just the same list but written top to bottom.

Again, bit 0 is

[1
 0]

And bit 1 is

[0
 1]

Bit 01 is

[0
 1
 0
 0]

Bit 11 is

[0
 0
 0
 1]

And so on.

Code for classical bits

Let's begin by writing some code to find all combinations of bits given a bit length.

(define (bits-of-len n)
  (cond
    ((< n 1) (error "Invalid bits length, must be >= 1"))
    ((= n 1) '((0) (1)))
    (else (let ([lower-bits (bits-of-len (- n 1))])
            (for*/list ([i (range 2)]
                        [x lower-bits])
              (cons i x))))))

Running it (bits-of-len 2) will give the following output:

'((0 0) (0 1) (1 0) (1 1))

This is pretty much the same combination as before, but in a list of lists — there’s a reason we chose Lisp!

How do we represent the column vector? We use col-matrix that comes with Racket. We can represent 00 like (col-matrix [1 0 0 0]). Which produces this output:

(array #[#[1] #[0] #[0] #[0]])

Internally it is an array of arrays — where each row is represented by an inner array.

Qubits — welcome to the world of probabilities

In the classical world, everything is deterministic. If I have a bit b I know that I will always get either bit 0 which is

[1
 0]

or bit 1 which is

[0
 1]

A qubit, or quantum bit, is almost same as above. The two states of a single qubit are represented as |0> and |1>, and in column vector form, again they are same:

Qubit |0> is

[1
 0]

And qubit |1> is

[0
 1]

So, what’s so special? Well, here’s what:

A qubit can be either in |0> state or |1> state, or any state in between. This is called superposition state of the qubit.

A qubit is generally represented as:

[a
 b]

Where, the probability formula for a and b is |a|^2 + |b|^2 = 1 — this is known as Born’s rule. Here a and b are complex numbers and are known as probability amplitudes, not probabilities. And the weird thing is, until we measure the qubit, it can be in a superposition state; but as soon as we measure the qubit, it collapses into one of |0> or |1> states! (Insert your favorite quote from Richard Feynman about quantum weirdness here)

We can see from the general column vector of a qubit, if b = 0 then we get |0> , and if a = 0 we get |1>. This is what differentiates a classical bit's column vector from a qubit's column vector. In classical bits, the column vector can never have anything other than 1 in the rows. And that too only one of the rows can be 1 at a time. For qubits, it can be any complex numbers at any row of the column vector, as long as they are all squared and summed to make 1.

However, properties like superposition and entanglement (which we will see later) give Quantum Computing the edge over classical computing.

Code to build a qubit

Now we write a helper method to build a qubit from two values a and b.

(define (qubit a b)
  (if (e-equal? (+ (* (magnitude a)
                      (magnitude a))
                   (* (magnitude b)
                      (magnitude b)))
                1.0)
      (col-matrix [a b])
      (error "Cannot create qubit, bad probabilities")))

The magnitude function determines the correct absolute value (or norm) of a complex number. The e-equal? is a predicate that determines if the value is sufficiently close to 1.0. It is defined as:

(define (e-equal? x y)
  (< (abs (- x y)) 0.00001))

Let's run it a few times.

(qubit 1 0) ==> (array #[#[1] #[0]])
(qubit 0 1) ==> (array #[#[0] #[1]])
(qubit 2 3) ==> Cannot create qubit, bad probabilities
(qubit (/ 1 (sqrt 2))
       (/ 1 (sqrt 2))) ==> (array #[#[0.7071067811865475] #[0.7071067811865475]])

That last qubit is really special — it has an equal chance of being a |0> or |1>.

Why equal chance? Here, a = 1 / square_root(2) and so is b. So, if we square them, we get probabilities 1/2 each. Half the times the qubit will measure as 0 and half the times it will be 1!

In the next parts, we will explore this qubit in more detail and see how we can make a qubit in |0> or |1> state into this kind of superposition state where either is equally possible! (Spoiler, it's the venerable Hadamard gate)

Check out Part 2 of the series and thanks for reading!

Check out the code for the complete simulator.