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.
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.
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.
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 l'information multipartite étudie les problèmes de communication avec plusieurs émetteurs, plusieurs récepteurs et des stations relais. L'objectif de cette thèse est d'étendre les idées centrales de la théorie de l'information classique à l'étude des canaux quantiques. Nous allons nous intéresser aux scénarios de communication suivants: les canaux quantiques à accès multiples, les canaux quantiques à interférence, les canaux quantiques de diffusion et les canaux quantiques à relais. Dans chacun des ces scénarios de communication, nous caractérisons les taux de communication réalisables pour l'envoi d'information classique sur ces canaux quantiques. La modélisation quantique des canaux de communication est importante car elle fournit une représentation plus précise de la capacité du canal à transmettre l'information. En utilisant des modèles physiquement réalistes pour les sorties du canal et la procédure de détection, nous obtenons de meilleurs taux de communication que ceux obtenus dans un modèle classique. En effet, l'utilisation de mesures quantiques collectives sur l'ensemble des systèmes physiques en sortie du canal permet une meilleure extraction d'information que des mesures indépendantes sur chaque sous-système. Nous avons choisi d'étudier les canaux à entrée classique et sortie quantique qui constituent une abstraction utile pour l'étude de canaux quantiques généraux où l'encodage est restreint au domaine classique.Nous étudions le régime asymptotique où de nombreuses copies de du canal sont utilisées en parallèle, et les utilisations sont indépendantes. Dans ce contexte, il est possible de caractériser les limites absolues sur la transmission d'information d'un canal, si on connait les statistiques du bruit sur ce canal. Ces résultats théoriques peuvent être utilisées comme un point de repère pour évaluer la performance des protocoles de communication pratiques. Nous considérons surtout les canaux où les sorties sont des systèmes quantiques de dimension finie, analogues aux canaux classiques discrets. Le dernier chapitre présente des applications pratiques de nos résultats à la communication optique, où systèmes physiques auront des degrés de liberté continus. Ce contexte est analogue aux canaux classiques avec bruit gaussien.
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.
High dimension and symmetries in quantum information theory S'il fallait résumer le sujet de cette thèse en une expression, cela pourrait être quelque chose comme: phénomènes de grande dimension (mais néanmoins finie) en théorie quantique de l'information. Cela étant dit, essayons toutefois de développer brièvement. La physique quantique a inéluctablement affaire à des objets de grande dimension. Partant de cette observation, il y a, en gros, deux stratégies qui peuvent être adoptées: ou bien essayer de ramener leur étude à celle de situations de plus petite dimension, ou bien essayer de comprendre quels sont les comportements universels précisément susceptibles d'émerger dans ce régime. Nous ne donnons ici notre préférence à aucune de ces deux attitudes, mais au contraire oscillons constamment entre l'une et l'autre. Notre but dans la première partie de ce manuscrit (Chapitres 5 et 6) est de réduire autant que possible la complexité de certains processus quantiques, tout en préservant, évidemment, leurs caractéristiques essentielles. Les deux types de processus auxquels nous nous intéressons sont les canaux quantiques et les mesures quantiques. Dans les deux cas, la complexité d'une transformation est mesurée par le nombre d'opérateurs nécessaires pour décrire son action, tandis que la proximité entre la transformation d'origine et son approximation est définie par le fait que, quel que soit l'état d'entrée, les deux états de sortie doivent être proches l'un de l'autre. Nous proposons des solutions universelles (basées sur des constructions aléatoires) à ces problèmes de compression de canaux quantiques et d'amenuisement de mesures quantiques, et nous prouvons leur optimalité. La deuxième partie de ce manuscrit (Chapitres 7, 8 et 9) est, au contraire, spécifiquement dédiée à l'analyse de systèmes quantiques de grande dimension et certains de leurs traits typiques. L'accent est mis sur les systèmes multi-partites et leurs propriétés ayant un lien avec l'intrication. Les principaux résultats auxquels nous aboutissons peuvent se résumer de la façon suivante: lorsque les dimensions des espaces sous-jacents augmentent, il est générique pour les états quantiques multi-partites d'être à peine distinguables par des observateurs locaux, et il est générique pour les relaxations de la notion de séparabilité d'en être des approximations très grossières. Sur le plan technique, ces assertions sont établies grâce à des estimations moyennes de suprema de processus gaussiens, combinées avec le phénomène de concentration de la mesure. Dans la troisième partie de ce manuscrit (Chapitres 10 et 11), nous revenons pour finir à notre état d'esprit de réduction de dimensionnalité. Cette fois pourtant, la stratégie est plutôt: pour chaque situation donnée, tenter d'utiliser au maximum les symétries qui lui sont inhérentes afin d'obtenir une simplification qui lui soit propre. En reliant de manière quantitative symétrie par permutation et indépendance, nous nous retrouvons en mesure de montrer le comportement multiplicatif de plusieurs quantités apparaissant en théorie quantique de l'information (fonctions de support d'ensembles d'états, probabilités de succès dans des jeux multi-joueurs non locaux etc.). L'outil principal que nous développons dans cette optique est un résultat de type de Finetti particulièrement malléable