Mathematical Analysis and Simulation of Shor’s Algorithm and the Quantum Fourier Transform

Abstract: In 1994, Peter Shor presented an algorithm for integer factorization that used exponentially less operations than the most efficient known algorithm. His algorithm requires the use of a quantum computer, a theoretical computational device using quantum mechanical effects not utilized in contemporary computers. In this paper we have analysed the mathematics behind Shor’s algorithm and the quantum circuits on which it operates. We have also studied the Quantum Fourier Transform, a central component of Shor’s Algorithm. Furthermore we have written a program in C++ to simulate a quantum circuit performing Shor’s algorithm and the quantum Fourier transform. We were able to understand the critical parts of Shor’s algorithm that contribute with the great increase in efficiency compared to classical algorithms.