Arithmetic on Quantum Computers: Multiplication

10 min readDec 8, 2018

This story is the third installment of my quantum arithmetic series, the first two covering different ways of adding numbers. This story covers the implementation of the multiplication operation on a quantum computer, and a step-by-step guide for writing a program that can multiply two numbers using Qiskit, IBM’s quantum computing API for Python.

Let’s get started.

How do (classical) computers multiply?

Computers don’t have built-in multiplication circuits like they do adders, so they perform repeated addition to implement multiplication. The method used is similar to the one taught in elementary school.

Suppose you want to multiply two numbers, say 1101 and 11 (which would be equivalent to 13 and 3). Doing it in your head is easy: you would compute the result (39) in a second or two, without needing to think about the intermediary steps. On a computer, however, these steps have to be defined. Taking the same two numbers, but this time breaking it down into simpler steps, we can derive the rules used by a computer:

Step-by-step multiplication of two numbers.

Following the picture above, we get:

Multiply 1101 by the rightmost 1 in 11, which gives 1101.
Multiply 1101 by the second 1 in 11 from the right, which gives 1101 again.
Shift this product left by 1 digit.
Sum the two numbers, which gives you the product of 1101 and 11, 100111 (39).

The number on top (1101) is usually called the multiplicand, and the number at the bottom (11) is called the multiplier. The numbers we sum up to get the product are called the partial products. These operations (multiplication by either 0 or 1, and bit shifts) can be performed by a computer, which would follow a similar procedure to multiply:

Take the product of the multiplicand and the rightmost digit of the multiplier.
Store the partial product.
Take the next digit of the multiplier and perform the same operations.
Shift the partial product one bit to the left.
Take the third digit of the multiplier, repeating the same procedure, and so on for all the digits of the multiplier, increasing the number of bits by which the partial products are shifted left with each iteration.
Sum up all the partial products using full and half adders.

Using these rules, we can create a simple multiplication circuit. But, as we will see below, there is a better way to multiply numbers, using something far cooler: the quantum Fourier transform.

Recap: quantum Fourier transform

In case the quantum Fourier transform is a little fuzzy, in a nutshell, it does this:

Given a milkshake, it gives you a list of its ingredients and quantities.
Similarly, given a signal, it gives you the pure (sinusoidal) waves that make up that signal.

We can use the quantum Fourier transform to add two numbers; for an explanation why, check out my tutorial on adding two numbers using the quantum Fourier transform here in case you missed it. Using this addition implementation, we can compute the product of two numbers faster, and using a far smaller number of qubits.

Multiplication as repeated addition

We can perform multiplication in another way as well: we can add a number to itself multiple times until we have a bit string that is equivalent to the product we would have obtained if we performed a multiplication operation. We can write down a few simple rules to use with this method:

Create a bit string holding the value 0, which we will call the accumulator.
Add the multiplicand to the accumulator.
Decrement the multiplier by one.
Repeat the last two steps until the multiplier hits zero.

If we take the same two numbers that we used above (1101 and 11), we would get this:

We will use this version of multiplication in the operation that we will implement.

Recap: QFT based addition

Let’s go over the functions we used in our quantum Fourier transform based addition program:

def createInputState(qc, reg, n, pie)def evolveQFTState(qc, reg_a, reg_b, n, pie)def inverseQFT(qc, reg, n, pie)

createInputState() took in a register and computed its Fourier transform by applying a series of Hadamard gates and conditioned rotations:

Visualization of createInputState() for a 5 qubit register.

After that we called evolveQFTState(), which applied rotations to the first register we passed conditioned on the qubits of the second register:

Visualization of evolveQFTState() for a 5 qubit register

Finally we called inverseQFT() to perform the inverse quantum Fourier transform on the register we passed to the createInputState() function:

Visualization of inverseQFT() for a 5 qubit register

We will need these functions for our quantum multiplier, so be sure to check out my tutorial covering how the quantum Fourier transform works in case you aren't sure what just happened, or need a quick refresher.

Creating a quantum multiplier

The multiplier we will develop will follow these rules:

Get the multiplicand and multiplier as user input.
Create a quantum register to use as the accumulator.
Add the multiplicand to the accumulator using quantum Fourier transform based addition.
Decrement the multiplier using quantum Fourier transform based subtraction.
Repeat this until the multiplier is zero.
Output the value of the accumulator, which now holds the product of the two numbers inputted.

So we keep adding and decrementing until the multiplier becomes zero.

But how do we check whether the multiplier is zero?

As of now, there is no classical control in Qiskit other than the c_if() method, which allows us to apply a gate, or a series of gates, based on the value held in a classical register:

qc.x(a[0]).c_if(cl, 1)

The above line tells the quantum computer over at IBM Q to apply an X gate to the first qubit of register a only if the value of the bit string stored in the classical register cl is equal to |00…01>. To the best of my knowledge, there is no way we can terminate a Qiskit job based on the value of a classical register.

What we can do is convert the multiplication operation into a series of addition jobs, returning the value of the multiplier each time, and wrapping the entire operation around a classical while loop, which would look like this:

while multiplier != 0:
    #Call function to add multiplicand to accumulator

Here we keep calling a function that updates the values of the accumulator and the multiplier, until the multiplier becomes zero. At that point the accumulator holds the product of the two numbers (in case you don’t see why, go back up to the breakdown of the multiplication operation).

We only really need to make a few modifications to the addition operation we implemented in the last tutorial to construct a multiplier using this method; we have to refactor it so that it takes two QuantumRegister objects holding the multiplicand and the accumulator, and adds instructions that add the multiplicand to the accumulator to a passed QuantumCircuit object.

Let’s start off by changing the arguments that the add() function takes:

def add(reg_a, reg_b, circ):
    """
    Add two quantum registers reg_a and reg_b, and store the result     
    in 
    reg_a.
    """

We should also define what these parameters are:

reg_a: the QuantumRegister that is added to reg_b. In our case it should hold the multiplicand.
reg_b: the QuantumRegister that is updated by increasing the value it holds by the value stored in reg_a. In our case it should hold the accumulator.
circ: the QuantumCircuit that holds both reg_a and reg_b, which we add instructions to.

The functions createInputState() and inverseQFT() stay the same. We only introduce a couple of new lines in evolveQFTState():

def evolveQFTState(qc, reg_a, reg_b, n, pie):
    """  
    Evolves the state |F(ψ(reg_a))> to |F(ψ(reg_a+reg_b))> using the 
    quantum Fourier transform conditioned on the qubits of the  
    reg_b. Apply repeated phase rotations with parameters being pi    
    divided by increasing powers of two.
    """
    l = len(reg_b)
    for i in range(0, n + 1):
        if (n - i) > l - 1:
            pass
        else:
            qc.cu1(pie / float(2**(i)), reg_b[n - i], reg_a[n])

What does this do?

It allows us to pass two registers that are not of the same length, as long as reg_a is larger than reg_b. To see why this happens, take the case of reg_a having 6 qubits, and reg_b having 4.

When we call evolveQFTState() and pass reg_b and n = 4, the first iteration within the for loop would involve using the qubit of reg_b at index 4, which does not exist, resulting in our program throwing an error.

If we check whether the value of the index of reg_a we are about to use is less than the length of reg_a, we can avoid the error, which is why we compare n-i and l-1:

if (n - i) > l - 1:

If the index value is greater than the length, we skip applying the rotation for that iteration, and our program now works fine with registers of different sizes.

Awesome!

We also need a subtract() function that takes the same arguments as the add() one, but subtracts the second register from the first instead of adding it.

The code for this function is exactly the same as that of add(), except here, when we call evolveQFTState(), we place a minus sign in front of the angle by which we rotate the passed qubit:

qc.cu1(-1*pie/float(2**(i)), reg_b[n-i], reg_a[n])

To do this we introduce a new parameter for the evolveQFTState() and add() function called factor, which can be either 1 or -1:

def add(reg_a, reg_b, circ, factor)
    """
    Add two quantum registers reg_a and reg_b, and store the result 
    in reg_a.
    """
    pie = pi
    n = len(reg_a)    # Compute the Fourier transform of register a
    for i in range(0, n):
        createInputState(circ, reg_a, n - i, pie)
    # Add the two numbers by evolving the Fourier transform   
    # F(ψ(reg_a))> to |F(ψ(reg_a+reg_b))>
    for i in range(0, n):
        evolveQFTState(circ, reg_a, reg_b, n - i, pie, factor)
    # Compute the inverse Fourier transform of register a
    for i in range(0, n):
        inverseQFT(circ, reg_a, i, pie)

In the evolveQFTState() function:

def evolveQFTState(qc, reg_a, reg_b, n, pie, factor):
    """  
    Evolves the state |F(ψ(reg_a))> to |F(ψ(reg_a+reg_b))> using the   
    quantum Fourier transform conditioned on the qubits of the 
    reg_b. Apply repeated phase rotations with parameters being pi 
    divided by increasing powers of two.
    """
    l = len(reg_b)
    for i in range(0, n + 1):
        if (n - i) > l - 1:
            pass
        else:
            qc.cu1(factor * pie / float(2**(i)), reg_b[n - i],    
                 reg_a[n])

Cool!

Now that we’ve defined our addition and subtraction functions, we can construct a loop that helps us multiply two numbers.

If we go back to the rules we defined earlier, two of them look like they should be done inside the loop we are about to create:

Add the multiplicand to the accumulator using quantum Fourier transform based addition.
Decrement the multiplier using quantum Fourier transform based subtraction.

Thanks to the factor parameter that we created, this is an easy task; all we have to do is call add() and pass a 1 to add, and a -1 to subtract. To decrement the multiplier every time we add to the accumulator, we create a 1 qubit register called d, for decrementer, and flip the only qubit in the register.

Now we can take user input to get the bit strings to multiply:

# Take two numbers as user input in binary form
multiplicand_in = input("Enter the multiplicand.")
l1 = len(multiplicand_in)
multiplier_in = input("Enter the multiplier.")
l2 = len(multiplier_in)
# Make sure multiplicand_in holds the larger number
if l2 > l1:
    multiplier_in, multiplicand_in = multiplicand_in, multiplier_in
    l2, l1 = l1, l2

We need to create four registers: three quantum ones to hold the multiplicand, the multiplier and the accumulator, and one classical one to hold the final output and the intermediary multiplier outputs:

accumulator = QuantumRegister(l1 + l2)
multiplicand = QuantumRegister(l1)
multiplier = QuantumRegister(l2)
d = QuantumRegister(1)
cl = ClassicalRegister(l1 + l2)circ = QuantumCircuit(accumulator, multiplicand, multiplier, 
    d, cl, name="circ")circ.x(d[0])

Then we store the bit strings in the registers for the multiplicand and multiplier:

for i in range(l1):
    if multiplicand_in[i] == '1':
        circ.x(multiplicand[l1 - i - 1])for i in range(l2):
    if multiplier_in[i] == '1':
        circ.x(multiplier[l2 - i - 1])

Now all we need to do is create the while loop we talked about earlier:

multiplier_str = '1'while(int(multiplier_str) != 0):
    add(accumulator, multiplicand, circ, 1)
    add(multiplier, d, circ, -1)
    for i in range(len(multiplier)):
        circ.measure(multiplier[i], cl[i])
    result = execute(circ,backend=Aer.get_backend('qasm_simulator'),
                shots=2).result().get_counts(circ.name)
    print(result)
    multiplier_str = list(result.keys())[0]

Once the multiplier reaches zero, we measure and output the product, which is stored in the accumulator:

circ.measure(accumulator, cl)
result = execute(circ, backend=Aer.get_backend('qasm_simulator'),
            shots=2).result().get_counts(circ.name)print(result)

Awesome — looks like we’re done!

Let’s test out our work. If we input 1101 (13) and 101 (5), we should get 1000001 (65) as the output:

Enter the multiplicand. 1101
Enter the multiplier. 101
{'1000001': 2}

Cool!

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

Looking back

We multiplied two numbers on a quantum computer —pretty impressive!

This tutorial was a little different from the previous tutorials covering addition — it also marks a change in the focus of this series to operations that are created using smaller algorithms as building blocks, like how we used repeated addition here to emulate multiplication.

The next article is going to focus on QForest Math, a small wrapper I built to make performing elementary arithmetic operations using Qiskit easier, which I’m super excited about — so stay tuned!