Generic Quantum Fourier Transforms
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- The Cooley-Tukey FFT and Group Theory2004
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem2001
- Quantum algorithms for solvable groups2001
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Separation of variables and the computation of Fourier transforms on finite groups, IJournal of the American Mathematical Society, 1997
- Fast Fourier Transforms for Wreath ProductsApplied and Computational Harmonic Analysis, 1995
- Fast Fourier analysis for abelian group extensionsAdvances in Applied Mathematics, 1990
- On the computational complexity of the general discrete fourier transformTheoretical Computer Science, 1987
- Representations Induced in an Invariant SubgroupAnnals of Mathematics, 1937