  Many quantum algorithms, including Shor's celebrated factoring and discrete
log algorithms, proceed by reduction to a Hidden Subgroup problem, in which an
unknown subgroup H of a group G must be determined from a uniform superposition
on a left coset of H. These hidden subgroup problems are typically solved by
Fourier sampling. When G is nonabelian, two important variants of Fourier
sampling have been identified: the weak standard method, where only
representation names are measured, and the strong standard method, where full
measurement (i.e., the row and column of the representation, in a suitably
chosen basis) occurs. It has remained open whether the strong standard method
is indeed stronger. In this article, we settle this question in the
affirmative. We show that hidden subgroups H of the q-hedral groups, i.e.,
semidirect products Z_q \ltimes Z_p where q | (p-1), and in particular the
affine groups A_p, can be information-theoretically reconstructed using the
strong standard method. Moreover, if |H| = p/ \polylog(p), these subgroups can
be fully reconstructed with a polynomial amount of quantum and classical
computation. We show that, for some q, neither the ``forgetful'' abelian method
nor measuring in a random basis succeeds, even information-theoretically. Thus,
at least for some groups, it is crucial to use the full power of representation
theory: namely, to measure the high-dimensional representations in an adapted
basis that respects the group's subgroup structure. We apply our algorithm for
the hidden subgroup problem to new families of cryptographically motivated
Hidden Shift problems, generalizing work of van Dam, Hallgren and Ip on shifts
of multiplicative characters.
