Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
Abstract
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) gates (and O(q) qubits) to perform the exact Fourier transform over 𝔽2q. 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 ( q (log q)) gates. On approximating the QFT over ZZ/(2q 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 ) gates, where ε is the approximating parameter. Our second main result again improves this to O ( q (log log(q/ε))α ) gates.
Related
- Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms
- Efficient Quantum Fourier Transforms For Semisimple Algebras
- Super Howe duality and rigidity of hybrid Fourier transforms
- Fourier Transforms of Color Glass Condensate Multi-Wilson-Line Correlators via Filon Quadrature
- Bi-Oriented Interlaced Matrix Multiplication and an Operator Factorisation of the Quantum Harmonic Oscillator
BibTeX
@misc{kayal2026improved,
title = {{Improved Exact and Approximate Quantum Fourier Transforms from Multiplication}},
author = {Chandrima Kayal and Rajat Mittal and Manaswi Paraashar and Nitin Saurabh},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06341},
eprint = {2611.06341},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06341},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
AU - Chandrima Kayal
AU - Rajat Mittal
AU - Manaswi Paraashar
AU - Nitin Saurabh
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06341
UR - https://arxiv.org/abs/2611.06341
AB - 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 𝔽_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 ( q (log q)) 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 ) gates, where ε is the approximating parameter. Our second main result again improves this to O ( q (log log(q/ε))^α ) gates.
ER -