In this tutorial we will go through Shor’s Algorithm and see how to run it on IBM’s quantum computers with Python and Qiskit.
What is the Shor’s Algorithm
Shor’s Algorithm is a quantum algorithm for integer factorisation. Simply put given an odd integer N it will find it’s prime factors.
The algorithm consists of 2 parts:
Classical part which reduces the factorisation to a problem of finding the period of the function. This is done classically using a quantum computer
Quantum part which uses a quantum computer to find the period using the Quantum Fourier Transform.
For the algorithm the steps are as follows:
Pick a random number A such that A < N
Computer the greatest common divisor (GCD) of and N
if the gcd != 1 then we found a factor of N
If not then run the quantum circuit that uses a Quantum Fourier Transform
If the period is odd then go back to step 1
Otherwise we have found the factors of N
The algorithm can be implemented incredibly easily since Qiskit has a baked in function for the algorithm called Shor(N).
Where N will be the integer you wish to factor. For example Shor(21) will find the prime factors for 21.
Note: For this tutorial you will need an API token which you can get by registering here: https://quantum-computing.ibm.com/
from qiskit import IBMQ from qiskit.aqua import QuantumInstance from qiskit.aqua.algorithms import Shor IBMQ.enable_account('ENTER API TOKEN HERE') # Enter your API token here provider = IBMQ.get_provider(hub='ibm-q') backend = provider.get_backend('ibmq_qasm_simulator') # Specifies the quantum device print('\n Shors Algorithm') print('--------------------') print('\nExecuting...\n') factors = Shor(21) #Function to run Shor's algorithm where 21 is the integer to be factored result_dict = factors.run(QuantumInstance(backend, shots=1, skip_qobj_validation=False)) result = result_dict['factors'] # Get factors from results print(result) print('\nPress any key to close') input()