Published by: Amit Nikhade
July 7 . 2021
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.
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.
The algorithm is composed of two parts as follows:
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.
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.
Shor’s algorithm consists of the following steps:
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
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.
The Probabilities can be given by this spectrum as shown above
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:
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
The factors resulted are 3 and 7.
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
I hope you found it insightful. Do hit those claps and follow me for more such amazing stuff.