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 :
Reports
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101788
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:16 AM
Last modification on : Wednesday, May 22, 2019 - 1:32:15 AM

File

RR2005-17.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101788, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

25

Files downloads

34