Quantum hidden subgroup algorithms - Nolan Wallach

Shor's algorithm for quantum factorization and discrete log involves a reduction to his quantum algorithm for period search. This can be interpreted as a hidden subgroup problem for a cyclic group. In this lecture we will describe Shor's method and the extent that it has been generalized in the literature (abelian groups, dihedral groups, normal subgroups of non-abelian groups). We will then discuss a new class of non-commutative groups for which there is a fast quantum algorithm.