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.
import matplotlib.pyplot as plt
import numpy as np
from qiskit import QuantumCircuit, Aer, execute
from math import gcd
import pandas as pd
from qiskit.visualization import plot_histogram
Step One : Initializing the Qubits
def initialize_qubits(given_circuit, n, m):
given_circuit.h(range(n))
given_circuit.x(n+m-1)
Step Two : Modular Exponentiation
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
from qiskit import QuantumCircuit
def c_amod15(a, x):
if a not in [2,7,8,11,13]:
raise ValueError("'a' must be 2,7,8,11,13")
U = QuantumCircuit(4)
for iteration in range(x):
if a in [2,13]:
U.swap(0,1)
U.swap(1,2)
U.swap(2,3)
if a in [7,8]:
U.swap(2,3)
U.swap(1,2)
U.swap(0,1)
if a == 11:
U.swap(1,3)
U.swap(0,2)
if a in [7,11,13]:
for q in range(4):
U.x(q)
U = U.to_gate()
U.name = "%i^%i mod 15" % (a, x)
c_U = U.control()
return c_U
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.
def modular_exponentiation(circuit, n, m, a):
for x in range(n):
exponent = 2**x
circuit.append(c_amod15(a, exponent),
[x] + list(range(n, n+m)))
Step Three : Applying the Inverse Quantum Fourier Transform
First, we will import the QFT class from the qiskit.circuit library.
from qiskit.circuit.library import QFT
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
Step Four : Implementing the Circuit
def shors_algorithm(n, m, a):
qc = QuantumCircuit(n+m, n)
initialize_qubits(qc, n, m)
qc.barrier()
modular_exponentiation(qc, n, m, a)
qc.barrier()
inverse_qft(qc, range(n))
qc.measure(range(n), range(n))
return qc
n = 4; m = 4; a = 7
final_circuit = shors_algorithm(n, m, a)
Here is what the circuit finally looks like:
Step Five : Running the Program on a Quantum Simulator
To see which values were measured when the circuit was executed, the following lines of code are written.
for measured_value in counts:
print(" {int(measured_value[::-1], 2)}")
Step Six : Classical Processing to Obtain Factors of the Number 15
for i in counts:
measured_value = int(i[::-1], 2)
if measured_value % 2 != 0:
print("Measured value not even")
continue #measured value should be even as we are doing a^(r/2) mod N and r/2 should be int
x = int((a ** (measured_value_decimal/2)) % 15)
if (x + 1) % 15 == 0:
continue
factors = gcd(x + 1, 15), gcd(x - 1, 15) #we saw earlier that a^(r/2)+1 or a^(r/2)-1 should be a factor of 15
print(factors)
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.