# Quantum Programming: **Shor’s Algorithm with Code**

# 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:

- Classical part which reduces the factorisation to a problem of finding the period of the function. This is done classically using a normal 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

# 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 ShorIBMQ.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 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/

Follow me on Linkedin: https://www.linkedin.com/in/macauley-coggins-a6887998/