Quantum Fourier transform toolbox
Abstract
Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over GL2(Fq) that scale polynomially in log q, rather than polynomially in q. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products Fwr Sn, whose cost depends on the cost of a QFT over F and the size of its representation registers. This removes the restriction |F|=poly(n) required by previous generic constructions and can yield exponential improvements when F itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
Related
- The quantum connection, Fourier-Laplace transform, and families of A∞ -categories
- Quantum Fourier transform for the symmetric group
- Contour-integral and Fourier transform based multivariable quantum eigenvalue transformation for commuting matrices
- FASS: Discrete Fourier Transform Adapters for Speech Separation With Incremental Learning
- A comparison of artificial neural networks and partial least squares modelling for the rapid detection of the microbial spoilage of beef fillets based on Fourier transform infrared spectral fingerprints
BibTeX
@misc{bruinsma2026quantum,
title = {{Quantum Fourier transform toolbox}},
author = {Carli Bruinsma and Pietro M. Posta and Joppe Stokvis and Dmitry Grinko and Maris Ozols},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.28573},
eprint = {2608.28573},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28573},
}
RIS
TY - UNPB
TI - Quantum Fourier transform toolbox
AU - Carli Bruinsma
AU - Pietro M. Posta
AU - Joppe Stokvis
AU - Dmitry Grinko
AU - Maris Ozols
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.28573
UR - https://arxiv.org/abs/2608.28573
AB - Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over GL_2(F_q) that scale polynomially in log q, rather than polynomially in q. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products Fwr S_n, whose cost depends on the cost of a QFT over F and the size of its representation registers. This removes the restriction |F|=poly(n) required by previous generic constructions and can yield exponential improvements when F itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
ER -