Authors
Sean Hallgren, Alexander Russell, Amnon Ta-Shma
Publication date
2000/5/1
Book
Proceedings of the thirty-second annual ACM symposium on Theory of computing
Pages
627-635
Description
The Hidden Subgroup Problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over Abelian groups and this was used in Simon's algorithm and Shor's Factoring and Discrete Log algorithms. The non-Abelian case is open; an efficient solution would give rise to an efficient quantum algorithm for Graph Isomorphism. We fully analyze a natural generalization of the Abelian case solution to the non-Abelian case, and give an efficient solution to the problem for normal subgroups. We show, however, that this immediate generalization of the Abelian algorithm does not efficiently solve Graph Isomorphism.
Total citations
Scholar articles
S Hallgren, A Russell, A Ta-Shma - Proceedings of the thirty-second annual ACM …, 2000