Abstract EN:

Les fondements de l'informatique ont subi un bouleversement face à l'émergence du calcul quantique comme nouveau modèle de calcul. Nous nous intéresserons dans cette thèse à la complexité de la communication, vue sous l'angle de la théorie de l'information quantique. En complexité de la communication, on cherche à savoir combien de communication il faut pour résoudre des problèmes où les entrées sont réparties entre les entités de calcul. Cette thèse présente un moyen d'obtenir des bornes inférieures en complexité de la communication en exploitant des idées liées à l'étude de phénomènes quantiques tels que la nonlocalité. Ces méthodes sont alors comparées aux méthodes déjà connues dans la littérature et permettent d'obtenir une nouvelle famille d'inégalités de Bell. Nous montrons aussi dans cette thèse, en utilisant les connections entre complexité de la communication et nonlocalité quantique, que toutes les bornes inférieures connues utilisées en complexité de la communication sont des bornes inférieures pour la complexité de l'information. Ceci renforce l'idée que ces deux quantités sont équivalentes et permet d'obtenir plusieurs résultats de sommes directes en complexité de la communication pour des fonctions souvent étudiées.