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

Lecture notes in computer science

Fast Quantum Fourier Transforms for a Class of Non-abelian Groups

Markus Püschel, Martin Rötteler, Thomas Beth

Published Jan 1, 1999• 46 citations
Publisher
DOI
10.1007/3-540-46796-3_15

Related papers

Quantum Fourier Transforms for a Class of Non-abelian Groups

Markus Püschel, Martin Roetteler, Thomas Beth

•Jul 22, 1998•1 citation

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

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.

arXiv:2408.00075•Physical review. D/Physical review. D.•Oct 1, 2024•23 citations

Quantum Fourier transform over symmetric groups — improved result

Yasuhito Kawano, Hiroshi Sekigawa

Journal of Symbolic Computation•Nov 5, 2015•20 citations

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

The Quantum Character Transform

Kagwe A. Muchane

Bastidas et al. (2025) highlighted the importance of exploiting group symmetries to reduce computational overhead and unify simulation methods across both condensed matter physics and ab initio quantum chemistry. I discuss the discrete character transform, which is the group Fourier transform restricted to $Z(\mathbb{C}[G])$, the center of the group algebra, where class functions form a commutative convolution algebra and irreducible characters are its spectral basis. The normalized character table of a non-abelian group can be obtained through a restriction operator, which means an efficient quantum character transform for any finite group with an efficient quantum Fourier transform. I give complementary quantum algorithms for class convolution based on direct class-sum block encoding and spectral implementation in the character basis, explaining their applications to symmetry-adapted many-body dynamics, molecular and spectroscopic symmetry analysis, and quantum walks, as well as characterizing the central information used in hidden-subgroup problems, including its limitations for graph isomorphism.

quant-pharXiv:2610.16827•Oct 13, 2026•0 citations
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.
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 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.
Bastidas et al. (2025) highlighted the importance of exploiting group symmetries to reduce computational overhead and unify simulation methods across both condensed matter physics and ab initio quantum chemistry. I discuss the discrete character transform, which is the group Fourier transform restricted to Z(C[G])Z(\mathbb{C}[G])Z(C[G]), the center of the group algebra, where class functions form a commutative convolution algebra and irreducible characters are its spectral basis. The normalized character table of a non-abelian group can be obtained through a restriction operator, which means an efficient quantum character transform for any finite group with an efficient quantum Fourier transform. I give complementary quantum algorithms for class convolution based on direct class-sum block encoding and spectral implementation in the character basis, explaining their applications to symmetry-adapted many-body dynamics, molecular and spectroscopic symmetry analysis, and quantum walks, as well as characterizing the central information used in hidden-subgroup problems, including its limitations for graph isomorphism.