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
Reports

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 metadata

Cited literature [24 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101788
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

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

20

Files downloads

210