Preuves Interactives Quantiques

Cette the se est consacre e a la complexite base e sur le paradigme des preuves interactives. Les classes ainsi de finies ont toutes en commun qu un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un ve rificateur, de puissance borne e, de l appartenance d un mot a un langage. Nous abordons ici le mode le classique, ou les participants sont des machines de Turing, et le mode le quantique, ou ceux-ci sont des circuits quantiques. La revue de litte rature s adresse a un lecteur de ja familier avec la complexite et l informatique quantique. Cette the se pre sente comme re sultat la caracte risation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les diffe rentes classes sont pre sente es 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 subse quemment pre sente es. Les chapitres deux et trois pre sentent respectivement les classes a un et a plusieurs prouveurs. La pre sentation du re sultat ci-haut mentionne est l objet du chapitre quatre.