Preuves interactives quantiques

Cette the¿se est consacre¿e ä 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 ä 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 ä un lecteur de¿jä 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 ä un et ä plusieurs prouveurs. La pre¿sentation du re¿sultat ci-haut mentionne¿ est l¿objet du chapitre quatre.