Generic quantum Fourier transforms

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.

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: Robert Beals, Quantum computation of Fourier transforms over symmetric groups, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.48-53, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258548]
• 3: T. Beth, On the computational complexity of the general discrete fourier transform, Theoretical Computer Science, v.51 n.3, p.331-339, April 1987 [doi>10.1016/0304-3975(87)90041-7]
• 4: Michael Clausen, Fast generalized Fourier transforms, Theoretical Computer Science, v.67 n.1, p.55-63, Sept. 1989 [doi>10.1016/0304-3975(89)90021-2]
• 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: Michelangelo Grigni , Leonard Schulman , Monica Vazirani , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece [doi>10.1145/380752.380769]
• 10: L. Hales , S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.515, November 12-14, 2000
• 11: Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335392]
• 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: Gábor Ivanyos , Frédéric Magniez , Miklos Santha, Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.263-270, July 2001, Crete Island, Greece [doi>10.1145/378580.378679]
• 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: David K. Maslen , Daniel N. Rockmore, Adapted diameters and the efficient computation of Fourier transforms on finite groups, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.253-262, January 22-24, 1995, San Francisco, California, United States
• 20: Cristopher Moore , Daniel Rockmore , Alexander Russell , Leonard J. Schulman, The power of basis selection in fourier sampling: hidden subgroup problems in affine groups, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: Markus Püschel , Martin Rötteler , Thomas Beth, Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.148-159, November 15-19, 1999
• 22: Daniel Rockmore, Fast Fourier analysis for abelian group extensions, Advances in Applied Mathematics, v.11 n.2, p.164-204, Jun. 1990 [doi>10.1016/0196-8858(90)90008-M]
• 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: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 26: Simon, B. 1996. Representations of Finite and Compact Groups. Graduate Studies in Mathematics, vol. 10. American Mathematical Society.
• 27: John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece [doi>10.1145/380752.380759]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
Quantum computation, group theory