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, 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.
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
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
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.