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.
This is instead the link to the common repository, grouping all the algorithms: repo
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 sometimes some issues in rendering LaTeX notation. Hopefully, everything should be understandable, otherwise use the following link to visualize the notebook (note however that nbviewer does not show some images):
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.