Efficient Quantum Fourier Transforms For Semisimple Algebras
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 Pn(d), Brauer algebra Bn(d), and walled Brauer algebra 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 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 poly(n,log d,log(1/ε)) for approximating the Fourier transform to error (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.
Related
- Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms
- Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
- 𝒪(n) alternative to Quantum Fourier Transform with efficient neural net classical post-processing
- Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization
- Communication-Efficient Distributed Inverse Quantum Fourier Transform
BibTeX
@misc{foxman2026efficient,
title = {{Efficient Quantum Fourier Transforms For Semisimple Algebras}},
author = {Ben Foxman and Barak Nehoran and Yongshan Ding},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.05337},
eprint = {2605.05337},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.05337},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient Quantum Fourier Transforms For Semisimple Algebras
AU - Ben Foxman
AU - Barak Nehoran
AU - Yongshan Ding
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2605.05337
UR - https://arxiv.org/abs/2605.05337
AB - 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 poly(n,log d,log(1/ε)) for approximating the Fourier transform to error (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.
ER -