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

ACM communications in computer algebra

Quantum Fourier Transform over Symmetric Groups

Yasuhito Kawano, Hiroshi Sekigawa

Published Feb 5, 2015• 2 citations
Publisher

Abstract

This paper improves the main result in our paper "Quantum Fourier Transform over Symmetric Groups, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 227--234, Northeastern University, Boston, USA (June 26-29, 2013)." In that paper, we presented an O(n4) quantum Fourier transform (QFT) algorithm over symmetric group Sn, which was faster than the existing algorithm. This paper proposes an O(n3 log n) QFT algorithm over Sn by relieving bottlenecks of our previous algorithm.

DOI
10.1145/2733693.2733708

Related papers

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

Quantum fourier transform over symmetric groups

Yasuhito Kawano, Hiroshi Sekigawa

This paper proposes an O(n4) quantum Fourier transform (QFT) algorithm over symmetric group Sn, the fastest QFT algorithm of its kind. We propose a fast Fourier transform algorithm over symmetric group Sn, which consists of O(n3) multiplications of unitary matrices, and then transform it into a quantum circuit form. The QFT algorithm can be applied to constructing the standard algorithm of the hidden subgroup problem.

International Symposium on Symbolic and Algebraic Computation•Jun 25, 2013•4 citations

Efficient Quantum Fourier Transforms For Semisimple Algebras

Ben Foxman, Barak Nehoran, Yongshan Ding

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.

quant-pharXiv:2605.05337•May 8, 2026•0 citations

Quantum Fourier transform toolbox

Carli Bruinsma, Pietro M. Posta, Joppe Stokvis +2 more

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.

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

A Faster Quantum Fourier Transform

Shah, Ronit

We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in $Θ(n \log n)$ gates, and the exact in $Θ(n^2)$ gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an $Θ(n(\log \log n)^2)$ algorithm for the approximate QFT using $Θ(\log n)$ ancillas, and an $Θ(n(\log n)^2)$ algorithm for the exact QFT requiring $Θ(n)$ ancillas.

arXiv:2501.12414•Jan 19, 2025•0 citations

An efficient high dimensional quantum Schur transform

Hari Krovi

The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an n fold tensor product V ⊗ n of a vector space V of dimension d . Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in n , d and log ⁡ ϵ − 1 , where ϵ is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in log ⁡ d is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in n , log ⁡ d and log ⁡ ϵ − 1 using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called permutation modules , which could have other applications.

arXiv:1804.00055•Quantum•Feb 14, 2019•42 citations
This paper improves the main result in our paper "Quantum Fourier Transform over Symmetric Groups, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 227--234, Northeastern University, Boston, USA (June 26-29, 2013)." In that paper, we presented an O(n4) quantum Fourier transform (QFT) algorithm over symmetric group Sn, which was faster than the existing algorithm. This paper proposes an O(n3 log n) QFT algorithm over Sn by relieving bottlenecks of our previous algorithm.
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.
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.
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.
We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in Θ(nlog⁡n)Θ(n \log n)Θ(nlogn) gates, and the exact in Θ(n2)Θ(n^2)Θ(n2) gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an Θ(n(log⁡log⁡n)2)Θ(n(\log \log n)^2)Θ(n(loglogn)2) algorithm for the approximate QFT using Θ(log⁡n)Θ(\log n)Θ(logn) ancillas, and an Θ(n(log⁡n)2)Θ(n(\log n)^2)Θ(n(logn)2) algorithm for the exact QFT requiring Θ(n)Θ(n)Θ(n) ancillas.
The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an n fold tensor product V ⊗ n of a vector space V of dimension d . Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in n , d and log ⁡ ϵ − 1 , where ϵ is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in log ⁡ d is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in n , log ⁡ d and log ⁡ ϵ − 1 using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called permutation modules , which could have other applications.