arXiv:2608.28569

Quantum Fourier transform for the symmetric group

Carli Bruinsma, Dmitry Grinko, Maris Ozols

quant-phmath.RTSubmitted Aug 28, 2026• Announced Aug 31, 2026• 0 citations• Revised Sep 17, 2026 (v2)

Abstract

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.

Related papers

Efficient Quantum Fourier Transforms For Semisimple Algebras

Ben Foxman, Barak Nehoran, Yongshan Ding

quant-pharXiv:2605.05337May 8, 20260 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 ComputationJun 25, 20134 citations

An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group

Dikshant Rathore, Leo Zhou

quant-pharXiv:2610.05752Oct 6, 20260 citations

Quantum Fourier transform toolbox

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

quant-pharXiv:2608.28573Aug 31, 20260 citations

Quantum Fourier Transform over Symmetric Groups

Yasuhito Kawano, Hiroshi Sekigawa

ACM communications in computer algebraFeb 5, 20152 citations

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

Yunseong Nam, Yuan Su, Dmitri A Maslov

arXiv:1803.04933npj Quantum InformationMar 13, 202093 citations

arXiv:2608.28569

Quantum Fourier transform for the symmetric group

Carli Bruinsma, Dmitry Grinko, Maris Ozols

quant-phmath.RTSubmitted Aug 28, 2026• Announced Aug 31, 2026• 0 citations• Revised Sep 17, 2026 (v2)

arXiv HTML PDF

Abstract

\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.

Related papers

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.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.05337May 8, 20260 citations

Quantum fourier transform over symmetric groups

Yasuhito Kawano, Hiroshi Sekigawa

International Symposium on Symbolic and Algebraic ComputationJun 25, 20134 citations

An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group

Dikshant Rathore, Leo Zhou

Consider a quantum state vector proportional to any given column of the character table of the symmetric group ( $S_n$ ), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assumptions, while there exists an efficient quantum algorithm for preparing this character state using the quantum Fourier transform (QFT) over $S_n$ [arXiv:2501.12579]. We give an alternative, simpler algorithm to prepare this character state with a sequence of Hamiltonian evolutions, as well as an efficient implementation with reconfigurable qubits that uses only nearest-neighbor gates in 1D. The gate complexity, accounting for Hamiltonian simulation errors, depends on the choice of the column: For fixed target state error, the estimated sufficient total gate count ranges from as few as $O(n)$ gates for the $n$ -cycle column, to $\widetilde O(n^{1.75})$ gates near the conjecturally classically hard parameter regime, to provably $\widetilde O(n^{2.5})$ gates in the worst case. In contrast, the QFT subroutine in the prior approach uses $\widetilde O(n^3)$ gates. Our gate count estimates come from leading-order state-dependent Trotter error analysis, and the proven worst-case bound relies on a QSVT-based Hamiltonian simulation method; numerical benchmarks of the Trotter-based protocol suggest that the estimates are conservative. Furthermore, we generalize our protocol to give an explicit algorithm for the quantum character transform (QCT) over $S_n$ using $\widetilde O(n^{2.5})$ gates and $O(n)$ qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.Consider a quantum state vector proportional to any given column of the character table of the symmetric group ($S_n$), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assumptions, while there exists an efficient quantum algorithm for preparing this character state using the quantum Fourier transform (QFT) over $S_n$ [arXiv:2501.12579]. We give an alternative, simpler algorithm to prepare this character state with a sequence of Hamiltonian evolutions, as well as an efficient implementation with reconfigurable qubits that uses only nearest-neighbor gates in 1D. The gate complexity, accounting for Hamiltonian simulation errors, depends on the choice of the column: For fixed target state error, the estimated sufficient total gate count ranges from as few as $O(n)$ gates for the $n$-cycle column, to $\widetilde O(n^{1.75})$ gates near the conjecturally classically hard parameter regime, to provably $\widetilde O(n^{2.5})$ gates in the worst case. In contrast, the QFT subroutine in the prior approach uses $\widetilde O(n^3)$ gates. Our gate count estimates come from leading-order state-dependent Trotter error analysis, and the proven worst-case bound relies on a QSVT-based Hamiltonian simulation method; numerical benchmarks of the Trotter-based protocol suggest that the estimates are conservative. Furthermore, we generalize our protocol to give an explicit algorithm for the quantum character transform (QCT) over $S_n$ using $\widetilde O(n^{2.5})$ gates and $O(n)$ qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.

quant-pharXiv:2610.05752Oct 6, 20260 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.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.28573Aug 31, 20260 citations

Quantum Fourier Transform over Symmetric Groups

Yasuhito Kawano, Hiroshi Sekigawa

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.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.

ACM communications in computer algebraFeb 5, 20152 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.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.04933npj Quantum InformationMar 13, 202093 citations

\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.

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.

Consider a quantum state vector proportional to any given column of the character table of the symmetric group (

S_n

), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assumptions, while there exists an efficient quantum algorithm for preparing this character state using the quantum Fourier transform (QFT) over

S_n

[arXiv:2501.12579]. We give an alternative, simpler algorithm to prepare this character state with a sequence of Hamiltonian evolutions, as well as an efficient implementation with reconfigurable qubits that uses only nearest-neighbor gates in 1D. The gate complexity, accounting for Hamiltonian simulation errors, depends on the choice of the column: For fixed target state error, the estimated sufficient total gate count ranges from as few as

O(n)

gates for the

n

-cycle column, to

\widetilde O(n^{1.75})

gates near the conjecturally classically hard parameter regime, to provably

\widetilde O(n^{2.5})

gates in the worst case. In contrast, the QFT subroutine in the prior approach uses

\widetilde O(n^3)

gates. Our gate count estimates come from leading-order state-dependent Trotter error analysis, and the proven worst-case bound relies on a QSVT-based Hamiltonian simulation method; numerical benchmarks of the Trotter-based protocol suggest that the estimates are conservative. Furthermore, we generalize our protocol to give an explicit algorithm for the quantum character transform (QCT) over

S_n

using

\widetilde O(n^{2.5})

gates and

O(n)

qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.

\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.

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.