Permutation groups, minimal degrees and quantum computing

by: Julia Kempe, Laszlo Pyber, Aner Shalev

(28 Jul 2006)

View FullText article

arXiv (abstract), arXiv (PDF)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

jrw, divall

Find related articles with these CiteULike tags

algorithms, computation, group, group-theory, mathematics, permutations, physics, quantum, quantum-computation, symmetry

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 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. <br />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.

@misc{citeulike:781363, 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 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. <br />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.}, author = {Kempe, Julia and Pyber, Laszlo and Shalev, Aner }, citeulike-article-id = {781363}, eprint = {quant-ph/0607204}, keywords = {group, quantum}, month = {Jul}, posted-at = {2006-08-06 05:37:51}, priority = {3}, title = {Permutation groups, minimal degrees and quantum computing}, url = {http://arxiv.org/abs/quant-ph/0607204}, year = {2006} }

RIS record

TY - ELEC ID - citeulike:781363 L3 - citeulike-article-id:781363 TI - Permutation groups, minimal degrees and quantum computing N2 - 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. <br />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. KW - group KW - quantum AU - Kempe, Julia AU - Pyber, Laszlo AU - Shalev, Aner PY - 2006/Jul/28/ UR - http://arxiv.org/abs/quant-ph/0607204 ER -

RIS BibTeX