Doing Kindergarten Math with the World’s Most High-Tech Computer

Note: If you are interested in the complete code for this project, click here.

Despite your personal feelings towards math, I think it’s safe to say that addition is a fairly important thing.

To come to think of it, addition is a bit more than just “fairly” important. I’m quite certain that I use addition every day of my life, and you probably do too! In fact, by using addition so much, we’ve become pretty good at it. Despite this, certain addition problems are too big for us stupid humans to solve. Luckily, despite being stupid, humans are pretty smart. We have made machines that can do addition for us! You may know of this nifty tool as a calculator!

We use calculators all the time, but how does a little hunk of plastic with a dimly-lit screen crunch numbers so much faster than the human brain? If we were to break a calculator open, and zoom in on the circuits making up its internal hardware, we would see that it is made up of fundamental computational units, arranged into networks of logic gates.

These logic gates are what allow computers to perform these computations. Logic gates are no more than collections of wires, passed through different circuit components. One of the most widely used electronic components to make logic gates in the PNP transistor. This transistor allows current to flow through it when there is some amount of current being applied to the middle pin. You can visualize this setup like this:

If a certain current is passed into B, then current will be allowed to flow from C to E. As I said before, these little devices are super important in making logic gates. Let’s look at the AND gate as an example. The function of the AND gate is fairly simple: if I have two wires that join in an AND gate, with a single wire outputted from the gate, the output wire will only allow current pass into it if both wires passing into the AND gate have some amount of current flowing through them. You can imagine the AND gate like this:

If both A and B have current flowing through them, the current will pass to the “out” pin. By using transistors, we can make this logic gate easily! Imagine a series circuit with a battery, two transistors attached in series (in some arbitrary order), and then an LED also placed in series after the transistors. Current will only pass to the LED, lighting it up, if both transistors are activated. It will not light up when only one, or neither of the transistor pins are activated, so this circuit configuration is an AND gate.

If you are interested in how more complex logic gates are actually realized in real computational hardware, here is a blog post I wrote a little while back about implementing a NOR gate (NOT combined with an OR gate) on a real circuit: Implementing NOR Gates.

Now, by putting together a bunch of these logic gates, we can actually make a circuit that adds together two binary numbers. This specific circuit will be discussed later in the article.

Quantum Annealing

Let’s completely switch gears and talk about a field of computation that is completely different: quantum annealing. Quantum annealers are a specific type of quantum computer that are able to harness the properties of quantum mechanics in order to solve certain types of optimization problems incredibly efficiently. This is done by using superconducting metal rings with current passing through them as quibts (units of quantum information), and then exploiting the properties of superposition of state, and entanglement between the qubits in order to make computation much faster. For a more complete introduction to quantum computer, here is an article I wrote another high-level overview article about the subject here: Intro to Quantum Computing.

I am not going to go too in-depth about quantum annealing, for the sake of brevity, but essentially, annealing problems require optimization problems to be phrased as an energy minimization problem, where the problem is defined as an energy landscape, which is merely a function, and the annealing program finds the minimum energy of the function, therefore finding the optimized value of the problem.

There are different models that can be used in quantum annealing problems, such as the Ising statistical model, however, in this article, we will be discussing all problems in the context of the QUBO model, which is defined as:

Where f(x) is the function we are trying to minimize, and Q is some matrix indexed by all possible values that the qubits used in the computation can take.

Bringing it All Together: Addition With Quantum Annealers

So how do these two seemingly different concepts relate? Well, that is exactly the objective of my quantum annealing project: to find two-number partitions after phrasing this as an optimization problem. More specifically, I created a problem to be run on a quantum annealer that can find two numbers that add up to some number inputted into the program.

In order to make this program, I used D-Wave’s quantum annealing simulation software, called Ocean. D-Wave’s platform also has the capabilities for running one’s annealing programs on a real quantum computer, however, due to the amount of testing and experimentation I was doing with this algorithm, I used the simulation.

So without further delay, let’s jump into the code!

We start by first constructing a function that can create the QUBO matrix for addition between two qubits. Since this is a minimization problem, the quantum computer is able to vary the input and output parameters, for every possible combination, and the configuration that yields the lowest energy (calculated using the previously defined function), will have a great likelihood of being outputted by the quantum annealing program. The values within the QUBO matrix allow for us to change the strength of the coherence of entanglement between two qubits, or simply the bias acting on a single qubit (introduced by some external force, in some cases, a magnetic field). For example, the first entry in the variable labelled qubo_matrix is 1. This corresponds to the bias acting on the first qubit, which in this case represents the first “input qubit”. The next value of 2 represents the coherence between the first input qubit and the second input qubit. Through a bunch of trial and error, I deduced that the circuit we could use for addition between two bits would look like this:

The matrix in the function essentially models this circuit. If we put a bunch of this circuit together, connecting the carried bit to the output bit of the next bit place in the number, and at each iteration measuring the least significant bit (and only connecting the final bit every two iterations), we can add much larger numbers. (This circuit description may seem really vague, but I am keeping it short also for the sake of brevity).

This next part of the circuit simply constructs the addition between bits in the previously described circuit, while also incorporating a portion into the circuit that ensures it finds the minimum energy at the entered number (it does this by constructing a parabolic function, with a minimum at the entered value).

This final part of the program simply runs the simulation and outputs all inputs and outputs that are yielded when the simulation is performed. When the simulation is run with the number 3 inputted, for example, the output looks like this:

The first and second number is the brackets represents the measured inputs, and the the third number represents the output. The number below each of the brackets is how many times (out of 2000), that configuration is outputted from the simulation. As can be seen, the most frequently occurring outputs give the correct partitions of the number 3, with 2+1, 3+0, 1+2, and 0+3. This circuit should work for a fairly large range of numbers, but will probably begin to become slower with much larger numbers.

So does this program demonstrate any quantum speedup? Likely not, but it is still an interesting endeavour to see if we can take concepts in classical computing, and actually realize them on quantum computers, using the properties of quantum mechanics to solve our problems. Maybe by making implementations like this, we will become one step closer to having more versatile quantum annealers that can solve more diverse sets of optimization problems. Quantum annealing has the capacity to change the world be solving so many difficult problems in the areas of material science, drug discovery, and even encryption, so I hope that with each new program realized on quantum annealers, we become one step closer to making them applicable in the world.