  The hidden subgroup problem (HSP) provides a unified framework to study
problems of group-theoretical nature in quantum computing such as order finding
and the discrete logarithm problem. While it is known that Fourier sampling
provides an efficient solution in the abelian case, not much is known for
general non-abelian groups. Recently, some authors raised the question as to
whether post-processing the Fourier spectrum by measuring in a random
orthonormal basis helps for solving the HSP. Several negative results on the
shortcomings of this random strong method are known. In this paper however, we
show that the random strong method can be quite powerful under certain
conditions on the group G. We define a parameter r(G) for a group G and show
that O((\log |G| / r(G))^2) iterations of the random strong method give enough
classical information to identify a hidden subgroup in G. We illustrate the
power of the random strong method via a concrete example of the HSP over finite
Heisenberg groups. We show that r(G) = \Omega(1) for these groups; hence the
HSP can be solved using polynomially many random strong Fourier samplings
followed by a possibly exponential classical post-processing without further
queries. The quantum part of our algorithm consists of a polynomial computation
followed by measuring in a random orthonormal basis. This gives the first
example of a group where random representation bases do help in solving the HSP
and for which no explicit representation bases are known that solve the problem
with (\log G)^O(1) Fourier samplings. As an interesting by-product of our work,
we get an algorithm for solving the state identification problem for a set of
nearly orthogonal pure quantum states.
