Menu
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
def initialize_qubits(given_circuit, n, m):
given_circuit.h(range(n))
given_circuit.x(n+m-1)
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)))
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.
def inverse_qft(circuit, measurement_qubits):
circuit.append(QFT( len(measurement_qubits), do_swaps=False).inverse(), measurement_qubits)
Now we will call the functions we have created to see the output
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:
simulator = Aer.get_backend('qasm_simulator')
counts = execute(mycircuit, backend=simulator, shots=1000).result().get_counts(mycircuit)
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)}")
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.
About
Support
Every week, our team curates the most important news, events, and opportunities in the quantum space. Our subscribers gain early access to opportunities and exclusive interviews with prominent individuals. You don't want to miss out.