Permutation groups, minimal degrees and quantum computing.
type: Item
instance of: scholarly article
title: Permutation groups, minimal degrees and quantum computing.
zbMATH Open document ID: 1143.20002
DOI: 10.4171/GGD/24
author: Julia Kempe
author: Aner Shalev
author: Laszló Pyber
published in: Groups, Geometry, and Dynamics
publication date: 2008-02-07T00:00:00Z
full work available at URL: https://arxiv.org/abs/quant-ph/0607204
review text: 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.)
reviewed by: A. Hulpke
Mathematics Subject Classification ID: 20B35
Mathematics Subject Classification ID: 20C15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 81P68
Mathematics Subject Classification ID: 20D60
Mathematics Subject Classification ID: 20B40
zbMATH DE Number: 5233110
zbMATH Keywords: permutation groups
zbMATH Keywords: quantum computing
zbMATH Keywords: minimal degree
zbMATH Keywords: hidden subgroup problem
zbMATH Keywords: characters
zbMATH Keywords: order bounds
MaRDI profile type: MaRDI publication profile
Wikidata QID: Q102355666
arXiv ID: quant-ph/0607204
cites work: On the order of uniprimitive permutation groups
cites work: On the order of doubly transitive permutation groups
cites work: Q4526969
cites work: Finite Permutation Groups and Finite Simple Groups
cites work: Q4882944
cites work: On quantum algorithms for noncommutative hidden subgroups
cites work: Q5465515
cites work: Q4044441
cites work: Classifying the finite simple groups
cites work: Q4860774
cites work: Q5465508
cites work: On the minimal degree of a primitive permutation group
cites work: Limitations of quantum coset states for graph isomorphism
cites work: Q5465509
cites work: EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
cites work: Q5315017
cites work: On the number of conjugacy classes of a finite group
cites work: A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
cites work: Parameters of Goppa codes revisited
Recommended article: On the number of fixed point free elements in a permutation group
Recommended article: On the orders of Transitive Permutation Groups
Recommended article: Minimal generation of transitive permutation groups
Recommended article: On minimal \(p\)-degrees in \(2\)-transitive permutation groups
Recommended article: Q3077170
Recommended article: Permutations of bounded degree generate groups of polynomial diameter
Recommended article: Q3979652
Recommended article: On minimal degrees and base sizes of primitive permutation groups
Recommended article: On the orders of doubly transitive permutation groups, elementary estimates
Recommended article: On the subgroup distance problem.
description: scientific article