Shor’s Algorithm (My Lab)
Cahyati Supriyati Sangaji (My Note)
In this lab, you will implement a quantum program to factor the number 15. In order to do this, you will write Qiskit code for Shor's algorithm.
You might find the following chapters of the Qiskit Textbook useful:
- Shor’s algorithm: https://qiskit.org/textbook/ch-algorithms/shor.html
- Quantum phase estimation: https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html
- Quantum Fourier transform: https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html
Remember, to run a cell in Jupyter notebooks, you press Shift + Return/Enter on your keyboard.
Installing necessary packages
Before we begin, you will need to install some prerequisites into your environment. Run the cell below to complete these installations. At the end, the cell outputs will be cleared.
!pip install -U qiskit==0.19
!pip install -U qiskit-ibmq-provider==0.7from IPython.display import clear_output
clear_output()
Review of Shor’s Algorithm
Shor’s algorithm can be used to factor numbers 𝑁 that are products of the form
where 𝑝 and 𝑞 are prime numbers. This is done in four main steps, similar to the implementation of quantum phase estimation. In this case, we will use two registers of qubits. The first register will have 𝑛 qubits, and will contain the measurement qubits. The second register will have 𝑚 qubits, and will be the eigenstate for quantum phase estimation.
After the measurement outcomes are determined, we will need to do additional classical post-processing in order to determine the factors or to decide to run the program again.
Graded Exercise 1: Implementing Shor’s Algorithm
In this lab, we will implement Shor’s algorithm and use it to factor 15 into 3 and 5.
1. Initializing the qubits
We will need to initialize our qubits as described above by applying a Hadamard gate on each of the 𝑛n measurement qubits. We will also set the target qubits to |1⟩, since that is the eigenstate onto which the unitary operator 𝑈 will be applied. Here, |1⟩ is initialized by applying an 𝑋 gate on the last qubit.
We have created a function below called initialize_qubits which takes in three arguments. The first argument is the quantum circuit onto which the gates will be applied. The second argument, n, is the number of measurement qubits. The third argument, m, is the number of target qubits for the unitary operator.
def initialize_qubits(given_circuit, n, m):
### WRITE YOUR CODE BETWEEN THESE LINES - START
for m in range(n):
given_circuit.h(m)
given_circuit.x(3+m)
#given_circuit.h(range(n))
#given_circuit.x(n+m-1)
### WRITE YOUR CODE BETWEEN THESE LINES - END2. Modular exponentiation
We have created a function called a_x_mod15 below which takes in two arguments, a and x, and implements the unitary operator
You do not need to modify this function.
from qiskit import QuantumCircuitdef a_x_mod15(a, x):
if a not in [2,7,8,11,13]:
raise ValueError("'a' must be 2,7,8,11 or 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
Note that the function a_x_mod15 creates a 4-qubit unitary controlled by an additional fifth qubit. In order to use this gate, you will need to append it to your quantum circuit using Qiskit's circuit.append() function by passing in the five qubits in a list containing the control qubit first, followed by the four target qubits.
Below, we have created a function called modular_exponentiation which takes in four arguments. The first argument, given_circuit, is the circuit onto which modular exponentiation will be applied. The next two arguments, n and m, are the numbers of measurement and target qubits. The schematic above for Shor's algorithm will be useful here. The last argument, a, is the base of the modular exponentiation. You will need to call the function a_x_mod15 as needed in the function below.
def modular_exponentiation(given_circuit, n, m, a):
### WRITE YOUR CODE BETWEEN THESE LINES - START
for m in range(n):
given_circuit.append(a_x_mod15(a, 2**m), [m] + [i+n for i in range(4)])
### WRITE YOUR CODE BETWEEN THESE LINES - END3. Implementing the inverse quantum Fourier transform
The last step before measuring the first 𝑛 qubits is the implementation of the inverse quantum Fourier transform. As with lab3(Quantum Phase Estimation), you can either implement it on your own or use Qiskit's circuit library.
The function apply_iqft takes two arguments. The first argument, given_circuit, contains the qubits onto which the inverse quantum Fourier transform will be applied. The second argument, measurement_qubits, contains the list of qubits onto which the inverse quantum Fourier transform will be applied.
from qiskit.circuit.library import QFTdef apply_iqft(given_circuit, measurement_qubits):
### WRITE YOUR CODE BETWEEN THESE LINES - START
# Do inverse-QFT
myQFT = QFT(num_qubits=n, approximation_degree=n,
do_swaps=False,insert_barriers=False, name='iqft')
given_circuit.append(myQFT.inverse(),measurement_qubits)
# given_circuit.append(QFT(len(measurement_qubits),
# do_swaps=False).inverse(), measurement_qubits)
### WRITE YOUR CODE BETWEEN THESE LINES - END
4. Putting it all together
Finally, we combine the functions to construct the quantum program that implements Shor’s algorithm.
The next lines of code put everything together.
from qiskit import QuantumCircuitdef shor_program(n, m, a):
# set up quantum circuit
shor = QuantumCircuit(n+m, n)
# initialize the qubits
initialize_qubits(shor, n, m)
shor.barrier()# apply modular exponentiation
modular_exponentiation(shor, n, m, a)
shor.barrier()
# apply inverse QFT
apply_iqft(shor, range(n))# measure the first n qubits
shor.measure(range(n), range(n))
return shor
n = 4; m = 4; a = 7
mycircuit = shor_program(n, m, a)
mycircuit.draw(output='text')
That’s it! In order to run your quantum circuit and get the measurement outcomes, you simply need to run Qiskit's execute function as follows.
from qiskit import Aer, execute
simulator = Aer.get_backend('qasm_simulator')
counts = execute(mycircuit, backend=simulator, shots=1000).result().get_counts(mycircuit)
from qiskit.visualization import plot_histogram
plot_histogram(counts)
for measured_value in counts:
print(f"Measured {int(measured_value[::-1], 2)}")Out:
Measured 8
Measured 0
Measured 4
Measured 12You can then follow the classical post-processing details to obtain the factors from the measurement outcomes. If you did everything correctly, you should have only measured 0, 4, 8 and 12.
Classical post-processing
from math import gcdfor measured_value in counts:
measured_value_decimal = int(measured_value[::-1], 2)
print(f"Measured {measured_value_decimal}")
if measured_value_decimal % 2 != 0:
print("Failed. Measured value is not an even number")
continue
x = int((a ** (measured_value_decimal/2)) % 15)
if (x + 1) % 15 == 0:
print("Failed. x + 1 = 0 (mod N) where x = a^(r/2) (mod N)")
continue
guesses = gcd(x + 1, 15), gcd(x - 1, 15)
print(guesses)
Out:
Measured 8
(1, 15)
Measured 0
(1, 15)
Measured 4
(5, 3)
Measured 12
(5, 3)Additional reading
- The first experimental demonstration of Shor’s algorithm was completed by researchers at IBM and Stanford in 2001 using an experimental platform called nuclear magnetic resonance. You can find the paper here: https://www.nature.com/articles/414883a
- For additional details on the method of continued fractions, you may refer to this page (https://riliu.math.ncsu.edu/437/notes3se4.html) or any standard reference such as Mermin’s Quantum Computer Science text.
References:
Qiskit (Global Summer School), Introduction to Quantum Computing and Quantum Hardware — Lab 4.
