Complexité en requêtes et symétries
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
This work is about the study of the query complexy of symmetric problems, in both frameworks of quantum and classical randomized computing. In the quantum case, we show a new application of the so-called "polynomial" lower bound method to the abelian hidden subgroup problems, via the "symmetrization" technique. In the case of randomized computing, under a "transitive symmetry" hypothesis on the considered problems, we give a combinatorial formula allowing us to compute the exact query complexity of the best nonadaptive algorithm. Moreover, we show that under some symmetry conditions, this best nonadaptive algorithm is optimal amongst general algorithms, which gives an expression of the exact query complexity for the corresponding class of problems.
Abstract FR:
Ces travaux portent sur l'étude de la complexité en requêtes de problèmes symétriques, dans les cadres du calcul probabiliste classique et du calcul quantique. Il est montré, dans le cas quantique, une application de la méthode de bornes inférieures dite "polynomiale" au calcul de la complexité en requête des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation". Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie transitive" des problèmes, il est donné une formule combinatoire permettant de calculer la complexité en requêtes exacte du meilleur algorithme non-adaptatif. De plus, il est mis en évidence que sous certaines hypothèses de symétries, ce meilleur algorithme non-adaptatif est optimal même parmi les algorithmes probabilistes plus généraux, ce qui donne pour la classe de problèmes correspondante une expression exacte de la complexité en requêtes.