  We resolve the question of whether Fourier sampling can efficiently solve the
hidden subgroup problem. Specifically, we show that the hidden subgroup problem
over the symmetric group cannot be efficiently solved by strong Fourier
sampling, even if one may perform an arbitrary POVM on the coset state. Our
results apply to the special case relevant to the Graph Isomorphism problem.
