Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Full text

Pdf (175 KB)

Source

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

Hersonissos, Greece

Pages: 68 - 74

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Michelangelo Grigni	Emory University
Leonard Schulman	Caltech
Monica Vazirani	U. C. Berkeley
Umesh Vazirani

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 28, Citation Count: 17

Additional Information:

abstract 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/380752.380769 What is a DOI?

ABSTRACT

We provide positive and negative results concerning the “standard method” of identifying a hidden subgroup of a nonabelian group using a quantum computer.

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	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]
	2	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]
	3	Persi Diaconis and Daniel Rockmore.E .cient isthesta-computation of the Fourier transform of finite roups. J. Amer. Math. Soc.,3(2),297 -332,1990.
	4	Mark Ettinger , Peter Høyer, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics, v.25 n.3, p.239-251, Oct. 2000 [doi>10.1006/aama.2000.0699]
	5	Mark Ettin er,Peter Hoyer and Emanuel Knill. Hidden sub roup states are almost orthogonal.LANL preprint quant-ph/9901034.
	6	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]
	7	Alexei Kitaev.Quantum measurements and the abelian stabilizer problem.ECCC Report TR96-003, 1996.
	8	Johannes Köbler , Uwe Schöning , Jacobo Torán, The graph isomorphism problem: its structural complexity, Birkhauser Verlag, Basel, Switzerland, 1994
	9	Markus Puschel,Martin Rotteler,and Thomas Beth. Fast quantum Fourier transforms for a class of non-abelian roups.LANL e-preprint quant-ph/9807064,1998.
	10	D. Rockmore, Computation of Fourier transforms on the symmetric group, Proceedings of the third conference on Computers and mathematics, p.156-165, May 1989, Boston, Massachusetts, United States
	11	Jean-Pierre Serre.Linear Representations of Finite Groups Springer-Verlag,1977.
	12	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]
	13	Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
	14	Wim van Dam and Sean Hall ren.E .cient Quantum Algorithms for Shifted Quadratic Character Problems. LANL e-preprint quant-ph/0011067,2000.

CITED BY 17

	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 , 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
	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
	Mark Ettinger , Peter Høyer , Emanuel Knill, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters, v.91 n.1, p.43-48, 16 July 2004
	Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004
	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
	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
	Scott Aaronson , Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM (JACM), v.51 n.4, p.595-605, July 2004
	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
	Andrew M. Childs , Richard Cleve , Enrico Deotto , Edward Farhi , Sam Gutmann , Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, ACM Transactions on Algorithms (TALG), v.2 n.4, p.707-723, October 2006
	Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Journal of the ACM (JACM), v.54 n.1, p.1-es, March 2007
	Cristopher Moore , Alexander Russell , Piotr Sniady, On the impossibility of a quantum sieve algorithm for graph isomorphism, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Katalin Friedl , Miklos Santha , Frédéric Magniez , Pranab Sen, Quantum Testers for Hidden Group Properties, Fundamenta Informaticae, v.91 n.2, p.325-340, April 2009