Miklos Santha
Introduction 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
Patricia Bouyer
Introduction à la modélisation et à
la vérification. Application aux systèmes temporisés
Alexander Bockmayr
Une introduction à la
bioinformatique moléculaire
Yves Lafont
Vers une théorie algébrique des
circuits booléens
Brigitte Vallée
L'algorithme d'Euclide, hier et
aujourd'hui : Un exemple d'analyse d'algorithmes
Jean Berstel
Répétitions dans les mots :
introduction et problèmes ouverts
Véronique Bruyère
Autour du théorème de
Cobham, approches par les automates et la logique
Paul-André Melliès
Introduction à la sémantique des
jeux asynchrones
Contacter le Département InformatiqueDernières modifications : le 10/11/2008