Generic quantum Fourier transforms

ABSTRACT

The quantum Fourier transform (QFT) is the principal ingredient of most 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 use 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 group families for which efficient QFTs are currently known and many new group families. 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: ACM, editor. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing: Hersonissos, Crete, Greece, July 6--8, 2001, New York, NY, USA, 2001. ACM Press.
• 2: A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Revew A, pages 3457--, 1995.
• 3: 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]
• 4: 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]
• 5: 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]
• 6: A. H. Clifford. Representations induced in an invariant subgroup. Annals of Mathematics, 38:533--550, 1937.
• 7: D. Coppersmith. An approximate Fourier transform useful in quantum factoring. Technical Report RC19642, IBM, 1994. Quantum Physics e-Print Archive, quantph/0201067.
• 8: Persi Diaconis and Daniel Rockmore. Efficient computation of the Fourier transform on finite groups. J. Amer. Math. Soc., 3(2):297--332, 1990.
• 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: Frank Harary. Graph Theory. Addison-Wesley, 1969.
• 13: Peter Høyer. Efficient quantum transforms. Technical Report quant-ph/9702028, Quantum Physics e-Print Archive, 1997.
• 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: Adalbert Kerber. Representations of Permutation Groups I, II, volume 240 and 495 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1971 and 1975.
• 16: A. Yu. Kitaev. Quantum measurements and the abelian stabilizer problem. Technical Report quant-ph/9511026, Quantum Physics e-Print Archive, 1995.
• 17: 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
• 18: David K. Maslen and Daniel N. Rockmore. Separation of variables and the computation of Fourier transforms on finite groups, I. Journal of the American Math Society, 10(1):169--214, 1997.
• 19: David K. Maslen and Daniel N. Rockmore. The Cooley-Tukey FFT and group theory. Notices Amer. Math. Soc., 48(10):1151--1160, 2001.
• 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: Daniel Rockmore. Fast Fourier transforms for wreath products. J. Applied and Computational Harmonic Analysis, 2:279--292, 1995.
• 24: Jean-Pierre Serre. Linear Representations of Finite Groups. Springer-Verlag, 1977.
• 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: Barry Simon. Representations of Finite and Compact Groups, volume 10 of Graduate Studies in Mathematics. American Mathematical Society, 1996.
• 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]