International Conference on Computer Engineering, Information Science & Application Technology (ICCIA)

Quantum Fourier Transform and Its Application in Shor’s Algorithm

Zhongwei Wang, Xirui Gou, Ruiqing Fu, Zhixuan Fu

Published Jan 1, 2020• 0 citations

Abstract

Quantum Fourier transform (QFT) plays an eminent role in quantum computation.It creates a superposition of different quantum states, allowing simultaneous calculation, which would take many steps were the same program implemented on a classical computer.The computational speed of a quantum computer is thus boosted dramatically.In this article, we explain the application of QFT in Shor's algorithm, which was proposed by Peter Shor to factor large integers on quantum computers.Specifically, the principle and design of quantum Fourier transform are explained.We stress the subtle distinction between QFT and its inverse.Since former articles did not emphasize it, we hope it could be a supplement to former articles.Our next work is to verify the existing articles on executing Shor's algorithm by conducting two experiments on IBMQ of factoring N = 15 in two ways (a = 7 and a = 11).We find that the effect of quantum entanglement might be crucial to the speed boost of factoring large integers in Shor's algorithm.

DOI: 10.23977/iccia2020047

Related papers

A review on quantum Fourier transform

Tomás Barros, Pablo Álvarez, Bárbara Vidal +1 more

This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.

Quantum Information ProcessingJan 27, 20262 citations

Deconstructing Shor’s Algorithm Using Quantum Fourier Transform

Dushyant Kumar, Balwinder Raj, Gurmohan Singh

Shor's algorithm proved a significant milestone in quantum computing since it promises an exponential speedup over conventional algorithms for integer factorization, a problem critical to modern cryptography systems. This work covers implementation steps of Shor’s algorithm and analyzes Quantum Fourier Transform (QFT) usage for extracting periodicity from quantum superpositions. Firstly, theoretical foundations of algorithm are illustrated concentrating on QFT construction and operation within the setting of the quantum circuit. Thereafter, each implementation step such as qubit optimization, modular exponentiation, and circuit design is discussed. Our findings validate the theoretical effectiveness of the QFT in solving the period-finding subroutine, while also highlighting the practical difficulties and scaling constraints presented by existing quantum hardware. The paper ends with a summary of possible advancements and future paths for error mitigation strategies and quantum algorithm design.

Indian Journal of Pure & Applied PhysicsJan 1, 20260 citations

Simulation of a Quantum Prime Factoring Algorithm

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.

Jan 1, 20160 citations

News

The fast Fourier transform (FFT) is the unsung digital workhorse of modern life.It's a clever mathematical shortcut that makes possible the many signals in our device-connected world.Every minute of every video stream, for instance, entails computing some hundreds of FFTs.The FFT's importance to practically every data-processing application in the digital age explains why some researchers have begun exploring how quantum computing can run the FFT algorithm more efficiently still."The fast Fourier transform is an important algorithm that's had lots of applications in the classical world," says Ian Walmsley, physicist at Imperial College London."It also has many applications in the quantum domain.[So] it's important to figure out effective ways to be able to implement it."The first proposed killer app for quantum computers-finding a number's prime factors-was discovered by mathematician Peter Shor at AT&T Bell Laboratories in 1994.Shor's algorithm scales up its factorization of numbers more efficiently and rapidly than any classical computer anyone could ever design.And at the heart of Shor's phenomenal quantum engine is a subroutine called-you guessed it-the quantum Fourier transform (QFT).Here is where the terminology gets a little out of hand.There is the QFT at the center of Shor's algorithm, and then there is the QFFT-the quantum fast Fourier transform.They represent different calculations that produce different results, although both are based on the same core mathematical concept, known as the discrete Fourier transform.

IEEE SpectrumDec 30, 20200 citations

Implementation of 5-Qubit approach-based Shor's Algorithm in IBM Qiskit

G. R. Mounica, G. Manimaran, Lauret Jerome +1 more

RSA cryptography is a principle part in today's cyber-security frameworks, which intensely depends on the diffi-culty of factorizing large integers. Finding a factor of large prime number is not a small feature compared to the time complexity for computation on a classical computer is far beyond comprehension. Back in 1994, Peter Shor proposed a quantum algorithm to factorize integers much more efficiently than a classical computer. This can effectively break asymmetric cryptosystems such as RSA or Diffie-Hellman, depicted as the most famous quantum algorithm. It leverages the efficacy proclaimed by quantum bits and clearly shows how quantum computers can outperform classical ones in specific tasks. In this paper, we show how Shor's algorithm factorizes an integer into its two prime factors. Shor uses both classical and quantum computation to perform this task in polynomial time, using Euclidean algorithm and find the greatest common divisor (gcd) of two numbers in the classical part. Thereafter, the power of Quantum Fourier Transform (QFT) and Quantum Phase Estimation (QPE) is utilised for period-finding using quantum bits. We have implemented this algorithm on IBM's Quantum Lab and successfully factorized the number 15 into its prime factors as 5 and 3, by using 5 qubits. This paper provides an overview of the implementation of Shor's algorithm involving QPE, QFT, Modular Exponentiation and the corresponding individual implementations, the only prerequisite being, to know how a qubit works.

IEEE Pune Section International Conference (PuneCon)Dec 16, 202117 citations

Shor Factoring Algorithm and the Quantum Fourier Transform

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.

Jul 9, 20260 citations