The hidden subgroup problem and permutation group theory

Julia Kempe, Aner Shalev

Research output: Contribution to conferencePaper

Abstract

We employ concepts and tools from the theory of finite permutation groups in order to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS) for the symmetric group. We show that under very general conditions both the weak and the random-strong form (strong form with random choices of basis) of QFS fail to provide any advantage over classical exhaustive search. In particular we give a complete characterisation of polynomial size subgroups, and of primitive subgroups, that can be distinguished from the identity subgroup with the above methods. Furthermore, assuming a plausible group theoretic conjecture for which we give supporting evidence, we show that weak and random-strong QFS for the symmetric group have no advantage whatsoever over classical search.

Original languageEnglish (US)
Pages1118-1125
Number of pages8
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The hidden subgroup problem and permutation group theory'. Together they form a unique fingerprint.

  • Cite this

    Kempe, J., & Shalev, A. (2005). The hidden subgroup problem and permutation group theory. 1118-1125. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.