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 metadatas

Cited literature [24 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:16 AM
Last modification on : Thursday, November 21, 2019 - 2:38:38 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⟩