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

Quantum algorithms and the Fourier transform

Richard Jozsa

Published Jan 1, 1997• 149 citations
OpenAlex

Abstract

The quantum algorithms of Deutsch, Simon and Shor are described in a way which highlights their dependence on the Fourier transform. The general construction of the Fourier transform on an Abelian group is outlined and this provides a unified way of understanding the efficacy of the algorithms. Finally we describe an efficient quantum factoring algorithm based on a general formalism of Kitaev and contrast its structure to the ingredients of Shor’s algorithm.

Related papers

Quantum algorithms and the Fourier transform

Richard Jozsa

The quantum algorithms of Deutsch, Simon and Shor are described in a way which highlights their dependence on the Fourier transform. The general construction of the Fourier transform on an Abelian group is outlined and this provides a unified way of understanding the efficacy of the algorithms. Finally we describe an efficient quantum factoring algorithm based on a general formalism of Kitaev and contrast its structure to the ingredients of Shor' algorithm.

arXiv:quant-ph/9707033•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 8, 1998•128 citations

Quantum computation of Fourier transforms over symmetric groups

Robert Beals

Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1997•140 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 algorithms: entanglement–enhanced information processing

ARTUR K. EKERT, Richard Jozsa

We discuss the fundamental role of entanglement as the essential nonclassical feature providing the computational speedup in the known quantum algorithms. We review the construction of the Fourier transform on an Abelian group and the principles underlying the fast Fourier transform algorithm. We describe the implementation of the FFT algorithm for the group of integers modulo 2n in the quantum context, showing how the group–theoretic formalism leads to the standard quantum network and identifying the property of entanglement that gives rise to the exponential speedup (compared to the classical FFT). Finally we outline the use of the Fourier transform in extracting periodicities, which underlies its utility in the known quantum algorithms.

arXiv:quant-ph/9803072•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 15, 1998•215 citations

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

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.

•Jan 1, 2012•1 citation

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
The quantum algorithms of Deutsch, Simon and Shor are described in a way which highlights their dependence on the Fourier transform. The general construction of the Fourier transform on an Abelian group is outlined and this provides a unified way of understanding the efficacy of the algorithms. Finally we describe an efficient quantum factoring algorithm based on a general formalism of Kitaev and contrast its structure to the ingredients of Shor’s algorithm.
Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups.That is, at some point in the computation, the macline is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log IGI), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G.We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.
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.
We discuss the fundamental role of entanglement as the essential nonclassical feature providing the computational speedup in the known quantum algorithms. We review the construction of the Fourier transform on an Abelian group and the principles underlying the fast Fourier transform algorithm. We describe the implementation of the FFT algorithm for the group of integers modulo 2n in the quantum context, showing how the group–theoretic formalism leads to the standard quantum network and identifying the property of entanglement that gives rise to the exponential speedup (compared to the classical FFT). Finally we outline the use of the Fourier transform in extracting periodicities, which underlies its utility in the known quantum algorithms.
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.
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.