Normal subgroup reconstruction and quantum computation using group representations

Abstract

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.