Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chapman & Hall/CRC eBooks

Factoring Using Quantum Computers

Kristian Gjøsteen

Published Jun 9, 2022• 0 citations
Publisher

Abstract

This chapter introduces some tools, including rational approximation and the discrete Fourier transform, and show how this could in principle be used to factor. The chapter then introduces the basic ideas of quantum computation, including the quantum Fourier transform, and shows how this could be used to factor integers if a sufficiently large quantum computer could be built.

DOI
10.1201/9781003149422-5

Related papers

Quantum Fourier Transform and Related Algorithms

Santanu Pattanayak

In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.

Apress eBooks•Jan 1, 2021•0 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, 2026•0 citations

Quantum Fourier transform

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum Fourier transform, which is an essential quantum algorithmic primitive that efficiently applies a discrete Fourier transform to the amplitudes of a quantum state. It features prominently in quantum phase estimation and Shor’s algorithm for factoring and computing discrete logarithms.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

A brief review on Quantum Computing and the Shor's Factoring Algorithm

L. Martina, Giulio Soliani

Quantum Information and Quantum Computation are rapidly evolving domains in their theoretical foundations, implementations and applications. The main scope of the present book is to give the basic ideas of this field to undergraduate students in Physics. A rigorous approach is used to provide the key concepts and methods. Many examples are discussed. To be self-contained, the principles of Quantum Mechanics are reviewed. The discussion is aimed to the specific, but paradigmatic, factorization problem of integers, dealt by the Quantum Shor’s Algorithm. Thus, notions of the Number Theory are given in the first Chapter, while the exposition of the algorithm and its implementation is reserved to the last Section.

•Jan 1, 2006•0 citations

Shor's algorithm

Nežka Rugelj

In this diploma paper we present the Shor’s algorithm for factorising numbers, which runs on quantum computers. Initially, we explain the basics of quantum computing. Afterwards, we present a general review of the Fourier and the discrete Fourier transform, from which we derive the quantum Fourier transform. In the last part, we first give a short introduction to modular arithmetics. Later on, we describe the concept of factorization that is used in Shor’s algorithm. Diploma thesis ends with a detailed review of how the algorithm works on quantum computers and a simple example.

•Jan 1, 2017•0 citations

An approximate Fourier transform useful in quantum factoring

D. Coppersmith

We define an approximate version of the Fourier transform on $2^L$ elements, which is computationally attractive in a certain setting, and which may find application to the problem of factoring integers with a quantum computer as is currently under investigation by Peter Shor. (1994 IBM Internal Report)

arXiv:quant-ph/0201067•Jan 16, 2002•344 citations
This chapter introduces some tools, including rational approximation and the discrete Fourier transform, and show how this could in principle be used to factor. The chapter then introduces the basic ideas of quantum computation, including the quantum Fourier transform, and shows how this could be used to factor integers if a sufficiently large quantum computer could be built.
In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.
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.
Quantum Information and Quantum Computation are rapidly evolving domains in their theoretical foundations, implementations and applications. The main scope of the present book is to give the basic ideas of this field to undergraduate students in Physics. A rigorous approach is used to provide the key concepts and methods. Many examples are discussed. To be self-contained, the principles of Quantum Mechanics are reviewed. The discussion is aimed to the specific, but paradigmatic, factorization problem of integers, dealt by the Quantum Shor’s Algorithm. Thus, notions of the Number Theory are given in the first Chapter, while the exposition of the algorithm and its implementation is reserved to the last Section.
In this diploma paper we present the Shor’s algorithm for factorising numbers, which runs on quantum computers. Initially, we explain the basics of quantum computing. Afterwards, we present a general review of the Fourier and the discrete Fourier transform, from which we derive the quantum Fourier transform. In the last part, we first give a short introduction to modular arithmetics. Later on, we describe the concept of factorization that is used in Shor’s algorithm. Diploma thesis ends with a detailed review of how the algorithm works on quantum computers and a simple example.
We define an approximate version of the Fourier transform on 2L2^L2L elements, which is computationally attractive in a certain setting, and which may find application to the problem of factoring integers with a quantum computer as is currently under investigation by Peter Shor. (1994 IBM Internal Report)