Quantum computation of Fourier transforms over symmetric groups

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantum computation of Fourier transforms over symmetric groups

Full text

Pdf (816 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 48 - 53

Year of Publication: 1997

ISBN:0-89791-888-6

Author

Robert Beals

Department of Mathematics, University of Arizona, P.O. BOX 210089, Tucson, AZ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 50, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258548 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Bennett, Logical reversability of computation, IBM J. Res. Develop. 17 pp. 525-532 (1973).
	2	C. Bennett and E. Bernstein and G. Brassard and U. Vazirani, Strengths and weaknesses of quantum computing, preprint (1994).
	3	Ethan Bernstein , Umesh Vazirani, Quantum complexity theory, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.11-20, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167097]
	4	Dan Boneh , Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.424-437, August 27-31, 1995
	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	D. Coppersmith, An approximate Fourier transform useful in quantum factoring, IBM Research Report 19642, (1994).
	7	P. Diaconis Group representations in probability and statistics, IMS Lecture Notes--Monograph Series 11, IMS, Hayward, California, (1988).
	8	P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, J. AMS $ no. 2, pp. 297-332 (1990).
	9	J. P. Serre, Linear representations of finite groups, Springer-Verlag, (1977).
	10	D. Simon, On the power of quantum computation, Proc. 35th IEEE FOGS, pp. 116-123 (1994).
	11	P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th IEEE FOGS, pp. 124-134 (1994).
	12	A. Yao, Quantum circuit complexity, Proc. 34th IEEE FOGS, pp. 352-360 (1993).

CITED BY 16

	Wim van Dam , Sean Hallgren , Lawrence Ip, Quantum algorithms for some hidden shift problems, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	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
	Lisa Hales , Sean Hallgren, Quantum Fourier sampling simplified, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.330-338, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Katalin Friedl , Gábor Ivanyos , Frédéric Magniez , Miklos Santha , Pranab Sen, Hidden translation and orbit coset in quantum computing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Richard Jozsa, Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem, IEEE MultiMedia, v.3 n.2, p.34-43, March 1996
	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
	Julia Kempe , Aner Shalev, The hidden subgroup problem and permutation group theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Sean Hallgren , Cristopher Moore , Martin Rötteler , Alexander Russell , Pranab Sen, Limitations of quantum coset states for graph isomorphism, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, ACM Transactions on Algorithms (TALG), v.2 n.4, p.707-723, October 2006
	Pascal Koiran , Vincent Nesme , Natacha Portier, The quantum query complexity of the abelian hidden subgroup problem, Theoretical Computer Science, v.380 n.1-2, p.115-126, June, 2007
	Peter W. Shor, Progress in Quantum Algorithms, Quantum Information Processing, v.3 n.1-5, p.5-13, October 2004
	Dave Bacon , Isaac L. Chuang , Aram W. Harrow, The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1235-1244, January 07-09, 2007, New Orleans, Louisiana
	David Emms , Richard C. Wilson , Edwin R. Hancock, Graph matching using the interference of continuous-time quantum walks, Pattern Recognition, v.42 n.5, p.985-1002, May, 2009