So, a couple weeks ago, I got pretty interested in this whole idea of “quantum computing” — a concept which is often described as having the potential to enable certain computing tasks that would be totally infeasible to impossible on a standard computer. For instance, factoring huge numbers for bank encryption, simulating complex molecules for drug synthesis and optimizing circuits for energy storage.
Now the way quantum computers go about solving certain problems is using algorithms — sets of instructions which tell the computer what to do and when to do it in order to arrive at a certain result. These algorithms leverage quantum gates which are analogous to the gates in a classical computer in that they take in qubits (the quantum parallel of bits) as input and return an output based on the combination.
So, because I wanted to get a feel for how these gates work in the context of a quantum circuit, I decided to code a “number adder” (also called a calculator :)) which is capable of adding together two numbers using IBM’s quiskit python library.
The purpose of this article is just to go over how I did that.
Step 1: Adding single digits
Of course, the basic component of any calculator is to be able to add two digits together. Right now, we are going to assume that these numbers have already been converted to binary.
First, we import everything we need.
Then, we define a quantum circuit called qc_one which has four qubits and two classical bits. The two digits that we will add will be stored on qubits 0 and 1.
We write two lines of code qc_one.x(0) and qc_one.x(1) to add X gates to the first two quantum gates. What the X gate does is flip the qubit’s vector over the x axis in quantum space. It switches the amplitudes associated with the 0 basis and the 1 basis, and so it turns 0s to 1s and 1s to 0s. Since qiskit automatically initializes qubits to 0, if we want to include 1s in our sum, we’ll have to add in the X gates. As you can see, we’ve currently commented out the X gate on qubit 1, so our sum is currently 1 + 0.
So, when we are adding two binary numbers, the four possibilities are 0+0=00, 0+1=01, 1+0=01 and 1+1=10. So, we have two digits which are either 0 or 1.
First, let’s focus on the resulting units digit. We can see that it will be a 0 if both of them are 0 or both of them are 1 and it will be a 1 if only one of them is a 0 and the other is a 1. So, what would be helpful is a gate that can figure out if the states of the input gates are the same or different…
This is exactly whtat the Controlled Not gate (CNOT) does. This gate is analogous to the XOR gate in classical computing in that it returns a 0 if the qubits’ states are the same and a 1 if they are different.
Now, the thing about the CNOT gate is it takes two qubits as inputs and writes the result overtop of the second qubit. The first qubit is called the control and the second qubit is called the target.
While we could overwrite the state of our second qubit, we’d prefer to keep it so that we can use it later when we need to figure out the tens digit. The fix is to introduce another qubit — q2 — and put our answer onto there.
So, what we need to do is use the CNOT gate on q0 and q2 and then use it again on q1 and q2. Since, q2 is initialized to 0, the CNOT of it and q0 is going to be whatever value is on q0 (because the CNOT of 0 and 0 is 0 and then the CNOT of 0 and 1 is 1). This is super convenient because then our second CNOT on q1 and q2 is effectively like doing the CNOT on q1 and q0, but just writing the result onto another qubit.
So, we add in the above 6th and 7th lines of code.
Now, we want to figure out the tens digits. Notice that the tens digit is only a 1 if there is any “carrying”, or if both of the qubits we are summing are 1. This is like the AND gate in classical computing. It’s quantum parallel is the “Toffoli Gate”.
Unlike the CNOT gate, the Toffoli gate takes in two control gates and writes the answer onto a seprate qubit. So, we can simply use q0 and q1 as the target gets and write it onto a new qubit, q3. This is why we couldn’t just write the CNOT of q0 and q1 overtop of q1, because then we wouldn’t be able to use it to figure out the tens digit.
Finally, we measure the “ones” digit (on q2) to the 0th classical bit and the “tens” digit (on q3) to the 1st classical bit. In the diagram, the numbers written under the arrows are not the answers to the computation, but just indicate which classical bit that specific measurement is happening on.
In order to actually see our results, we can
and we see that we get 01 100% of the time which is great, because 1 + 0 does equal 1!
Step 2: Adding 2 digit numbers
So the next logical step is to add 2 digit numbers. Now, the jump from one digit to two digits is significantly more challenging than say, the jump from two digits to three digits. This is because we have to integrate carrying, which effectively means that we have to be able to add three digits together.
The way we can do this is by adding the first two digits together and then adding the third digit to the result. Not necessarily as simple as it sounds because we have to account for the fact that after we add the first two digits, the third digit not only has to be handled in relationship to the resulting “ones” digit, but also the resulting “tens” digit.
In total there are four possible cases we could have when summing three digits. 1+1+1 = 11, 1+1+0 = 10, 1+0+0 = 01 and 0+0+0=0. The units digit behaves in a similar way to the units digit above — when there is an even number of 1s, it is 0 and when there is an odd number of ones, it is 1. We can compute this using a couple CNOT gates.
The tens digit on the other hand is 1 if 2 or 3 of the digits we are adding are 1. Unfortunately, there is not a quantum gate that will allow us to have three inputs and figure out of two or more of them are 1.
So, what we need to do is looking at 2 digits at a time. If the first 2 digits are 1 + 1, then regardless of what the third digit is, we are going to carry a 1. If the first 2 digits are 0+0, then regardless of what the third digit is, we are not going to carry anything. But, if the first 2 digits are 0+1, then if the third digit is a 0, we won’t carry anything and if the third digit is a 1, we will carry a 1.
Let’s say the first 2 digits we want to add are the tens digits of the initial 2 digit numbers we are adding. Using a toffoli gate, we will figure out if they will produce a 1 to carry, but then (for reasons that will become apparent below), we are going to add a NOT gate. This results in the situation where if the two digits are 1, we get a 0 and otherwise, we get a 1.
We are going to do the same thing for whatever we carry from summing the units digits and the “units” digit of summing the two tens digits.
Then, we will do a toffoli gate on these two results. From this, we get that if either of our two inputs are 0 (which only occurs when both of their two inputs are 1), we get a 0. By adding an X gate to this, we get that if both of two inputs of either of the two inputs are 1, we get a 1. This is a representation of what we found above: if at least 2 of the original digits are 1, we get something to carry.
Lets say we let q_0 and q_1 be our “ones” digits and q_2 and q_3 be the “tens digits”. We can implement these gates as
which yields a circuit that looks like
We measure q_4, q_6 and q_9, because they are the “1s, 10s and 100s” digits respectively.
This specific circuit adds 11 + 1. By running the circuit, we get that
which returns 100 with 100% probability which is exactly what we want.
Step 3: Using measurement to inform gates
Now, this way of figuring out all the specific gates to represent figuring out if at least 2 of the 3 inputs are 1 required a lot of qubits, and so if we wanted to scale this approach to add 3 or 4 digit numbers, it can be a lot to keep track of.
Back before we implemented those gates, we came to the conclusion that if the first 2 digits are 1 + 1, then regardless of what the third digit is, we are going to carry a 1. If the first 2 digits are 0+0, then regardless of what the third digit is, we are not going to carry anything. But, if the first 2 digits are 0+1, then if the third digit is a 0, we won’t carry anything and if the third digit is a 1, we will carry a 1.
This can be generalized to the idea if the first 2 digits are the same, then we carry whatever either of those digits is. But, if the first 2 digits are different then we carry whatever the third digit is.
First, in order to determine of the first 2 digits are the same or different, we can use our trusty old CNOT gate — say on the q_2 and q_3 (the tens digits of the initial numbers we are adding).
Then, if the answer is 0 (i.e. they are the same), we do a toffoli gate on q_2 and q_3 which returns 0 (in the case that both of them are 0) and 1 (in the case that both of them are 1).
On the other hand, if the answer is 1 (i.e. they are different), we do a toffoli gate on the third digit (in this case, whatever we carry from summing the “ones” digits) and the answer (the result of summing q_2 and q_3). Since this is 1, the answer will be 1 if the third digit is 1 and 0 if the third digit is 0, as desired.
What remains is determining if the answer from the first two digits is 0 or 1. This can be done by measuring the answer to a classical register and then defining a function that will introduce either of the above gates depending on the answer that get.
To do this, we’ll define a function that takes the quantum circuit, the classical register we are measuring to as well as the five qubits we want to measure as inputs like:
Then we can integrate it into the circuit and measure the relevant qubits
which results in
This specific example adds the 11 + 1 which again outputs
100, as we want.
Step 4: Extending the scope
Because we defined this find_carry function as a general form, we can extend the calculator to really add numbers with any number of digits. All we have to do is add the required number of qubits to represent the digits, shift the gates down and add in supplemental gates. For instance, if we want to add three digit numbers, our code would look something like
and the corresponding circuit would look like
This adds 111 + 101 which produces
1100 — perfect!
Step 5: Customizability
So far, all the code we’ve written relies on us manually adding X gates to the qubits which correspond to the digits that are 1. But, of course, in a real calculator, this is not what happens — you write out the numbers you want to add, and it adds them for you.
In order to do this, we need to integrate user input. For the sake of simplicity, we are going to take user input which is already in binary and has leading zeros so that both numbers are the same length. For instance, if we want to add 101 + 10, the inputs would be 101 and 010 (so that both numbers have 3 digits).
I’m not going to cover this too much in depth, as it doesn’t contain any quantum computing concepts, just general python stuff.
First, we’re going to be asking the user to provide their input as two strings and record each individual character as a list. To do this, we have to define a function which splits a word into individual characters
then, we define the variables “val_a” and “val_b” to record the users input and define “list_a” and “list_b” to take in the split sequence.
Then we create a quantum circuit with a quantum register containing four times as many qubits as we have digits in each of our numbers, and a classical register which has one more bit as digits.
Notice that when it comes to adding the tens, hundreds, thousands… digits, there is a repeating set of gates that we employ. We are going to call this a “module” and define a “module function” which adds these appropriate gates.
As arguments, it takes q (the circuit), i (the “place value” that we are adding), x (the classical register) and a (the list containing the string that the user has inputed).
Similar to before, it adds two cx gates to determine the units digit, measures the result and employs the find_carry function accordingly, then it puts another cx gate to determine what carries.
Then, we define the setup function which uses this input to put the gates on the circuit. As with the previous circuits, we make the units digits q_0 and q_1, the tens q_2 and q_3, the hundreds q_4 and q_5 and so on.
The first qubit in each such pair is from the first number (list_a) and the second qubit is from the second number (list_b). We use while loops to add X gates to any qubit that corresponds to a spot in the list containing the string ‘1’.
After that, to add the initial gates that add the “units” digits, we add two cx gates and one ccx gate that take q_0 and q_1 as controls and the 2*len(a)th qubit as a target.
Then, we reference the module function, applying it one time for each pair of qubits after the “units” digits using a for loop.
Finally, we use a while loop to measure the qubits that we need to measure.
Then, we can combine all these things, and actually set up our function and draw it.
Say, we want to sum 101 + 111. Then, when we draw the function, we get
just like before!