CaltechAUTHORS
  A Caltech Library Service

The hidden subgroup problem and quantum computation using group representations

Hallgren, Sean and Russell, Alexander and Ta-Shma, Amnon (2003) The hidden subgroup problem and quantum computation using group representations. SIAM Journal on Computing, 32 (4). pp. 916-934. ISSN 0097-5397. http://resolver.caltech.edu/CaltechAUTHORS:HALsiamjc03

[img]
Preview
PDF
See Usage Policy.

214Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:HALsiamjc03

Abstract

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.


Item Type:Article
Additional Information:© 2003 Society for Industrial and Applied Mathematics. Received by the editors August 28, 2001; accepted for publication (in revised form) December 16, 2002; published electronically June 10, 2003. A preliminary version of this article appeared in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 627–635. The bulk of this research was completed while the authors were at the University of California, Berkeley. The authors thank Umesh Vazirani for many helpful discussions and the simplification of several of the proofs.
Subject Keywords:quantum computation, quantum algorithms, computational complexity, representation theory, finite groups, algorithms, computer
Record Number:CaltechAUTHORS:HALsiamjc03
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:HALsiamjc03
Alternative URL:http://dx.doi.org/10.1137/S009753970139450X
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:850
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:21 Oct 2005
Last Modified:26 Dec 2012 08:41

Repository Staff Only: item control page