Quantum Fourier Transform and Shor’s Factoring Algorithm

Alice Flarend, Robert Hilborn

Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.

Rafael Pereira da Silva

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.

Manisha J. Nene, Gaurav K. Upadhyay

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Elizabeth Ellen Parsons

The intent of this thesis is to elucidate the quantum computing algorithm developed by Peter Shor called Shor's algorithm. We will provide a detailed description and simulation of the algorithm using MATLAB. Precursory information regarding quantum phenomena such as superposition, entanglement, and Dirac notation, will be described in great detail so that the reader may have a better understanding of the operations in Shor's algorithm. Quantum computers store and transport information quite differently than their classical counterparts. We will provide a quick overview of these differences to high- light the benefit of utilizing quantum phenomena in a computer in order to create massive parallel computations. Thus, reducing the complexity time for classical algorithms used to solve problems such as the prime factorization problem and the period finding problem. The Quantum Fourier Transform is a principle component in Shor's algorithm. We will explicitly define the Quantum Fourier Transform and show that it is a unitary transformation. We will also show how the Quantum Fourier Transform, as well as another unitary transformation called the Hadamard transform, functions in Shor's algorithm. One of the initial parameters in Shor's algorithm is to select a random variable. We will examine the erratic effects of this random variable as well as how it effects the probability of us successfully reducing an integer into a product of two primes. We will provide a thorough analysis of the randomness in Shor's algorithm. We will also show how measuring the state of our quantum system as well as selecting a suitable random variable impacts finding the period of the Quantum Fourier Transform which in turn will either give a high or low probability of obtaining a factor of some integer.