Skip to content
Preprint

Quantum Fourier transform toolbox

Aug 2026 · 0 citations
Physics Mathematics

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 $\mathrm{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 $F\wr 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|=\operatorname{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.

View source

Similar papers

Preprint Aug 2026

Exact quantum splitting and the structure of finite algebras

This work gives an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles and combines R'onyai's classical structure theory with R'onyai's classical structure theory to yield the radical and the Wedderburn decomposition.

Muhammad Imran · 0 citations
Sep 2026

Ramanujan quantum expanders from the Weil representation

For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$. The construction transfers Morgenstern's Ramanujan Cayley graphs on $\operatorname{PSL}_2(\mathbb{F}_{p})$ for $p$ which is an even power of $q$, through the odd irreducible subrepresentation of the...

Siddhartha Jain · 0 citations
Preprint Aug 2026

Shor's algorithm requires Fanout

Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). In this note, we resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires th...

Lucas Gretta, M. Joshi · 0 citations
Preprint Sep 2026

Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security

A unified Fourier analytic treatment of Dinur's variable-output single-permutation construction, $\mathsf{LXoP}$, for every fixed output width, and derive its classical and quantum security bounds; for one- and two-block outputs, they give concrete quantum security bounds.

Ritam Bhaumik, Chun Guo, Xiao-Ning Guo et al. · 0 citations
Preprint Sep 2026

Improved Quantum Algorithms for Black-Box Abelian Group Decomposition

Decomposing finite Abelian black-box groups into cyclic factors is a basic problem in quantum computation. We give a quantum algorithm for decomposing finite Abelian black-box groups by adapting the quantum sampling and classical lattice-reduction method of Regev's factoring algorithm. The algorithm computes an invaria...

Jun Luo, Yi-Nan Li, François Le Gall · 0 citations
Preprint Sep 2026

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

A deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest, and a full sample--time tradeoff that interpolates between exponential and polynomial runtime is established.

Robin Kothari, Tony Metger, Ryan O'Donnell et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.