Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

The Quantum Query Complexity of the Abelian Hidden Subgroup Problem.

Abstract : Simon in his FOCS'94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon's problem from the point of view of quantum query complexity and give here a first nontrivial lower bound on the query complexity of a hidden subgroup problem, namely Simon's problem. Our bound is optimal up to a constant factor. We also show how, as a consequence, this gives us the query complexity of the Abelian hidden subgroup problem, up to a constant factor. At last we expose some elementary facts about complexity in weaker query models.
Document type :
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:06:16 AM
Last modification on : Saturday, September 11, 2021 - 3:19:19 AM


Files produced by the author(s)


  • HAL Id : hal-02101788, version 1



Pascal Koiran, Vincent Nesme, Natacha Portier. The Quantum Query Complexity of the Abelian Hidden Subgroup Problem.. [Research Report] LIP RR-2005-17, Laboratoire de l'informatique du parallélisme. 2005, 2+12p. ⟨hal-02101788⟩



Record views


Files downloads