Shor-s-Algorithm
Shor-s-Algorithm copied to clipboard
mett29
Description and implementation of the Shor's algorithm (to solve the prime factorization problem) using the IBM SDK Qiskit and the framework ProjectQ.
Introduction
This project was done as part of the Software Engineering 2 course at Polytechnic of Milan. The aim was to explore the field of Quantum Computing to understand its characteristics and potential. In order to accomplish this task, I and other colleagues started from the paper Quantum Algorithm Implementations for Beginners, from which each person chose an algorithm and then started its study. As you can understand, my algorithm is the Shor's algorithm.
Shor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization, formulated in 1994. Informally, it solves the following problem: Given an integer N, find its prime factors.
Disclaimer
GitHub has some issues in rendering LaTeX notation. Hopefully, everything should be understandable, otherwise use the following link to visualize the notebook:
Alternatively, just clone this repository and launch jupyter lab.
git clone https://github.com/mett29/Shor-s-Algorithm.git
Overview
Lemma: Factoring is equivalent to finding a nontrivial squareroot of 1 mod N.
Complexity:
-
Complexity on quantum computer:
-
Complexity on classical computer:
Image credits: https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm
Structure of the algorithm
Shor's algorithm consists of two parts:
1) [CLASSICAL PART] A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
2) [QUANTUM PART] A quantum algorithm to solve the order-finding problem.
mett29