Permutation groups, minimal degrees and quantum computing. (Q2469771)

The minimal degree \(m\) of a permutation group \(H\leq S_n\) is the minimum number of points moved by a nontrivial element of \(H\). It can be considered as a ``minimum distance'' of group elements in the context of coding theory. Generalizing a result for transitive groups of \textit{M. W. Liebeck} [Bull. Lond. Math. Soc. 16, 523-524 (1984; Zbl 0551.20001)] to the general case, the authors prove a bound for \(|H|\) in terms of the minimal degree \(m\), concretely \(|H|\leq n^{10n/m}\) for \(m\leq\log_2(n)\) and \(|H|\leq 2^{10n}\) otherwise. These bounds are essentially tight. They also give (Theorem B), involving a rather technical proof, a bound for the size of the subset of elements of \(H\) that attain the minimal degree, provided this minimal degree exceeds a certain absolute constant. A main motivation for this bound is the so-called Hidden Subgroup Problem (HSP) in quantum computation: Given a function that decides whether two elements \(x,y\in G\) lie in the same coset of \(H\leq G\), determine whether \(H\) is nontrivial. The known quantum algorithms for factorization [\textit{P. W. Shor}, SIAM J. Comput. 26, No. 5, 1484-1509 (1997; Zbl 1005.11065)] essentially solve this problem for Abelian groups, a nonabelian version would solve graph isomorphism on a quantum computer. The order bound of Theorem B then implies (Theorem C and Corollary D) that any HSP that can be solved in polynomial time by a certain generalization of the methods for the Abelian case (the ``weak standard method'') can already be solved in polynomial time by classical methods. This strengthens an impossibility result of \textit{A. R. C. Moore} and \textit{L. Schulman} [The symmetric group defines strong Fourier sampling. In FOCS '05, IEEE Computer Society 479-490 (2005)]. (The proof relies on the classification of finite simple groups.)