Let's break the encryption

Shor’s Algorithm exposed/simplified/clarified with a quick overview.

Prof.Peter Williston Shor

Once you read this article, you’ll get a clear overview of how exactly Shor's algorithm works. I tried explaining it, without going into a much deeper section, because it will definitely confuse at the beginner stage.

RSA breaching isn’t only the application of Shor’s algorithm but there are several use-cases like quantum simulation, spin-off technology, Quantum cryptography, etc.

Introduction

Shor’s algorithm was developed by Peter Shor (American mathematician) in the year 1994. It performs integer factorization in polynomial time. The requirement of the algorithm is the quantum computer. The algorithm says that the quantum computer is capable of performing factorization on a very large number in polynomial time. There are many algorithms made for integer multiplication, but there weren’t any of them for factorizing an integer Let us take a deep overview of this useful stuff.

According to Quantitative Church’s thesis, Any physical computing device can be 

simulated by a Turing machine in a number of steps polynomial in the resources 

used by the computing device.

 Eagle eye view

The algorithm is composed of two parts as follows:

1. Turning the factoring problem into the problem of finding the period of a function
2.  Finding the period using the quantum Fourier transform.

Run time on the classical computer is O[exp (L1/3(log L)2/3)] and that on the quantum computer is O(L3).

The algorithm requires both classical as well as quantum computation. The first part is performed classically and the second one utilizes quantum power and responsible for quantum speedup. Shor’s algorithm is probabilistic in nature, it addresses results with high probabilities, and the one with failure can be reduced by looping the algorithm until we get the desired output. 

Salient terms

1. Prime number: The number that can only be divided by itself like, 3, 7, 11, etc.
2. Polynomial Time: An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k), where n is the number of steps to solve the algorithm and k is constant i.e the non-negative number. The polynomial-time algorithm is much faster as compared to the exponential time algorithms. Problems that can be solved by a polynomial-time algorithm are called tractable problems.
3. Euclid algorithm: The Euclidien algorithm is used to find the GCD of two numbers i.e the greatest common divisor. Where a and b are two numbers, the GCD(a, b) = GCD(b, a%b), if a=0 then GCD(a, b)=b and if b=0 then GCD (a, b) = b. The algorithm finds the greatest common divisor in polynomial time.
4. Quantum Fourier transforms: The quantum Fourier transform is a unitary transformation. In quantum Fourier transform the (DFT) Discrete Fourier transform is applied over the amplitudes of the quantum states. The Discrete Fourier transform can be defined as:

  DFT

The Fourier transform is mainly used to map a signal or a function into an alternate representation, characterized by sine and cosines. It’s just a fancy term used to change a form of representation. Discrete Fourier transform has various applications, it is used to digitize the signals, like in Fourier analysis where we describe the internal frequencies of a function. However, the quantum Fourier transform is exponentially faster than the DFT as well as its faster version FFT. Quantum Fourier transformation circuit is composed of Hadamard gates and conditional phase shift gates. Quantum Fourier transform can be defined as shown in the below figure, where x is the basis state.

The Quantum Fourier Transform is a generalization of the Hadamard transform by the Hadamard gate.

6. Period finding: Period finding is the basic building block of Shor's algorithm, similar to the simons algorithm. If finding the period of a function is done efficiently, we would be able to factor integers quickly. To begin with, the states are initialized to state∣0⟩ and apply Hadamard gate to put them into superposition, Another approach would be the use of Quantum Fourier transform. Finding the period heavily depends on the ability of the Quantum computer to achieve superposition. The quantum Fourier transform helps us finding the superior result returning them with their probabilities. The period finding can be also done using the classical approach but can be done in a better way with quantum computers.

You may hear something like “Factoring reduces to order-finding” (Can be done classically) which means that if there is an algorithm to solve order-finding efficiently, we can efficiently solve the factoring problem as well by a polynomial-time reduction from factoring to order-finding. The order finding is similar to the Period finding.

Algorithm

Shor’s algorithm consists of the following steps:

1. Choose a random positive integer m. Compute the greatest common divisor GCD using the euclidean method (m, N) where N is the set of natural numbers N={1, 2, 3, 4, 5…….}. If the greatest common divisor gcd(m, N) != 1, then the value obtained is the non-trivial factor of N. But if gcd(m, N) = 1, then we need to determine the period.
2. This step involves finding the period r of the function f(x) = a^x mod N. Such that f(x)= f(x+r), we need to find the smallest value of r. (This step can be brought into use only with a Quantum computer) 
3. If r is an odd number, then we need to again start from the beginning else we’ll proceed to the next step.
4. If m^r/2 + 1 = 0 mod N, then we again need to go to step 1. else we need to compute the greatest common divisor of (m^r/2- 1, N) using the Euclidean algorithm, And finally we obtain non-trivial factors of N

Calculating the GCD

Suppose we wist to factor 91 i.e N=91. And we know that square of 64 = 4096 i.e 45*91+1, so that x=64 is a solution of square of x = 1 (mod 91) .

The above explanation implies that 45*91=square of 64–1 = 63*65

Summary of Classical computation

1. Choose a random integer.
2. Calculate the GCD. If GCD is equal to one, proceed to the next step i.e the period finding. else if GCD is not one, it's done.
3. If the period is odd, start from step 1. Else proceed to the next step.
4. If m^r/2 + 1 = 0 mod N, then we again need to go to step 1, Else it's done with just calculating the GCD.

Quantum Period finding subroutine

1. Firstly, we need to initialize the registers state, like 

  2. Next, we need to apply the Hadamard gate to register one, for        superpositioning them. where ⊗ denotes the tensor product.

   Where the |0⟩ represents the empty second register

 3. furthermost, we need to construct the f(x) as a quantum function  and  Apply the linear transformation Uf to the two registers to obtain

Here, We have entangled both registers where Uf is the unitary transformation that maps|x⟩ |0⟩ to |x⟩ |f(x)⟩.

4. This step, we apply the Quantum Fourier transform to the first register, which concludes with

5. At the almost end we measure the register one, which yields y. We also find the period r via the continued fraction expansion method by y/2^L.

6. The Continued fraction method helped us obtaining the period r. Now we simply have to perform some classical post-processing. Here if the resulting period value is an odd integer, the process has to be restarted and if it is even we can proceed to further classical computing steps. 

source

The Probabilities can be given by this spectrum as shown above

Summary of Period Finding Algorithm

1. Step 1: Initialize Registers with their states
2. Step 2: Apply Hadamard gates to qubit in register 1.
3. Step 3: Apply Unitary transform to the registers
4. Step 4: Apply quantum Fourier transform to register 1.
5. Step 5: Perform Measurement of register 1.

Implementing the code

We’ll try creating a code for Shor’s algorithm in python. Let’s see how it works. We need to install Qiskit firstly. Below are the installation steps.

Qiskit is tested and supported on the following 64-bit systems:

• Ubuntu 16.04 or later
• macOS 10.12.6 or later
• Windows 7 or later

Qiskit supports Python 3.6 or later.

Create a conda environment.

conda create -n qenv python=3

Activate your new environment.

conda activate qenv

Next, install the Qiskit package.

pip install qiskit

And you are done.

Next, you have to set up the IBM Quantum Experience, Just create an account on it, and get your API token. Now you are fully set for coding with Qiskit.

Let dive into the code now:

from qiskit import IBMQ
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Shor
IBMQ.enable_account('API') # Enter your API token here
provider = IBMQ.get_provider(hub='ibm-q')
backend = provider.get_backend('ibmq_qasm_simulator') # Specifies the quantum device
factors = Shor(21) #Function to run Shor's algorithm where 21 is the integer to be factoredresult_dict = factors.run(QuantumInstance(backend, shots=1, skip_qobj_validation=False))
Factors = result_dict['factors'] # Get factors from results
print(Factors)

Output

The factors resulted are 3 and 7.

Conclusion

Quantum computing is a flagship technology that can yield advancements beyond imagination. Shor's algorithm has been an immense achievement in quantum computing, but still, we are not able to implement it practically due to the Quantum computers haven’t yet reached a significant level that can perform factorization on a very big number. Hope we’ll soon able to see them.

Originally Published on amitnikhade.com

References

https://arxiv.org/pdf/quant-ph/0010034.pdf

https://en.wikipedia.org/wiki/Shor's_algorithm#Quantum_part:_period-finding_subroutine

qiskit.org

I hope you found it insightful. Do hit those claps and follow me for more such amazing stuff.