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/0404060

A quantum Fourier transform algorithm

Chris Lomont

Published Apr 9, 2004• 3 citations
arXivHTMLPDF

Abstract

Algorithms to compute the quantum Fourier transform over a cyclic group are fundamental to many quantum algorithms. This paper describes such an algorithm and gives a proof of its correctness, tightening some claimed performance bounds given earlier. Exact bounds are given for the number of qubits needed to achieve a desired tolerance, allowing simulation of the algorithm.

DOI
10.48550/arxiv.quant-ph/0404060

Related papers

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

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

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

Quantum hashing and Fourier transform

Farid Mansurovich Ablayev, Alexander Vasiliev

In the paper based on the notion of small-biased sets we define the quantum transformation that describes the quantum hash function over the cyclic group. We discuss its similarity to the well-known Quantum Fourier Transform and show possible applications to constructing space-efficient algorithms in various computational scenarios, including two-party quantum communication model, simultaneous message passing model, and the model of quantum online streaming algorithms.

Journal of Physics Conference Series•Dec 1, 2020•4 citations

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•1 citation

Efficient Quantum Transforms

Peter Høyer

Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.

arXiv:quant-ph/9702028•Feb 12, 1997•149 citations
Algorithms to compute the quantum Fourier transform over a cyclic group are fundamental to many quantum algorithms. This paper describes such an algorithm and gives a proof of its correctness, tightening some claimed performance bounds given earlier. Exact bounds are given for the number of qubits needed to achieve a desired tolerance, allowing simulation of the algorithm.
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.
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 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.
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.
Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.