How Shor’s algorithm is implemented today: Kitaev’s approach

Anyone who is interested in quantum computing knows about Shor’s factoring algorithm, even if you have just heard of it.

So can we actually start using Shor’s algorithm to factor large numbers and break RSA encryption? Not so fast! So far, only small numbers such as 15,21 etc. (15 was the first number to be factored in 2001) have been successfully factored. This is because Shor’s algorithm requires a very large number of qubits. It is currently not possible to accurately control so many because the physical qubits we have today are susceptible to many errors (especially for multi-qubit gates) and are not usable for large periods of time (another way of saying this is that they have short coherence times).

Then how was 15 factored? Using the Kitaev approach. That’s what I hope to explain in this article. In a nutshell, it is possible to give out the answer of the algorithm one bit at a time instead of all at once. This reduced the number of qubits required. I will also show you how to implement this algorithm on an IBM machine.

In this blog post, I am not going to explain Shor’s algorithm from the basics. If thats what you are looking for, you should check out Jonathan Hui’s article on Shor’s algorithm and the Qiskit textbook chapter on the same. This blog focuses on implementing the algorithm using the Kitaev approach. I will also briefly talk about the things you must keep in mind to implement this algorithm on Qiskit.
Our aim will be to factor the number 15.

QC — Cracking RSA with Shor’s Algorithm

Shor's Algorithm

The Kitaev Aproach

Some Examples

Let us first start with a simple example.

Figure 1: A CNOT gate

Lets say that we do not have access to a CNOT gate. How would we implement the above circuit? With our classical intuition, a CNOT gate is very similar to an if statement.

if b0 == 1:
        b1 = 1
else:
        b1 = 1

So we can implement our circuit in the following way

Figure 2: CNOT gate. The arrow means that if the measured value is 1, apply the X gate.

Here the arrow means that if the measured value for b0 is 1, only then apply the X gate on b1 else do not apply the X gate (remember that CNOT is just a controlled X gate). Note two important aspects of such an implementation

1. The circuits have to execute in a sequence. That is, you can only execute the second circuit after you have executed the first since you require the result of the measurement from the first circuit.
2. This semi classical implementation of a CNOT gate is NOT a perfect replacement for the quantum CNOT gate. Remember that the quantum CNOT gate as shown in Figure 1, also entangles the two qubits into the state |00> + |11>. The semi classical approach on the other hand has no entanglement. However as we shall see, for our purposes, this will do.

Another example is the following circuit

Figure 3

A and B are any single qubit gates. I have used the two colours to differentiate between the two qubits and the gates which they are the control bits for. Observe that before we apply the CNOT gate, the two qubits b0 and b1 are not coupled at all. In a situation where we do not need them to be entangled, we can then implement our CNOT gate semi classically.

Figure 4

As you can see we have to run two circuits, however for both we only need 2 qubits instead of 3.Now we can apply this approach to Shor’s algorithm.

Shor’s Algorithm Circuit for factoring 15

To factor N = 15, we first need to decide the size of two registers, period register(where we perform the inverse QFT) and computational register(where we perform modular exponentiation). Size of the period register is 3 and that of the computational register is 4 (minimum number of bits needed to represent 15 in binary).

Figure 5: Circuit for factoring 15

If you observe carefully, this is exactly like our second example! However instead of just b0 and b1 we have three qubits and instead of a single qubit register b2 we have a multiqubit register. Here is the same diagram coloured.

Figure 6

I have coloured to differentiate between the three different parts of the circuit which we shall separate. All the gates which are not coloured will be semi classically implemented.

Figure 7

This is Kitaev’s approach! As you can see that we have reduced the period register from 3 qubits to just 1 qubit. So we can always allot just one qubit for the period register and we have to keep recycling it. While in the case of 15 this just a reduction of just 2 qubits, even if we take the case of 21 qubits the period register normally requires 9 qubits! This is why the Kitaev approach is preferred when we want to use the minimum number of qubits to factor the number. Also the answer will be received bit by bit instead of coming all at once.

Before we try to run our algorithm on Qiskit, let us analyze how to make the modular exponentiation gets (which act on the period register).

Qiskit Implementation

Here I will not be discussing a step by step approach to writing the code. Instead, I will discuss some hints and nuances one must keep in mind before implementing this algorithm.

Modular Exponentiation Gates

One important aspect of Shor’s algorithm is being able to perform the modular exponentiation operation.

Let us discuss how to make the three gates for N = 15, namely U⁴, U² and U. As an example I am taking the case of a = 2.

What is the approach? Note the input for the gate and see what kets it consists of. For each ket, find the operation of the gate on the ket. Then make a circuit which is able to perform those operations. We will not be creating a gate which performs the correct operation on every ket, rather we will only work with the kets we have to. An example will illustrate this.

This turns out to be a trivial case. But the next case is more interesting.

For the next gate.

And we have our three gates! Note that this is just one way to do it and you might notice that as the number of gates or N gets bigger such a procedure is more difficult to carry out. You can either add each gate seperately or group them together into one gate in the following manner.

#Making U gate for a = 2, N = 15
U = QuantumCircuit(4)
#Performing swap operations
U.swap(0,1)
U.swap(2,3)
U = U.to_gate()
U.name = "%i^%i mod 15" % (a,0)
c_U= U.control()

You can try creating the gates for a = 2,11,8 and 13.

How to implement measurement based gates

Here the answer depends on the backend you use. If you are using the qiskit simulator or the QASM simulator, then our job is very straightforward, as the simulators have such gates builtin.

#Assume qc is a defined QuantumCircuit and cr is a ClassicalRegister
#Add X gate if classical register has value = 1qc.x(qubit).c_if(cr,1)

However such functionality is not yet supported by the IBM machines. Therefore the above code will not work. However there is a solution!

In ref[2], they have proposed the following implementation, where we need to create the circuits separately and add the phase gates depending on the values measured before.

Semiclassical Approach proposed in ref[2]

Congrats! You are now ready to implement this algorithm on Qiskit. I hope you have fun trying it out for yourself for different values of N and a.

Resources

1. Quantum Computation and Quantum Information, Michael A. Nielsen & Isaac L. Chuang.
2. Experimental study of Shor’s factoring algorithm using the IBM Q Experience
3. Stephane Beauregard, Circuit for Shor’s algorithm using 2n+3 qubits, arXiv:quant-ph/0205095
4. A. Y. Kitaev, http://arxiv.org/abs/quant-ph/9511026 (1995)