Quantum Computing: A Mathematical Analysis of Shor's Algorithm

Gaurav Raj, Dheerendra Singh, Abhishek Madaan

Marcus Ahlström, Peda Dizdarevic, Patrik Henelius

In 1994, Peter Shor presented an algorithm for integer factorization that used exponentiallyless operations than the most efficient known algorithm. His algorithm requiresthe use of a quantum computer, a theoretical computational device using quantum mechanicaleffects not utilized in contemporary computers. In this paper we have analysedthe 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’sAlgorithm. Furthermore we have written a program in C++ to simulate a quantum circuitperforming Shor’s algorithm and the quantum Fourier transform. We were able tounderstand the critical parts of Shor’s algorithm that contribute with the great increasein efficiency compared to classical algorithms.

Matt W. Hayward

Chenxuan Wang

The unique principles of quantum physics introduce an element of uncertainty into our previously deterministic world. Quantum computing, derived from quantum physics, enables the representation of a qubit in both |0> and |1> states, thus encoding more information and unleashing a realm of new possibilities. This paper conducts an analysis of the classical RSA encryption protocol and its vulnerability to the quantum algorithm—Shor's algorithm. Furthermore, this paper rigorously establishes the mathematical theories required for the analysis. Finally, the algorithm is thoroughly explored, and the potential efficiencies of quantum computing are discussed. As the study of quantum computing deepens, its application is poised to surpass that of traditional computers in various fields, leaving a profound impact.

Océane Koska, Arnaud Gazda, Maxime Remaud

Anil Kumar Malviya, Lokendra Singh Umrao Vibhooti Singh

Quantum computing has emerged as an important interdisciplinary field, merging theories in mathematics, physics and computer science. So far, a significant portion of research in quantum computing has focused on the design of quantum algorithms. Quantum Com-puters requires very different algorithms for factorization, which plays an important role in the field of quantum computing and shor’s algo-rithm is used to address integer factorization problem. Shor's algorithm is important because it breaks a widely used public-key cryptography scheme known as RSA. This paper discusses the refinement of quantum factorization algorithm. Keywords: - quantum algorithm, factorization, gcd, prime decomposition, shor’s algorithm.