Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 19 Février 2008

Des algorithmes probabilistes aux algorithmes quantiques (et vice versa)

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr