The Quantum Query Complexity of the Abelian Hidden Subgroup Problem. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

The Quantum Query Complexity of the Abelian Hidden Subgroup Problem.

(1) , (1) , (1)
1

Résumé

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.
Dans son article de FOCS’94, Simon fut le premier à montrer un cas où le calcul quantique permet une accélération exponentielle par rapport au calcul classique. Il s’agissait d’un problème qui fait partie d’une classe de problèmes aujourd’hui très étudiés, les problèmes de sous-groupes cachés. Nous étudions le problème de Simon du point de vue de la complexité en requêtes quantiques. Nous donnons une première borne inférieure non triviale sur cette complexité et montrons comment on obtient en conséquence la complexité en requêtes quantiques du problème du sous-groupe caché Abélien, à un facteur constant près. Nous présentons enfin quelques résultat élémentaires de complexité pour des modèles de requêtes plus faibles
Fichier principal
Vignette du fichier
RR2005-17.pdf (619.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101788 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101788 , version 1

Citer

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⟩
20 Consultations
231 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More