  Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving
the hidden subgroup problem (HSP) over Z_2^n provided one of the first
algebraic problems for which quantum computers are exponentially faster than
their classical counterparts. In this paper, 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 = (m_1, ..., m_n) in G^n from an oracle f
with the property that f(x) = f(xy) iff y equals m or the identity. 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. Here we give quantum
algorithms with time complexity 2^O(sqrt(n log n)) that recover hidden
involutions m = (m_1, ..., m_n) in G^n where, as in Simon's problem, each m_i
is either the identity or the conjugate of a known element k, and there is a
character X of G for which X(k) = -X(1)$. 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 hidden subgroup
algorithms for group families that require highly entangled multiregister
Fourier sampling.
