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

Efficient Quantum Fourier Transforms For Semisimple Algebras

Ben Foxman, Barak Nehoran, Yongshan Ding

quant-phSubmitted May 6, 2026• Announced May 8, 2026• 1 citation• Revised Sep 28, 2026 (v2)
v1 · May 6, 2026v2 · Sep 28, 2026
arXivHTMLPDF

Abstract

The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra $P_n(d)$, Brauer algebra $B_n(d)$, and walled Brauer algebra $B_{r,s}(d)$. These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms. Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter $d$ is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras $A$ from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity $\mathrm{poly}(n,\log d,\log(1/\varepsilon))$ for approximating the Fourier transform to error $(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)$. Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.

Related papers

THEORETICAL FRAMEWORK AND ALGORITHMIC IMPLEMENTATION OF THE QUANTUM FOURIER TRANSFORM AND PHASE ESTIMATION

Medak Srinivas

The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.

Iterative International Publishers eBooks•May 1, 2026•0 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

Generic Quantum Fourier Transforms

Cristopher Moore, Daniel N. Rockmore, Alexander C. Russell

The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by ``quantizing'' the separation of variables technique that has been so successful in the study of classical Fourier transform computations. Specifically, this framework applies the existence of computable Bratteli diagrams, adapted factorizations, and Gel'fand-Tsetlin bases to offer efficient quantum circuits for the QFT over a wide variety a finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, the method gives rise to the first subexponential-size quantum circuits for the QFT over the linear groups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime power q.

arXiv:quant-ph/0304064•Apr 9, 2003•27 citations

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

Chandrima Kayal, Rajat Mittal, Manaswi Paraashar +1 more

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 $\mathbb{F}_{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 \left( q (\log q)\right)$ 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 \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^α \right)$ gates.

arXiv:2611.06341•Nov 4, 2026•0 citations

Generic quantum Fourier transforms

Cristopher Moore, Daniel N. Rockmore, Alexander C. Russell

The quantum Fourier transform (QFT) is the principal ingredient of most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly successful separation of variables technique for the construction of efficient classical Fourier transforms. Specifically, we apply the existence of computable Bratteli diagrams, adapted factorizations, and Gel’fand-Tsetlin bases to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, our method provides the first subexponentialsize quantum circuits for the QFT over the linear groups GLk(q), SLk(q), and the finite groups of Lie type, for any fixed prime power q.

•Jan 11, 2004•35 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•122 citations
The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra Pn(d)P_n(d)Pn​(d), Brauer algebra Bn(d)B_n(d)Bn​(d), and walled Brauer algebra Br,s(d)B_{r,s}(d)Br,s​(d). These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms.
Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter ddd is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras AAA from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity poly(n,log⁡d,log⁡(1/ε))\mathrm{poly}(n,\log d,\log(1/\varepsilon))poly(n,logd,log(1/ε)) for approximating the Fourier transform to error (d−1/2+ε)⋅poly(∣A∣)(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)(d−1/2+ε)⋅poly(∣A∣). Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.
The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.
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.
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by ``quantizing'' the separation of variables technique that has been so successful in the study of classical Fourier transform computations. Specifically, this framework applies the existence of computable Bratteli diagrams, adapted factorizations, and Gel'fand-Tsetlin bases to offer efficient quantum circuits for the QFT over a wide variety a finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, the method gives rise to the first subexponential-size quantum circuits for the QFT over the linear groups GL_k(q), SL_k(q), and the finite groups of Lie type, for any fixed prime power q.
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)O(q^2)O(q2) gates (and O(q)O(q)O(q) qubits) to perform the exact Fourier transform over F2q\mathbb{F}_{2^q}F2q​. Cleve and Watrous (FOCS 2000) improved this gate count to O(q(log⁡q)2(log⁡log⁡q))O(q (\log q)^2 (\log \log q))O(q(logq)2(loglogq)) using the integer multiplication algorithm in O(n(log⁡n)(log⁡log⁡n))O(n (\log n) (\log \log n))O(n(logn)(loglogn)) time for two nnn-bit integers (best known at that time). Our first main result shows that this gate count can be improved to O(q(log⁡q))O(q (\log q))O(q(logq)). In fact, if there is a multiplication circuit, to multiply two nnn-bit integers, with O(n(log⁡n)α)O(n (\log n)^α)O(n(logn)α) gates; we get a QFT circuit with O(q(log⁡q)α)O(q (\log q)^α)O(q(logq)α) gates (improving upon O(q(log⁡q)α+1)O(q (\log q)^{α+ 1})O(q(logq)α+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))o \left( q (\log q)\right)o(q(logq)) 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)O \left( q (\log \log(q/\varepsilon))^{α+1} \right)O(q(loglog(q/ε))α+1) gates, where εεε is the approximating parameter. Our second main result again improves this to O(q(log⁡log⁡(q/ε))α)O \left( q (\log \log(q/\varepsilon))^α \right)O(q(loglog(q/ε))α) gates.
The quantum Fourier transform (QFT) is the principal ingredient of most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly successful separation of variables technique for the construction of efficient classical Fourier transforms. Specifically, we apply the existence of computable Bratteli diagrams, adapted factorizations, and Gel’fand-Tsetlin bases to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all group families for which efficient QFTs are currently known and many new group families. Moreover, our method provides the first subexponentialsize quantum circuits for the QFT over the linear groups GLk(q), SLk(q), and the finite groups of Lie type, for any fixed prime power q.
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.