Generic quantum Fourier transforms
Open Access
- 1 October 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 2 (4) , 707-723
Abstract
The quantum Fourier transform (QFT) is a principal ingredient appearing in many 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 Bratteli diagrams, Gel'fand-Tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all families of groups for which efficient QFTs are currently known and many new families as well. Moreover, our method provides 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 17 references indexed in Scilit:
- Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem2001
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Elementary gates for quantum computationPhysical Review A, 1995
- Fast Fourier Transforms for Wreath ProductsApplied and Computational Harmonic Analysis, 1995
- Fast Fourier analysis for abelian group extensionsAdvances in Applied Mathematics, 1990
- Efficient computation of the Fourier transform on finite groupsJournal of the American Mathematical Society, 1990
- Fast generalized Fourier transformsTheoretical Computer Science, 1989
- On the computational complexity of the general discrete fourier transformTheoretical Computer Science, 1987
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- Representations Induced in an Invariant SubgroupAnnals of Mathematics, 1937