Shor's algorithm is a quantum algorithm for factoring a number 𝑁 in polynomial time. We will write a quantum program to factor the number 15. We will implement the code on Qiskit.
The following circuit will be implemented:
We will first import the required libraries from Qiskit.
Any value of 𝑎 except 14 returns the factors of 15. When we test shor's algorithm, we will use a=7
We will define the function c_amod15 which returns controlled-U gate for 𝑎 repeated 𝑥 times. c_amod15 will be a 4 qubit unitary controlled by a 5th qubit which will be appended to the circuit
Next we will carry out modular exponentiation on the circuit and append the fifth qubit by passing the control qubit followed by 4 target qubits.
First, we will import the QFT class from the qiskit.circuit library.
Next we will define a function inverse_qft will take two parameters: the circuit on which the inverse Quantum Fourier transform will be applied and the set of measurement qubits onto which the Inverse Fourier transform will be applied and apply the .inverse() function to get the inverse QFT function.
Now we will call the functions we have created to see the output
Here is what the circuit finally looks like:
To see which values were measured when the circuit was executed, the following lines of code are written.
The output pairs we get for gcd(x+1,15) and gcd(x-1,15) is (1,15) and (5,3) which are the factors of 15! Thus, we factorized the number 15 using Shor's Algorithm.