Frédéric Magniez (LRI, Orsay)

Le but de cet exposé est de présenter les liens forts existants entre algorithmique probabiliste et quantique. D’une part, une large classe des algorithmes quantiques connus ont des analogues probabilistes dont ils s’inspirent. Nous exposeront les algorithmes de Grover et ceux des marches quantiques sous cet angle. D’autre part, la taille de la plus petite formule logique représentant une fonction booléenne donnée est reliée à sa complexité (en requêtes) quantique. Nous prouverons ce résultat en utilisant la méthode dite par adversaire, que nous caractériserons avec des outils de la complexité de Kolmogorov.