Normal subgroup reconstruction and quantum computation using group representations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Normal subgroup reconstruction and quantum computation using group representations

Full text

Pdf (834 KB)

Source

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

Portland, Oregon, United States

Pages: 627 - 635

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Sean Hallgren	Computer Science Division, University of California, Berkeley, CA
Alexander Russell	Department of Computer Science and Engineering, University of Connecticut, Storrs, CT
Amnon Ta-Shma	Computer Science Division, University of California, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 32, Citation Count: 18

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/335305.335392 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	Noga Alon and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, Inc., 1992.
	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	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
	4	Persi Diaconis and Daniel Rockmore. Efficient computation of the Fourier transform on finite groups. J. Amer. Math. Soc., 3(2):297-332, 1990.
	5	Mark Ettinger and Peter Heyer. On quantum algorithms for noncommutative hidden subgroups. In Symposium on Theoretical Aspects in Computer Science, University of Trier, 426 March 1999.
	6	Mark Ettinger and Peter Heyer. Quantum state detection via elimination. Technical report, quantph/9905099, 1999.
	7	Mark Ettinger and Peter Heyer. A quantum observable for the graph isomorphism problem. Technical report, quant-ph/9901029, 1999.
	8	Mark Ettinger and Peter Heyer and Emanuel Knill. Hidden subgroup states are almost orthogonal. Technical report, quant-ph/9901034, 1999.
	9	Mikael Goldmann , Alexander Russell, The Complexity of Solving Equations Over Finite Groups, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.80, May 04-06, 1999
	10	Michaelangelo Grigni, Leonard Schulman, and Umesh Vazirani. Unpublished, 1997.
	11	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 [doi>10.1145/301250.301336]
	12	Joe Harris and William Fulton. Representation Theory. Number 129 in Graduate Texts in Mathematics. Springer-Verlag, New York, NY, 1991.
	13	Alexey Yu. Kitaev. Quantum measurements and the abelian stabilizer problem. Technical report, quantph/9511026, 1995.
	14	Johannes Köbler , Uwe Schöning , Jacobo Torán, The graph isomorphism problem: its structural complexity, Birkhauser Verlag, Basel, Switzerland, 1994
	15	Martin RStteler and Thomas Beth. Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. Technical report, quantph/9812070, 1998.
	16	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]
	17	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]

CITED BY 18

	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
	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
	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
	Richard Jozsa, Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem, IEEE MultiMedia, v.3 n.2, p.34-43, March 1996
	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
	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
	V. Arvind , Piyush P. Kurur, Graph isomorphism is in SPP, Information and Computation, v.204 n.5, p.835-852, May 2006
	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
	Gorjan Alagic , Cristopher Moore , Alexander Russell, Quantum algorithms for Simon's problem over general groups, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1217-1224, January 07-09, 2007, New Orleans, Louisiana