# 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 normal 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 IBMQfrom qiskit.aqua import QuantumInstancefrom qiskit.aqua.algorithms import ShorIBMQ.enable_account('ENTER API TOKEN HERE') # Enter your API token hereprovider = IBMQ.get_provider(hub='ibm-q')backend = provider.get_backend('ibmq_qasm_simulator') # Specifies the quantum deviceprint('\n Shors Algorithm')print('--------------------')print('\nExecuting...\n')factors = Shor(21) #Function to run Shor's algorithm where 21 is the integer to be factoredresult_dict = factors.run(QuantumInstance(backend, shots=1, skip_qobj_validation=False))result = result_dict['factors'] # Get factors from resultsprint(result)print('\nPress any key to close')input()`

# Output

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

--

--

## More from Macauley Coggins

Developer, Author, and founder of Quantum Computing UK which aims to teach people about quantum computing

Love podcasts or audiobooks? Learn on the go with our new app.

## Macauley Coggins

15 Followers

Developer, Author, and founder of Quantum Computing UK which aims to teach people about quantum computing