Alagic, G.,Moore, C.,Russell, A.
Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding "hidden shifts" of Z(2)(n) provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution (m) over right arrow = (m(1),..., m(n)) is an element of G(n) from an oracle f with the property that f ((x) over right arrow.(y) over right arrow) = f ((x) over right arrow) double left right arrow (y) over right arrow is an element of {(1) over right arrow, (m) over right arrow}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G(n), where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G(n) have a simple product structure, they share important representation-theoretic properties with the symmetric groups S-n, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so- called "standard method" requires highly entangled measurements on the tensor product of many coset states. In this article, we provide quantum algorithms with time complexity 2(O(root n)) that recover hidden involutions (m) over right arrow = (m(1),..., m(n)) is an element of G(n) where, as in Simon's problem, each m(i) is either the identity or the conjugate of a known element m which satisfies kappa(m) = -kappa(1) for some kappa is an element of (G) over cap. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the "missing harmonic" approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.