Complexité de la communication : fonctions à grande sortie, bornes partitions et non-localité quantique La plupart des problèmes étudiés en complexité de la communication sont Booléens. Pour des fonctions à plus large sortie, la manière dont le résultat du calcul doit être retourné – le modèle de sortie – peut grandement changer la complexité du problème. De même, les bornes inférieures ne s’appliquent pas toutes à tous les modèles. Dans cette thèse, nous étudions des bornes inférieures impactées par le modèle de sortie, revisitons quelques résultats classiques à la lumière de ces modèles de sortie, et les relions au formalisme des comportements et des inégalités de Bell du domaine de la non-localité quantique. Premièrement, nous nous intéressons aux bornes partition et montrons que leur application à une fonction à large sortie donne nécessairement de grandes valeurs, indiquant qu’elles ne sont des bornes inférieures que pour un de nos modèles de sortie. Nous montrons également comment construire un protocole déterministe à partir d’une solution optimale de la borne partition dite “positive”, ainsi qu’une nouvelle connexion avec une autre borne inférieure, la régularité faible. Via une récente réinterprétation de la borne partition en termes d’information, nous établissons une séparation exponentielle entre la borne partition et la complexité de la communication. Le problème permettant cette séparation est un problème récemment introduit pour séparer la complexité de la communication et la complexité de l’information dite “externe”. Ensuite, nous définissons plusieurs modèles de sortie. Nous les séparons, en montrant de grands écarts de complexités entre les différents modèles sur quelques problèmes. Nous re-prouvons dans nos modèles quelques résultats classiques de réduction d’erreur et de suppression d’aléatoire auparavant seulement connus pour les modèles de sortie les plus courants. Nous établissons pour quelques problèmes naturels supplémentaires que leur complexité varie significativement en selon le modèle de sortie, et montrons que la borne inférieure du rang s’applique toujours à nos modèles à une petite modification près. En dernier lieu, nous traitons de non-localité quantique et montrons que certaines bornes inférieures en complexité de la communication peuvent être interprétées sous la forme d’inégalités de Bell. Les inégalités de Bell obtenues sont résistantes à l’inefficacité de détection, et ne le sont pas a priori à d’autres formes de bruit. Nous reformulons le calcul d’une fonction dans un modèle de sortie spécifique en le calcul d’un comportement – une famille de distributions de probabilités indexées par les entrées possibles. Ceci nous permet d’utiliser les bornes efficacité comme des généralisations naturelles de la borne partition pour des modèles de sortie non-standards.
Complexité de la communication : fonctions à grande sortie, bornes partitions et non-localité quantique La plupart des problèmes étudiés en complexité de la communication sont Booléens. Pour des fonctions à plus large sortie, la manière dont le résultat du calcul doit être retourné – le modèle de sortie – peut grandement changer la complexité du problème. De même, les bornes inférieures ne s’appliquent pas toutes à tous les modèles. Dans cette thèse, nous étudions des bornes inférieures impactées par le modèle de sortie, revisitons quelques résultats classiques à la lumière de ces modèles de sortie, et les relions au formalisme des comportements et des inégalités de Bell du domaine de la non-localité quantique. Premièrement, nous nous intéressons aux bornes partition et montrons que leur application à une fonction à large sortie donne nécessairement de grandes valeurs, indiquant qu’elles ne sont des bornes inférieures que pour un de nos modèles de sortie. Nous montrons également comment construire un protocole déterministe à partir d’une solution optimale de la borne partition dite “positive”, ainsi qu’une nouvelle connexion avec une autre borne inférieure, la régularité faible. Via une récente réinterprétation de la borne partition en termes d’information, nous établissons une séparation exponentielle entre la borne partition et la complexité de la communication. Le problème permettant cette séparation est un problème récemment introduit pour séparer la complexité de la communication et la complexité de l’information dite “externe”. Ensuite, nous définissons plusieurs modèles de sortie. Nous les séparons, en montrant de grands écarts de complexités entre les différents modèles sur quelques problèmes. Nous re-prouvons dans nos modèles quelques résultats classiques de réduction d’erreur et de suppression d’aléatoire auparavant seulement connus pour les modèles de sortie les plus courants. Nous établissons pour quelques problèmes naturels supplémentaires que leur complexité varie significativement en selon le modèle de sortie, et montrons que la borne inférieure du rang s’applique toujours à nos modèles à une petite modification près. En dernier lieu, nous traitons de non-localité quantique et montrons que certaines bornes inférieures en complexité de la communication peuvent être interprétées sous la forme d’inégalités de Bell. Les inégalités de Bell obtenues sont résistantes à l’inefficacité de détection, et ne le sont pas a priori à d’autres formes de bruit. Nous reformulons le calcul d’une fonction dans un modèle de sortie spécifique en le calcul d’un comportement – une famille de distributions de probabilités indexées par les entrées possibles. Ceci nous permet d’utiliser les bornes efficacité comme des généralisations naturelles de la borne partition pour des modèles de sortie non-standards.
La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.
Les fondements de l'informatique ont subi un bouleversement face a l'emergence du calcul quantique comme nouveau modele de calcul. Nous nous interesserons dans cette these a la complexite de la communication, vue sous l'angle de la theorie de l'information quantique. En complexite de la communication, on cherche a savoir combien de communication il faut pour resoudre des problemes ou les entrees sont reparties entre les entites de calcul. Cette these presente un moyen d'obtenir des bornes inferieures en complexite de la communication en exploitant des idees liees a l'etude de phenomenes quantiques tels que la nonlocalite. Ces methodes sont alors comparees aux methodes deja connues dans la litterature et permettent d'obtenir une nouvelle famille d'inegalites de Bell. Nous montrons aussi dans cette these, en utilisant les connections entre complexite de la communication et nonlocalite quantique, que toutes les bornes inferieures connues utilisees en complexite de la communication sont des bornes inferieures pour la complexite de l'information. Ceci renforce l'idee que ces deux quantites sont equivalentes et permet d'obtenir plusieurs resultats de sommes directes en complexite de la communication pour des fonctions souvent etudiees.
La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.
La théorie de la complexité de communication étudie le coût minimum de communication nécessaire pour évaluer une fonction lorsque les entrées sont distribuées parmi plusieurs entités. Deux modèles qui sont bien étudiés sont les modèles d'erreur bornée et d'erreur non-bornée, où les entités peuvent profiter de l'aléatoire pour faciliter leurs calculs. Les premiers résultats dans ce domaine montrèrent que la fonction Égalité peut être calculée avec un coût minimal dans des deux modèles aléatoires, tandis qu'elle atteint le coût maximal dans le modèle déterministe. Ceci démontre le pouvoir de l'aléatoire dans la communication, par opposition à des autres modèles de computation, tels que les arbres de décision.Le fait que l'Égalité présente la séparation maximale entre les efficacités de communication aléatoire et déterministe incite la recherche d'un modèle hybride de communication : un modèle déterministe avec accès à un oracle d'Égalité, où l'on remplace la sélection au hasard avec un pouvoir omniscient qui calcule l'Égalité de manière efficace. Un résultat clé concernant ce modèle d'oracle démontre que le pouvoir de la sélection aléatoire n'est pas entièrement reflété par la capacité de calculer l'Égalité efficacement, ce qui fait ce modèle intéressant à étudier.Un sujet fondamental dans la théorie de la complexité est la comparaison des puissances relatives des différents modèles. Les résultats sur les puissances peuvent être classifiés en trois catégories principales : séparation — quand un modèle est plus fort qu'un autre, inclusion — quand le critère d'efficacité d'un modèle est contenu dans celui d'un autre, et structure — quand les fonctions que l'on peut calculer dans un modèle possèdent certaines propriétés qui correspondent à la simplicité de calcul.Malgré de la recherche extensive dans le domaine, plusieurs questions fondamentales à propos de ces trois modèles ne sont toujours pas résolues. Le manque d'exemples explicites limite sévèrement notre compréhension des résultats structurels. De plus, beaucoup des techniques actuellement connues pour établir des bornes inférieures sont trop faibles pour caractériser structurellement les fonctions avec complexité uniformément bornée.Cette thèse présente de nouveaux résultats de séparation et structurels dans la complexité de communication, ce qui représente un avancement vers la résolution de ces problèmes ouverts reliés aux régimes de coût constant. On démontre que nos résultats de séparation fournissent des nouvelles séparations au-delà de la théorie de la complexité de communication : ils impliquent des séparations dans les domaines de la théorie d'apprentissage et la théorie de la complexité des requêtes
Preuves quantiques, le problème des Hamiltoniens locaux et applications Dans la classe de complexité QMA – la généralisation quantique de la classe NP – un état quantique est fourni comme preuve à un algorithme de vérification pour l’aider à résoudre un problème. Cette classe de complexité a un problème complet naturel, le problème des Hamiltoniens locaux. Inspiré par la Physique de la matière condensée, ce problème concerne l’énergie de l’état fondamental d’un système quantique. Dans le cadre de cette thèse, nous étudions quelques problèmes liés à la classe QMA et au problème des Hamiltoniens locaux. Premièrement, nous étudions la différence de puissance si au lieu d’une preuve quantique, l’algorithme de vérification quantique reçoit une preuve classique. Nous proposons un cadre intermédiaire à ces deux cas, où la preuve consiste en un état quantique “plus simple” et nous arrivons à démontrer que ces états plus simples sont suffisants pour résoudre tous les problèmes dans QMA. À partir de ce résultat, nous obtenons un nouveau problème QMA-complet et nous étudions aussi la version de notre nouvelle classe de complexité avec erreur unilatérale. Ensuite, nous proposons le premier schéma de délégation vérifiable relativiste de calcul quantique. Dans ce cadre, un client classique délègue son calcul quantique à deux serveurs quantiques intriqués. Ces serveurs peuvent communiquer entre eux en respectant l’hypothèse que l’information ne peut pas être propagé plus vite que la vitesse de la lumière. Ce protocole a été conçu à partir d’un jeu non-local pour le problème des Hamiltoniens locaux avec deux prouveurs et un tour de communication. Dans ce jeu, les prouveurs exécutent des calculs quantiques de temps polynomiaux sur des copies de l’état fondamental du Hamiltonien. Finalement, nous étudions la conjecture PCP quantique, où l’on demande si tous les problèmes dans la classe QMA acceptent un système de preuves où l’algorithme de vérification a accès à un nombre constant de qubits de la preuve quantique. Notre première contribution consiste à étendre le modèle QPCP avec une preuve auxiliaire classique. Pour attaquer le problème, nous avons proposé une version plus faible de la conjecture QPCP pour ce nouveau système de preuves. Nous avons alors montré que cette nouvelle conjecture peut également être exprimée dans le contexte des problèmes des Hamiltoniens locaux et ainsi que dans lecadre de la maximisation de la probabilité de acceptation des jeux quantiques. Notre résultat montre la première équivalence entre un jeu multi-prouveur et une conjecture QPCP.
La mécanique quantique prédit l'existence de corrélations entre particules distantes qui ne peuvent s'expliquer dans le cadre des théories réalistes locales. Suite au développement récent de la théorie de l'information quantique, il a été réalisé que ces corrélations non-locales ont des implications quant aux capacités de traitement de l'information des systèmes quantiques. Outre une signification physique, elles possèdent donc une signification informationnelle. Cette thèse traite de différents aspects de la non-localité liés à ces deux facettes du phénomène. Nous commençons par un examen de la structure des corrélations locales et non-locales. Nous dérivons dans ce contexte de nouvelles inégalités de Bell, et généralisons ensuite le paradoxe de Greenberger-Horne-Zelinger à des états quantiques de dimension arbitraire et composés de plusieurs sous-systèmes. Nous abordons par après la non-localité du point de vue de la théorie de l'information. Il est possible de concevoir des théories non-locales consistantes avec le principe de causalité mais offrant des avantages supérieurs à la mécanique quantique en terme de manipulation de l'information. Nous investiguons l'ensemble des corrélations compatibles avec de telles théories afin d'éclairer l'origine des limitations imposées par le formalisme quantique. Nous nous intéressons également à la quantité de communication classique nécessaire pour simuler les corrélations non-locales. Nous montrons que cette mesure naturelle de la non-localité est étroitement liée au degré de violations des inégalités de Bell. Nous nous tournons ensuite vers des aspects expérimentaux. La faible efficacité des détecteurs utilisés dans les expériences de violation des inégalités de Bell reste un obstacle majeur à une démonstration convaincante de la non-localité, mais aussi à toute utilisation de la non-localité dans des protocoles d'information quantique. Nous dérivons d'une part des bornes quant à l'efficacité minimale requise pour violer les inégalités de Bell, et d'autre part des exemples de corrélations plus résistante à ces imperfections expérimentales. Finalement, nous clôturons cette thèse en montrant comment la non-localité, principalement étudiée dans le cadre de systèmes décrits par des variables discrètes, telles que les variables de spin, peut également se manifester dans des systèmes à variables continues, telles que les variables de position et d'impulsion.