The Quantum Query Complexity of the Abelian Hidden Subgroup Problem.

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 faible