Preuves interactives quantiques

Cette these est consacree a la complexite basee sur le paradigme des preuves interactives. Les classes ainsi definies ont toutes en commun qu'un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un verificateur, de puissance bornee, de l'appartenance d'un mot a un langage. Nous abordons ici le modele classique, ou les participants sont des machines de Turing, et le modele quantique, ou ceux-ci sont des circuits quantiques. La revue de litterature s'adresse a un lecteur deja familier avec la complexite et l'informatique quantique. Cette these presente comme resultat la caracterisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les differentes classes sont presentees dans un ordre permettant d'aborder aussi facilement que possible les classes interactives. Le premier chapitre est consacre aux classes de base de la complexite; celles-ci seront utiles pour situer les classes subsequemment presentees. Les chapitres deux et trois presentent respectivement les classes a un et a plusieurs prouveurs. La presentation du resultat ci-haut mentionne est l'objet du chapitre quatre.