0

# Introduction

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:

1. Classical part which reduces the factorisation to a problem of finding the period of the function. This is done classically using a quantum computer

2. Quantum part which uses a quantum computer to find the period using the Quantum Fourier Transform.

For the algorithm the steps are as follows:

1. Pick a random number A such that A < N

2. Computer the greatest common divisor (GCD) of and N

3. if the gcd != 1 then we found a factor of N

4. If not then run the quantum circuit that uses a Quantum Fourier Transform

5. If the period is odd then go back to step 1

6. Otherwise we have found the factors of N

# Implementation

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/

# Code

``````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()``````

# Output Output for the code above showing the factors 3 and 7 for N=21.

Want to learn about Quantum Programming? Head over to Quantum Computing UK: https://quantumcomputinguk.org/