Arithmetic on Quantum Computers: Addition

12 min readSep 8, 2018

In this story, I will be going over the basics of addition, on classical as well as quantum computers. We will also implement an adder circuit for a quantum computer, using QISkit, IBM’s quantum computing API for Python.

This is also the first in a series of tutorials that will encompass other basic binary operators and more complex tasks such as solving linear equation systems and implementing matrix operations.

Let’s get started.

How do (classical) computers add?

When we were kids, we were taught to do addition using a few simple rules: add the digits in the units term for each number, pass any carry digits over to the tens column, pass any carry from the tens column to the hundreds column, and so on. Computer addition also works the same way, except that there can only be two possible values for every digit, 0 or 1, and the only possible carry is 1.

Take 10101 and 11010 (21 and 26). The resulting sum would be 101111 (47). We can arrive at this, step by step, as shown below:

To enable a computer to do the same, we simply need to feed it with a set of instructions that mirror the rules we follow while performing addition.

There are two operations performed during addition: the carry operation and the sum operation. Computers can also use a type of adder called a half adder, which neglects carry bits, but we will focus on the type that does take carry bits into account, called a full adder. Full adder networks use a few simple rules:

Start at the least significant (rightmost) bit.
Pass all carry bits to the column to the immediate left.
Calculate the carry for the most significant (leftmost) bit.
Column-wise, add up the input carry bit and those of the two addends.

We can, from here, now implement a simple adder network on a quantum computer using these same rules.

So what’s the difference?

Classical computers are made up of billions of tiny units called bits. These bits can, at any point of time, be in the zero (|0>) or the one (|1>) state, but only one of those at one point, and are stored in groups called registers. Many registers, when put together, form a circuit. Quantum computers are almost the same as the regular (classical) computers that we use everyday; the two most important differences are:

Instead of using classical bits, quantum computers use quantum bits, or qubits.
The values of qubits cannot be directly outputted, but must be measured and stored in classical bits and then read.

For the purposes of this tutorial, qubits work essentially the same way as classical bits, except they are stored in special registers called quantum registers, and many quantum registers form a quantum circuit.

While this is all you need to follow the rest of the tutorial and write your first quantum program, if you are curious, for a deeper understanding of how qubits allow quantum computers to do things that classical computers cannot, check out this great article.

Where’s my quantum computer?

Unfortunately, quantum computers aren’t as easily accessible as classical ones, and cannot be bought off-the-shelf like laptops or desktop PCs are. However, we can still write code for and run programs on quantum computers using platforms like the IBM Q Experience, which allows users to interact with quantum hardware and simulators. The Q Experience devices (also called backends) can be programmed using QISkit, an SDK (Software Development Kit) created by IBM.

In case you haven’t got QISkit running on your computer, follow these steps to install it:

If you have the PIP tool on your machine, simply enter and execute this in your command line to install QISkit: pip install qiskit . If you are using Python 2 version 2.7.9 or later, or Python 3 version 3.4 or later, PIP is already installed.
To get PIP, save the text file from here and run python get-pip.py in your command line.

Next, in order to interact with the simulator, you need to set up a IBM Q Experience account, which can be done here. Under ‘My Account’, select ‘Advanced’, and copy the API token displayed. Use the configuration file (called Qconfig.py) from here, and replace the API token placeholder with the one you copied, and place the file in the same directory as the one you intend to create your quantum program in.

A completed, working Qconfig.py file would look like this:

APItoken = '123456789abc...'
config = {
'url': 'https://quantumexperience.ng.bluemix.net/api'
}

To get you familiarized with how QISkit works, we’ll write a small, quantum “hello world” equivalent:

First we import all the QISkit modules that we need to run our program.

from qiskit import ClassicalRegister, QuantumRegister
from qiskit import QuantumCircuit
from qiskit import register, execute

Then we create a quantum register called qreg, and a classical register called creg, with 1 bit each, and put them together in a quantum circuit called circ.

qreg = QuantumRegister(1)
creg = ClassicalRegister(1)
circ = QuantumCircuit(qreg, creg)

After that, we apply a X gate (more on how it works later) on the qubit in register qreg, and measure its value and store it in the bit of classical register creg.

circ.x(qreg[0])circ.measure(qreg[0], creg[0])

Finally, we set up the API call and execute our program. The shots parameter decides how many times the instructions we have programmed is run.

import Qconfig
register(Qconfig.APItoken, Qconfig.config["url"])result = execute(circ, backend='ibmq_qasm_simulator',                                                               shots=2).result()
print(result.get_counts())

The output of the program should be this:

{'1': 2}

This means that both of the times the program was run, the value of the bit in the classical register was 1.

Now that we’ve covered the basic syntax of QISkit, we can finally begin to program a quantum adder. If you still aren’t comfortable with QISkit, a great set of annotated examples is available on the QISkit GitHub repository.

Converting rules into gates

When we execute a program on a classical computer, the computer first converts the instructions into sequences of operations called logic gates, which are applied to bits to change their values based on certain conditions. Quantum computers work the same way.

However, a high level language like Python or Java does not exist yet for quantum computers, so we work at the level of logical gates directly. In this sense we won’t be really writing code for a quantum computer, but listing the quantum gates that we want the computer to perform.

To construct an addition operator we need a few basic quantum logic gates, which we will use to perform the steps part of the addition process:

The quantum X gate acts like a classical NOT, flipping a qubit in the |0> state to the |1> state, and vice versa.
The CX (Controlled — X) gate acts on two qubits at once, with one being called the control qubit, and the other being called the target qubit. This gate applies an X gate on the target qubit only if the control qubit is in the |1> state.
The CCX (Controlled — Controlled — X) gate acts on three qubits a once, with two control qubits and one target qubit. It applies an X gate on the target qubit only if both control qubits are in the |1> state.

To calculate the carry bit, we need a gate that takes three input qubits: the carry qubit from the previous column, and one qubit from each of the addends (go back to the rules for full adder networks if this doesn’t make sense). The gate would perform an operation to set a qubit to the |1> state if at least two of the input qubits are in the |1> state.

The truth table (a table showing the possible inputs and outputs for a gate) for the carry gate would look like this, if the two numbers were stored in registers called a and b, and a carry register c:

We can break down this operation into multiple steps:

Compare the qubits from c and a first, and if both are in the |1> state, flip the bit the output is being fed to, which, in this case, is the next bit from the carry register c.
Flip the b register qubit if the qubit from a is in the |1> state.
Compare the qubits from c and b, and if both are in the |1> state, flip the output bit.

This cannot be done using any one of the X, CX, or CCX gates, so we can try to achieve this behavior using multiple gates:

Visualization of the carry gate using CXX and CX gates. Crosses represent the target qubit, and filled in circles the control qubits.

The lines with two filled in circles and one hollowed out circle with a cross represent the CCX gates, and the one with one of each circle represents the CX gate.

For the sum gate, we need a gate that takes three input qubits: the input carry qubit, and one qubit from each of the addends. The gate would perform an operation that would achieve the same results as the truth table below:

The output is the qubit from register b because this way we can save space and operations by overwriting the b register with the sum instead of having another register to store it. Looking at the truth table, we can break down the operation into smaller steps:

Flip the qubit from the b register if the input carry qubit is in the |1> state.
Flip it again if the qubit from A is in the |1> state.

We can achieve this behavior using CX gates:

Visualization of sum gate using CX gates. Crosses represent the target bit, and filled in circles the control bits.

Now that we have the basics down, we can implement a quantum adder using QISkit.

Implementing a quantum adder

The first step would be to take two numbers as user input.

first = input("Enter a binary number with less than 8 digits")
second = input("Enter another binary number with less than 8 digits")

The reason we need numbers with less than 8 digits is because the IBM QISkit simulator only has 32 (qu)bits for us to use. If we let each number we input be n bits long, then we would need:

2n bits to store the two numbers
n carry bits (look at how classical computers add again if this doesn’t make sense)
n + 1 classical bits to store the result of the addition.

This adds up 4n + 1 bits, of which 3n are qubits. Since we only have 32 (qu)bits to work with, n can be, at maximum, 7.75, which gives 7 after rounding down to the nearest integer.

We do not need another register to store the (quantum) result because we overwrite the second number with the sum of the two numbers to save qubits. Now we check which number is longer, and use the length of the longer one to set the sizes of our registers, and then we combine all the registers and create a quantum circuit.

l = len(first)
l2 = len(second)
if l > l2:
     n = l
else:
     n = l2#Initializing the registers; two quantum registers with n bits each
#1 more with n+1 bits, which will also hold the sum of the two #numbers
#The classical register has n+1 bits, which is used to make the sum #readable
a = QuantumRegister(n) #First number
b = QuantumRegister(n+1) #Second number, then sum
c = QuantumRegister(n) #Carry bits
cl = ClassicalRegister(n+1) #Classical output
#Combining all of them into one quantum circuit
qc = QuantumCircuit(a, b, c, cl)

The next step is to transfer the information about the two numbers inputted to our quantum registers. However, as the registers are made of qubits, we cannot directly assign values from the bit strings to the quantum register . Fortunately, when we create a new quantum register, all of its qubits start off in the |0> state, so flipping the qubits should give us the one state |1>, which we can perform with the quantum X gate.

#Setting up the registers using the values inputted
for i in range(l)):
    if first[i] == "1":
       qc.x(a[l - (i+1)]) #Flip the qubit from 0 to 1
for i in range(l2)):
   if second[i] == "1":
      qc.x(b[l2 - (i+1)]) #Flip the qubit from 0 to 1

Now that the registers a and b hold the two numbers, we can move to the addition. We first create a process to calculate and pass forward the carry bits using the quantum logic gates CX and CCX.

#Implementing a carry gate that is applied on all (c[i], a[i], b[i]) #with output fed to c[i+1]
for i in range(n-1):
    qc.ccx(a[i], b[i], c[i+1])
    qc.cx(a[i], b[i])
    qc.ccx(c[i], b[i], c[i+1])

However, the register b is going to be used to store the sum of a and b, so instead of creating an extra carry bit for the last carry, and then transferring that to register b, we can substitute the last qubit of b for the last carry bit.

#For the last iteration of the carry gate, instead of feeding the #result to c[n], we use b[n], which is why c has only n bits, with #c[n-1] being the last carry bit
qc.ccx(a[n-1], b[n-1], b[n])
qc.cx(a[n-1], b[n-1])
qc.ccx(c[n-1], b[n-1], b[n])

We now reverse all the operations we just did to ensure that the sum gates (which we will implement) are fed with the correct inputs, and to revert the carry register to its original state.

Reversing the operations performed is simple: we perform the same operations again, because all quantum logic gates are reversible: applying the same gate twice to a qubit will leave the qubit in the same state it was in before applying the gates.

#Reversing the gate operation performed on b[n-1]
qc.cx(c[n-1], b[n-1])
#Reversing the gate operations performed during the carry gate implementations
#This is done to ensure the sum gates are fed with the correct input bit states
for i in range(n-1):
    qc.ccx(c[(n-2)-i], b[(n-2)-i], c[(n-1)-i])
    qc.cx(a[(n-2)-i], b[(n-2)-i])
    qc.ccx(a[(n-2)-i], b[(n-2)-i], c[(n-1)-i])
    #These two operations act as a sum gate; if a control bit is at                
    #the 1> state then the target bit b[(n-2)-i] is flipped
    qc.cx(c[(n-2)-i], b[(n-2)-i])
    qc.cx(a[(n-2)-i], b[(n-2)-i])

After performing the inverse carry and sum operations, the result of the addition should be stored in the b register. However, in order to view the result, we must measure the qubits and copy the result into the classical register cl.

#Measure qubits and store results in classical register cl
for i in range(n+1):
    qc.measure(b[i], cl[i])

Finally, we set our API token and url. We also choose a backend to execute our program on, in this case the local QASM simulator.

#Import configuration and set API token and url
import Qconfig
register(Qconfig.APIToken, Qconfig.config['url'])#Set chosen backend and execute job
num_shots = 2 #Setting the number of times to repeat measurement
selected_backend = "local_qasm_simulator"
job = execute(qc, selected_backend, shots=num_shots)
#Get results of program
job_stats = job.result().get_counts()
print(job_stats)

The output I got when I ran the program with inputs 10101 (21) and 11010 (26) was 101111 (47), and can be seen below:

Enter a binary number with less than 8 digits. 10101
Enter another binary number with less than 8 digits. 11010
{'101111': 2}

We can also visualize the gate sequence executed, making it easier for us to understand what operations took place during the execution of the program. For the same two numbers (10101 and 11010), the gate sequence shown below is executed:

The addition program used in this tutorial can be found here.

Looking back

So, there you go!

Addition for quantum computers, made easier and simpler. Note that just like how there are many ways to add two numbers on a classical computer, there are many ways to do so on a quantum computer as well.

The method outlined here, while simple and easy to pick up, is not the most efficient, as it simply replicates the processes used by classical computers on a quantum computer. Another, faster method, will be explored in my next article.