Shor's Algorithm is one of the algorithm which truly shows the supremacy of Quantum computers over its classical counterpart. In this project we show the speedup in the factoring using Shor's Algorithm on a quantum computer.
We construct a circuit to factor 21 using a compiled version of Shor's Algorithm and successfully factor the number using very few resources compared to the standard approach. We also show another optimal method to factor a composite number 51 using Fermat prime. Both of these methods are one of the various optimal methods which can be used to achieve factoring using very few resources on a Quantum Computer.
Chapter 1 discusses the fundamentals of linear algebra and quantum mechanics required to understand various quantum gates, measurements, state space, etc.
Chapter 2 briefly describes the need of Quantum Computers and some fundamentals of Quantum Computation like qubits and Bloch Sphere.
Chapter 3 gives a brief introduction to various Quantum gates, techniques to develop circuits and do measurements on them.
Chapter 4 builds the foundation for the project. We discuss the Quantum Fourier Transform which is the heart of Shor's Algorithm. Additionally, we also discuss the Quantum Phase Estimation and the Order Finding Algorithm which are key parts in the Shor's Algorithm. Later we derive the circuit for Shor's Algorithm and factor 15 both mathematically and using the Algorithm on a Quantum Computer.
Chapter 5 discusses about the first optimal method in which we factor 21 using Qubit Recycling Method using very few resources compared to the standard approach.
In Chapter 6 we showcase another optimal method based on Fermat primes and successfully factor 51 with fewer resources compared to the standard approach of factoring with Shor's Algorithm.