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

arXiv:quant-ph/0301093 · International Journal of Quantum Information

EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS

Michele Mosca, Christof Zalka

Published Mar 1, 2004• 75 citations
arXivHTMLPDF

Abstract

We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2n to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev1 showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as "amplitude amplification". Although unlikely to be of any practical use, this construction allows one to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that "quantum" need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely, the parameters of the gates can be approximated efficiently.

DOI
10.1142/s0219749904000109

Related papers

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

Chandrima Kayal, Rajat Mittal, Manaswi Paraashar +1 more

In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs $O(q^2)$ gates (and $O(q)$ qubits) to perform the exact Fourier transform over $\mathbb{F}_{2^q}$. Cleve and Watrous (FOCS 2000) improved this gate count to $O(q (\log q)^2 (\log \log q))$ using the integer multiplication algorithm in $O(n (\log n) (\log \log n))$ time for two $n$-bit integers (best known at that time). Our first main result shows that this gate count can be improved to $O(q (\log q))$. In fact, if there is a multiplication circuit, to multiply two $n$-bit integers, with $O(n (\log n)^α)$ gates; we get a QFT circuit with $O(q (\log q)^α)$ gates (improving upon $O(q (\log q)^{α+ 1})$) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with $o \left( q (\log q)\right)$ gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with $O \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^α \right)$ gates.

arXiv:2611.06341•Nov 4, 2026•0 citations

An exact quantum order finding algorithm and its applications

Muhammad Imran

We present an efficient exact quantum algorithm for order finding problem when a multiple $m$ of the order $r$ is known. The algorithm consists of two main ingredients. The first ingredient is the exact quantum Fourier transform proposed by Mosca and Zalka in [MZ03]. The second ingredient is an amplitude amplification version of Brassard and Hoyer in [BH97] combined with some ideas from the exact discrete logarithm procedure by Mosca and Zalka in [MZ03]. As applications, we show how the algorithm derandomizes the quantum algorithm for primality testing proposed by Donis-Vela and Garcia-Escartin in [DVGE18], and serves as a subroutine of an efficient exact quantum algorithm for finding primitive elements in arbitrary finite fields. .

arXiv:2205.04240•May 6, 2022•2 citations

Fast Quantum Fourier Transforms for a Class of Non-abelian Groups

Markus Püschel, Martin Roetteler, Thomas Beth

An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.

arXiv:quant-ph/9807064•Jul 22, 1998•10 citations

Quantum Computing Discrete Logarithms with the Help of a Preprocessed State

Wim van Dam

An alternative quantum algorithm for the discrete logarithm problem is presented. The algorithm uses two quantum registers and two Fourier transforms whereas Shor's algorithm requires three registers and four Fourier transforms. A crucial ingredient of the algorithm is a quantum state that needs to be constructed before we can perform the computation. After one copy of this state is created, the algorithm can be executed arbitrarily many times.

arXiv:quant-ph/0311134•Nov 20, 2003•4 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•1 citation

A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform

Nan-Hong Kuo, Renata Wong

We propose a quantum analogue of Bluestein's algorithm (QBA) that implements an exact $N$-point Quantum Fourier Transform (QFT) for arbitrary $N$. Our construction factors the $N$-dimensional QFT unitary into three diagonal quadratic-phase gates and two standard radix-2 QFT subcircuits of size $M = 2^m$ (with $M \ge 2N - 1$). This achieves asymptotic gate complexity $O((\log N)^2)$ and uses $O(\log N)$ qubits, matching the performance of a power-of-two QFT on $m$ qubits while avoiding the need to embed into a larger Hilbert space. We validate the correctness of the algorithm through a concrete implementation in Qiskit and classical simulation, confirming that QBA produces the exact $N$-point discrete Fourier transform on arbitrary-length inputs.

quant-pharXiv:2512.15349•Physica Scripta•Dec 18, 2025•1 citation
We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2n to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev1 showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as "amplitude amplification". Although unlikely to be of any practical use, this construction allows one to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that "quantum" need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely, the parameters of the gates can be approximated efficiently.
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs O(q2)O(q^2)O(q2) gates (and O(q)O(q)O(q) qubits) to perform the exact Fourier transform over F2q\mathbb{F}_{2^q}F2q​. Cleve and Watrous (FOCS 2000) improved this gate count to O(q(log⁡q)2(log⁡log⁡q))O(q (\log q)^2 (\log \log q))O(q(logq)2(loglogq)) using the integer multiplication algorithm in O(n(log⁡n)(log⁡log⁡n))O(n (\log n) (\log \log n))O(n(logn)(loglogn)) time for two nnn-bit integers (best known at that time). Our first main result shows that this gate count can be improved to O(q(log⁡q))O(q (\log q))O(q(logq)). In fact, if there is a multiplication circuit, to multiply two nnn-bit integers, with O(n(log⁡n)α)O(n (\log n)^α)O(n(logn)α) gates; we get a QFT circuit with O(q(log⁡q)α)O(q (\log q)^α)O(q(logq)α) gates (improving upon O(q(log⁡q)α+1)O(q (\log q)^{α+ 1})O(q(logq)α+1)) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with o(q(log⁡q))o \left( q (\log q)\right)o(q(logq)) gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with O(q(log⁡log⁡(q/ε))α+1)O \left( q (\log \log(q/\varepsilon))^{α+1} \right)O(q(loglog(q/ε))α+1) gates, where εεε is the approximating parameter. Our second main result again improves this to O(q(log⁡log⁡(q/ε))α)O \left( q (\log \log(q/\varepsilon))^α \right)O(q(loglog(q/ε))α) gates.
We present an efficient exact quantum algorithm for order finding problem when a multiple mmm of the order rrr is known. The algorithm consists of two main ingredients. The first ingredient is the exact quantum Fourier transform proposed by Mosca and Zalka in [MZ03]. The second ingredient is an amplitude amplification version of Brassard and Hoyer in [BH97] combined with some ideas from the exact discrete logarithm procedure by Mosca and Zalka in [MZ03]. As applications, we show how the algorithm derandomizes the quantum algorithm for primality testing proposed by Donis-Vela and Garcia-Escartin in [DVGE18], and serves as a subroutine of an efficient exact quantum algorithm for finding primitive elements in arbitrary finite fields. .
An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.
We propose a quantum analogue of Bluestein's algorithm (QBA) that implements an exact NNN-point Quantum Fourier Transform (QFT) for arbitrary NNN. Our construction factors the NNN-dimensional QFT unitary into three diagonal quadratic-phase gates and two standard radix-2 QFT subcircuits of size M=2mM = 2^mM=2m (with M≥2N−1M \ge 2N - 1M≥2N−1). This achieves asymptotic gate complexity O((log⁡N)2)O((\log N)^2)O((logN)2) and uses O(log⁡N)O(\log N)O(logN) qubits, matching the performance of a power-of-two QFT on mmm qubits while avoiding the need to embed into a larger Hilbert space. We validate the correctness of the algorithm through a concrete implementation in Qiskit and classical simulation, confirming that QBA produces the exact NNN-point discrete Fourier transform on arbitrary-length inputs.