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:2608.28573

Quantum Fourier transform toolbox

Carli Bruinsma, Pietro M. Posta, Joppe Stokvis, Dmitry Grinko, Maris Ozols

quant-phmath.RTSubmitted Aug 28, 2026• Announced Aug 31, 2026• 0 citations• Revised Sep 30, 2026 (v2)
v1 · Aug 28, 2026v2 · Sep 30, 2026
arXivHTMLPDF

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.

Related papers

Highly-efficient quantum Fourier transformations for some nonabelian groups

Murairi, Edison M., M. Sohaib Alam, Henry Lamm +2 more

Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard abelian QFT is well-studied, important variants corresponding to \emph{nonabelian} groups of interest have seen less development. In particular, fast nonabelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the nonabelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics, $\mathbb{BT}$, $\mathbb{BO}$, $Δ(27)$, $Δ(54)$, and $Σ(36\times3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by up to three orders of magnitude for the finite groups that we have investigated.

arXiv:2408.00075•Jul 31, 2024•0 citations

Highly-efficient quantum Fourier transformations for certain non-Abelian groups

Edison M. Murairi, M. Sohaib Alam, Henry Lamm +2 more

Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard Abelian QFrT is well studied, important variants corresponding to non-Abelian groups of interest have seen less development. In particular, fast non-Abelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the non-Abelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of non-Abelian groups of interest for high energy physics, $\mathbb{B}\mathbb{T}$, $\mathbb{B}\mathbb{O}$, $6\mathrm{\ensuremath{\Delta}}(27)$, $\mathrm{\ensuremath{\Delta}}(54)$, and $\mathrm{\ensuremath{\Sigma}}(36\ifmmode\times\else\texttimes\fi{}3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by an up to three orders of magnitude for the finite groups that we have investigated.

Physical review. D/Physical review. D.•Oct 1, 2024•14 citations

Quantum Fourier transform for the symmetric group

Carli Bruinsma, Dmitry Grinko, Maris Ozols

Quantum Fourier transforms (QFT) for general groups were recognized to be fundamental already early in the field. A canonical example of non-abelian QFT for the symmetric group was outlined by Beals (1997). Later, a more detailed analysis of this algorithm was carried out by Kawano and Sekigawa (2016). In this paper, we revisit that construction. After a careful analysis, we revise their gate complexity to $\widetilde{\mathcal{O}}(n^{3.5})$ and circuit depth to $\widetilde{\mathcal{O}}(n^3)$. Moreover, we observe that their construction is not optimal in the choice of transversal elements, so we propose simpler realization of the symmetric group QFT.

quant-pharXiv:2608.28569•Aug 31, 2026•0 citations

Approximate quantum Fourier transform with O(n log(n)) T gates

Yunseong Nam, Yuan Su, Dmitri A Maslov

Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of $$O(n\,{\mathrm{log}}^{2}\,(n))$$ O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of $$O(n\,{\mathrm{log}}\,(n))$$ O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

arXiv:1803.04933•npj Quantum Information•Mar 13, 2020•93 citations

Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?

Keisuke Fujii

A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in $\mathrm{NP}\cap\mathrm{BQP}$ and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at $k=1$, recovering the repetition number contains finite-field discrete logarithm over $\mathbb{F}_{2^r}^{\times}$. In general, restricting every exponent to $\{0,1\}$ removes the Abelian-group closure and makes feasibility NP-complete for variable $k$, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.

quant-pharXiv:2609.35239•Sep 29, 2026•0 citations

Normalizer Circuits and Quantum Computation

Juan Bermejo-Vega

(Abridged abstract.) In this thesis we introduce new models of quantum computation to study the emergence of quantum speed-up in quantum computer algorithms. Our first contribution is a formalism of restricted quantum operations, named normalizer circuit formalism, based on algebraic extensions of the qubit Clifford gates (CNOT, Hadamard and $π/4$-phase gates): a normalizer circuit consists of quantum Fourier transforms (QFTs), automorphism gates and quadratic phase gates associated to a set $G$, which is either an abelian group or abelian hypergroup. Though Clifford circuits are efficiently classically simulable, we show that normalizer circuit models encompass Shor's celebrated factoring algorithm and the quantum algorithms for abelian Hidden Subgroup Problems. We develop classical-simulation techniques to characterize under which scenarios normalizer circuits provide quantum speed-ups. Finally, we devise new quantum algorithms for finding hidden hyperstructures. The results offer new insights into the source of quantum speed-ups for several algebraic problems. Our second contribution is an algebraic (group- and hypergroup-theoretic) framework for describing quantum many-body states and classically simulating quantum circuits. Our framework extends Gottesman's Pauli Stabilizer Formalism (PSF), wherein quantum states are written as joint eigenspaces of stabilizer groups of commuting Pauli operators: while the PSF is valid for qubit/qudit systems, our formalism can be applied to discrete- and continuous-variable systems, hybrid settings, and anyonic systems. These results enlarge the known families of quantum processes that can be efficiently classically simulated. This thesis also establishes a precise connection between Shor's quantum algorithm and the stabilizer formalism, revealing a common mathematical structure in several quantum speed-ups and error-correcting codes.

arXiv:1611.09274•Nov 28, 2016•3 citations
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)\mathrm{GL}_2(F_q)GL2​(Fq​) that scale polynomially in log⁡q\log qlogq, rather than polynomially in qqq. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products F≀SnF\wr S_nF≀Sn​, whose cost depends on the cost of a QFT over FFF and the size of its representation registers. This removes the restriction ∣F∣=poly⁡(n)|F|=\operatorname{poly}(n)∣F∣=poly(n) required by previous generic constructions and can yield exponential improvements when FFF itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard abelian QFT is well-studied, important variants corresponding to \emph{nonabelian} groups of interest have seen less development. In particular, fast nonabelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the nonabelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics, BT\mathbb{BT}BT, BO\mathbb{BO}BO, Δ(27)Δ(27)Δ(27), Δ(54)Δ(54)Δ(54), and Σ(36×3)Σ(36\times3)Σ(36×3). For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by up to three orders of magnitude for the finite groups that we have investigated.
Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard Abelian QFrT is well studied, important variants corresponding to non-Abelian groups of interest have seen less development. In particular, fast non-Abelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the non-Abelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of non-Abelian groups of interest for high energy physics, BT\mathbb{B}\mathbb{T}BT, BO\mathbb{B}\mathbb{O}BO, $6\mathrm{\ensuremath{\Delta}}(27)$, $\mathrm{\ensuremath{\Delta}}(54)$, and $\mathrm{\ensuremath{\Sigma}}(36\ifmmode\times\else\texttimes\fi{}3)$. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by an up to three orders of magnitude for the finite groups that we have investigated.
Quantum Fourier transforms (QFT) for general groups were recognized to be fundamental already early in the field. A canonical example of non-abelian QFT for the symmetric group was outlined by Beals (1997). Later, a more detailed analysis of this algorithm was carried out by Kawano and Sekigawa (2016). In this paper, we revisit that construction. After a careful analysis, we revise their gate complexity to O~(n3.5)\widetilde{\mathcal{O}}(n^{3.5})O(n3.5) and circuit depth to O~(n3)\widetilde{\mathcal{O}}(n^3)O(n3). Moreover, we observe that their construction is not optimal in the choice of transversal elements, so we propose simpler realization of the symmetric group QFT.
Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of O(n log2 (n))O(n\,{\mathrm{log}}^{2}\,(n))O(nlog2(n)) O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of O(n log (n))O(n\,{\mathrm{log}}\,(n))O(nlog(n)) O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.
A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in NP∩BQP\mathrm{NP}\cap\mathrm{BQP}NP∩BQP and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at k=1k=1k=1, recovering the repetition number contains finite-field discrete logarithm over F2r×\mathbb{F}_{2^r}^{\times}F2r×​. In general, restricting every exponent to {0,1}\{0,1\}{0,1} removes the Abelian-group closure and makes feasibility NP-complete for variable kkk, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.
(Abridged abstract.) In this thesis we introduce new models of quantum computation to study the emergence of quantum speed-up in quantum computer algorithms. Our first contribution is a formalism of restricted quantum operations, named normalizer circuit formalism, based on algebraic extensions of the qubit Clifford gates (CNOT, Hadamard and π/4π/4π/4-phase gates): a normalizer circuit consists of quantum Fourier transforms (QFTs), automorphism gates and quadratic phase gates associated to a set GGG, which is either an abelian group or abelian hypergroup. Though Clifford circuits are efficiently classically simulable, we show that normalizer circuit models encompass Shor's celebrated factoring algorithm and the quantum algorithms for abelian Hidden Subgroup Problems. We develop classical-simulation techniques to characterize under which scenarios normalizer circuits provide quantum speed-ups. Finally, we devise new quantum algorithms for finding hidden hyperstructures. The results offer new insights into the source of quantum speed-ups for several algebraic problems. Our second contribution is an algebraic (group- and hypergroup-theoretic) framework for describing quantum many-body states and classically simulating quantum circuits. Our framework extends Gottesman's Pauli Stabilizer Formalism (PSF), wherein quantum states are written as joint eigenspaces of stabilizer groups of commuting Pauli operators: while the PSF is valid for qubit/qudit systems, our formalism can be applied to discrete- and continuous-variable systems, hybrid settings, and anyonic systems. These results enlarge the known families of quantum processes that can be efficiently classically simulated. This thesis also establishes a precise connection between Shor's quantum algorithm and the stabilizer formalism, revealing a common mathematical structure in several quantum speed-ups and error-correcting codes.