skip to main content
article

Generic quantum Fourier transforms

Published: 01 October 2006 Publication History

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 GLk(q), SLk(q), and the finite groups of Lie type, for any fixed prime power q.

References

[1]
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A 52, 3457--3467.]]
[2]
Beals, R. 1997. Quantum Computation of Fourier transforms over symmetric groups. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, TX, May 4--6). ACM, New York, 48--53.]]
[3]
Beth, T. 1987. On the computational complexity of the general discrete Fourier transform. Theoret. Comput. Sci. 51, 3, 331--339.]]
[4]
Clausen, M. 1989. Fast generalized Fourier transforms. Theoret. Comput. Sci. 67, 1, 55--63.]]
[5]
Clifford, A. 1937. Representations induced in an invariant subgroup. Ann. Math. 38, 533--550.]]
[6]
Cooley, J. W., and Tukey, J. W. 1965. An algorithm for the machine calculating of complex Fourier series. Math. Comput. 19, 297--301.]]
[7]
Coppersmith, D. 1994. An approximate Fourier transform useful in quantum factoring. Tech. Rep. RC19642, IBM. Quantum Physics e-Print Archive, quant-ph/0201067.]]
[8]
Diaconis, P., and Rockmore, D. 1990. Efficient computation of the Fourier transform on finite groups. J. Amer. Math. Soc. 3, 2, 297--332.]]
[9]
Grigni, M., Schulman, L., Vazirani, M., and Vazirani, U. 2001. Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (Hersonissos, Crete, Greece, July 6--8). ACM, New York, 68--74.]]
[10]
Hales, L., and Hallgren, S. 2000. An improved quantum Fourier transform algorithm and applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, Nov. 12--14). IEEE Computer Society Press, Silver Spring, MD, 515--525. (IEEE Computer Society Order Number PR00850.)]]
[11]
Hallgren, S., Russell, A., and Ta-Shma, A. 2000. Normal subgroup reconstruction and quantum computation using group representations. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (Portland, OR, May 21--23). ACM Press, New York, 627--635.]]
[12]
Harary, F. 1969. Graph Theory. Addison-Wesley, Reading, MA.]]
[13]
Høoyer, P. 1997. Efficient quantum transforms. Tech. Rep. quant-ph/9702028, Quantum Physics e-Print Archive.]]
[14]
Ivanyos, G., Magniez, F., and Santha, M. 2001. Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. In Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (Heraklion, Crete Island, Greece). ACM, New York, 263--270.]]
[15]
Kerber, A. 1971 and 1975. Representations of Permutation Groups I, II. Lecture Notes in Mathematics, vol. 240 and 495. Springer-Verlag, Berlin, Germany.]]
[16]
Kitaev, A. 1995. Quantum measurements and the abelian stabilizer problem. Tech. Rep. quant-ph/9511026, Quantum Physics e-Print Archive.]]
[17]
Maslen, D., and Rockmore, D. 1997. Separation of variables and the computation of Fourier transforms on finite groups, I. J. Amer. Math Soc. 10, 1, 169--214.]]
[18]
Maslen, D., and Rockmore, D. 2001. The Cooley-Tukey FFT and group theory. Notices Amer. Math. Soc. 48, 10, 1151--1160.]]
[19]
Maslen, D. K., and Rockmore, D. N. 1995. Adapted diameters and the efficient computation of Fourier transforms on finite groups. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA). ACM, New York, 253--262.]]
[20]
Moore, C., Rockmore, D., Russell, A., and Schulman, L. 2004. The value of basis selection in Fourier sampling: Hidden subgroup problems in affine groups. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 1106--1115.]]
[21]
Püschel, M., Rötteler, M., and Beth, T. 1999. Fast quantum Fourier transforms for a class of non-Abelian groups. In Proceedings of Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (AAECC-13). Lecture Notes in Computer Science, vol. 1719. Springer-Verlag, New York, 148--159.]]
[22]
Rockmore, D. 1990. Fast Fourier analysis for Abelian group extensions. Adv. Appl. Math. 11, 164--204.]]
[23]
Rockmore, D. 1995. Fast Fourier transforms for wreath products. J. Appl. Comput. Harmon. Anal. 2, 279--292.]]
[24]
Serre, J.-P. 1977. Linear Representations of Finite Groups. Springer-Verlag, New York.]]
[25]
Shor, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (Oct.), 1484--1509.]]
[26]
Simon, B. 1996. Representations of Finite and Compact Groups. Graduate Studies in Mathematics, vol. 10. American Mathematical Society.]]
[27]
Watrous, J. 2001. Quantum algorithms for solvable groups. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (Hersonissos, Crete, Greece, July 6--8). ACM, New York, 60--67.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 2, Issue 4
October 2006
233 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/1198513
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2006
Published in TALG Volume 2, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Quantum computation
  2. group theory

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)84
  • Downloads (Last 6 weeks)8
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Highly-efficient quantum Fourier transformations for certain non-Abelian groupsPhysical Review D10.1103/PhysRevD.110.074501110:7Online publication date: 1-Oct-2024
  • (2024) Primitive quantum gates for an discrete subgroup: Physical Review D10.1103/PhysRevD.110.034515110:3Online publication date: 23-Aug-2024
  • (2024) Primitive quantum gates for an discrete subgroup: Binary octahedral Physical Review D10.1103/PhysRevD.109.054503109:5Online publication date: 13-Mar-2024
  • (2024)Information compression via hidden subgroup quantum autoencodersnpj Quantum Information10.1038/s41534-024-00865-210:1Online publication date: 8-Aug-2024
  • (2024)On the Various Ways of Quantum Implementation of the Modular Exponentiation Function for Shor’s FactorizationInternational Journal of Theoretical Physics10.1007/s10773-023-05532-463:1Online publication date: 10-Jan-2024
  • (2024)Extraction of emerging trends in quantum algorithm archivesNeural Computing and Applications10.1007/s00521-024-10198-y36:29(17851-17880)Online publication date: 1-Oct-2024
  • (2022)Quantum Fourier Convolutional NetworkACM Transactions on Multimedia Computing, Communications, and Applications10.1145/351424919:1(1-14)Online publication date: 5-Jul-2022
  • (2022) Primitive quantum gates for an discrete subgroup: Binary tetrahedral Physical Review D10.1103/PhysRevD.106.114501106:11Online publication date: 8-Dec-2022
  • (2022)Primitive quantum gates for dihedral gauge theoriesPhysical Review D10.1103/PhysRevD.105.114501105:11Online publication date: 2-Jun-2022
  • (2022)Quantum algorithms for group convolution, cross-correlation, and equivariant transformationsPhysical Review A10.1103/PhysRevA.106.032402106:3Online publication date: 1-Sep-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media