  We study permutation groups of given minimal degree without the classical
primitivity assumption. We provide sharp upper bounds on the order of a
permutation group of minimal degree m and on the number of its elements of any
given support. These results contribute to the foundations of a non-commutative
coding theory.
  A main application of our results concerns the Hidden Subgroup Problem for
the symmetric group in Quantum Computing. We completely characterize the hidden
subgroups of the symmetric group that can be distinguished from identity with
weak Quantum Fourier Sampling, showing these are exactly the subgroups with
bounded minimal degree. This implies that the weak standard method for the
symmetric group has no advantage whatsoever over classical exhaustive search.
