 |
| Département |
| Informatique |
|
|
Miklos SanthaIntroduction au calcul quantique D'après la version quantitative de la thèse de Church, n'importe quel outil de calcul physiquement réalisable peut être simulé par une machine de Turing probabiliste avec un surcoût seulement polynomial. Le grand intérêt envers les ordinateurs quantiques lors de la dernière décennie est dû au fait qu'ils constituent le premier défi potentiel à cette thèse : en effet, pour plusieurs problèmes importants des algorithmes quantiques efficaces ont été obtenus qui n'ont pas à cette date des variantes classiques. Dans cette conférence on va décrire les résultats de base de ce domaine nouveau.Au début de l'exposé on définira les principes de base de la mécanique quantique qui sont appliqués en algorithmique pour exploiter le parallélisme intrinsèque des superpositions. Deux modèles du calcul quantique seront brièvement décrits: la machine de Turing et le circuit quantiques. On discutera quelques unes des questions fondamentales concernant ces modèles : la caractérisation des instances valides, l'existence des machines universelles, et les simulations parmi les modèles. La partie principale de la conférence traitera des algorithmes quantiques efficaces pour les problèmes ``Moitié ou Rien" (MR) , Sous-groupe Abélien Inconnu" (SAI) et ``Recherche" (R). La solution de Deutsch et Jozsa sera présentée pour le problème MR, où on doit distinguer des fonction balancées des fonctions constantes avec aussi peu d'évaluations que possible. Dans le problème SAI on recoit une fonction définie sur un groupe fini, qui est constante et distincte sur les cosets d'un sous-groupe inconnu : la tâche est de trouver un ensemble générateur pour le sous-groupe en temps polylogarithmique en la taille du groupe. On décrira une méthode générale pour résoudre ce problème qui est l'aboutissement d'une série de résultats, et on montrera comment la procédure de Simon et l'algorithme célèbre de factorisation de Shor découlent de cette méthode. Enfin, le problème R consiste à chercher un élément distingué dans un tableau de $N$ entrées : l'élégant algorithme de recherche de Grover accomplit cette tâche en $O(\sqrt{N})$ pas. A la fin de la conférence on définira des classes de complexité quantique et on discutera leur rapport aux classes classiques. Les résultats algorithmiques seront interprétés dans ce cadre théorique. Georges Gonthier Le théorème des quatre couleurs
Introduction à la modélisation et à la vérification. Application aux systèmes temporisés Une introduction à la bioinformatique moléculaire Vers une théorie algébrique des circuits booléens L'algorithme d'Euclide, hier et aujourd'hui : Un exemple d'analyse d'algorithmes Répétitions dans les mots : introduction et problèmes ouverts Autour du théorème de Cobham, approches par les automates et la logique Introduction à la sémantique des jeux asynchrones
Contacter le Département Informatique Dernières modifications : le 10/11/2008 |