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 Iso- morphism. 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 Isomor- phism.