Skip to content

Description and implementation of the Shor's algorithm (to solve the prime factorization problem) using the IBM SDK Qiskit and the framework ProjectQ.

License

Notifications You must be signed in to change notification settings

mett29/Shor-s-Algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

  • Complexity on classical computer: classical_complexity

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.

References and resources

About

Description and implementation of the Shor's algorithm (to solve the prime factorization problem) using the IBM SDK Qiskit and the framework ProjectQ.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published