© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal 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• 65 citations

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

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•0 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•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

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•3 citations

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•0 citations

A log-depth in-place quantum Fourier transform that rarely needs ancillas

Gregory D. Kahanamoku–Meyer, John Blue, Thiago Bergamaschi +2 more

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth $O(\log (n / ε))$ for tunable error parameter $ε$, uses $n$ total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by $ε$ on all input states except an $O(ε)$-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions [arXiv:2403.18006], the optimistic QFT yields factoring circuits of nearly linear depth using only $2n + O(n/\log n)$ total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of $O(\log (n/ε))$ with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.

arXiv:2505.00701•May 1, 2025•0 citations

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.

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. .

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

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.

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth

O(\log (n / ε))

for tunable error parameter

ε

, uses

n

total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by

ε

on all input states except an

O(ε)

-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions [arXiv:2403.18006], the optimistic QFT yields factoring circuits of nearly linear depth using only

2n + O(n/\log n)

total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of

O(\log (n/ε))

with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.