Groups, Geometry, and Dynamics


Full-Text PDF (284 KB) | Metadata | Table of Contents | GGD summary
Volume 1, Issue 4, 2007, pp. 553–584
DOI: 10.4171/GGD/24

Permutation groups, minimal degrees and quantum computing

Julia Kempe[1], László Pyber[2] and Aner Shalev[3]

(1) Tel Aviv University, Israel
(2) Hungarian Academy of Sciences, Budapest, Hungary
(3) The Hebrew University of Jerusalem, Israel

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 ≤ Sn 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 Sn in quantum computing. We completely characterize the hidden subgroups of Sn 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 Sn has no advantage whatsoever over classical exhaustive search.

Keywords: Permutation groups, quantum computing, minimal degree, Hidden Subgroup Problem, characters

Kempe Julia, Pyber László, Shalev Aner: Permutation groups, minimal degrees and quantum computing. Groups Geom. Dyn. 1 (2007), 553-584. doi: 10.4171/GGD/24