Permutation groups, minimal degrees and quantum computing

Abstract

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 $H\le S_n$ 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 $S_n$ in quantum computing. We completely characterize the hidden subgroups of $S_n$ that can be distinguished from identity with weak Quantum Fourier Sampling, showing that these are exactly the subgroups with bounded minimal degree. This implies that the weak standard method for $S_n$ has no advantage whatsoever over classical exhaustive search.