L'informatique quantique, ce surprenant mariage entre informatique et physique, est un domaine riche en nouvelles idées, autant pour la technologie future qu'une meilleure compréhension de notre univers. C'est le phénomène de l'intrication qui est au coeur de cette nouvelle façon de voir l'information. Ce mémoire porte sur l'étude des corrélations quantiques observées dans la nature, mises de l'avant, entre autres, par John Bell. Plus particulièrement, deux jeux non signalants, dans lesquels ces corrélations se manifestent, sont étudiés: le jeu CHSH, probablement l'exemple le plus connu à ce jour, et le jeu de pseudotélépathie du carré magique. Pour ce faire, deux points de vue seront adoptés, soit probabiliste et algorithmique. Le premier est motivé par la prédiction (ce qui aurait pu se passer), tandis que le second s'intéresse à l'information intrinsèque contenue dans un objet (ce qui s'est passé). Les concepts «aléatoire» et «information» seront donc abordés premièrement à la Shannon (approche probabiliste) puis à la Kolmogorov (approche algorithmique). C'est la complexité de Kolmogorov qui sera utilisée pour quantifier l'information de façon factuelle. De plus, le cas particulier où plusieurs répétitions d'un jeu sont jouées en parallèle dans un monde classique sera examiné. Le théorème des répétitions parallèles, résultat important sur le sujet démontré par Ran Raz, sera présenté et utilisé par la suite dans l'étude algorithmique des jeux CHSH et du carré magique.
L'informatique quantique, ce surprenant mariage entre informatique et physique, est un domaine riche en nouvelles idées, autant pour la technologie future qu'une meilleure compréhension de notre univers. C'est le phénomène de l'intrication qui est au coeur de cette nouvelle façon de voir l'information. Ce mémoire porte sur l'étude des corrélations quantiques observées dans la nature, mises de l'avant, entre autres, par John Bell. Plus particulièrement, deux jeux non signalants, dans lesquels ces corrélations se manifestent, sont étudiés: le jeu CHSH, probablement l'exemple le plus connu à ce jour, et le jeu de pseudotélépathie du carré magique. Pour ce faire, deux points de vue seront adoptés, soit probabiliste et algorithmique. Le premier est motivé par la prédiction (ce qui aurait pu se passer), tandis que le second s'intéresse à l'information intrinsèque contenue dans un objet (ce qui s'est passé). Les concepts «aléatoire» et «information» seront donc abordés premièrement à la Shannon (approche probabiliste) puis à la Kolmogorov (approche algorithmique). C'est la complexité de Kolmogorov qui sera utilisée pour quantifier l'information de façon factuelle. De plus, le cas particulier où plusieurs répétitions d'un jeu sont jouées en parallèle dans un monde classique sera examiné. Le théorème des répétitions parallèles, résultat important sur le sujet démontré par Ran Raz, sera présenté et utilisé par la suite dans l'étude algorithmique des jeux CHSH et du carré magique.
Cette thèse se trouve à l'intersection de la théorie des matrices aléatoires, des probabilités libres et de la théorie de l'information quantique. La plus grande partie des travaux présentés se concentrent sur les aspects probabilistes de l'information quantique et, en particulier, sur l'usage des matrices aléatoires dans différents modèles en théorie quantique. Une autre partie de cette thèse est dédiée à la théorie des probabilités libres et à ses liens avec les matrices aléatoires et l'information quantique. En théorie quantique de l'information, il existe différents modèles de matrices densités aléatoires. On s'intéresse, dans l'esprit de la théorie des matrices aléatoires, au comportement asymptotique des matrices densités, dans la limite où la taille du système converge vers l'infini. Le point de vue pris dans cette thèse est celui des systèmes quantiques ouverts, où l'espace qui nous intéresse est couplé avec l'environnement et le système composé se trouve dans un état pur uniforme. En prenant la trace partielle sur l'environnement, on obtient des matrices densités aléatoires que l'on étudie dans deux régimes asymptotiques. En exploitant des liens avec l'ensemble des matrices aléatoires dites de Wishart, on obtient les densités spectrales limites et les fluctuations des valeurs propres extrémales. En collaboration avec Clément Pellegrini, on étudie des interactions répétées entre un système quantique et une chaîne de systèmes auxiliaires. Nous avons introduit des éléments aléatoires dans ce modèle, soit en considérant que les états de la chaîne sont des variables indépendantes et identiquement distribuées, soit en choisissant, à chaque interaction, une matrice unitaire d'interaction aléatoire uniforme. On s'intéresse aux propriétés asymptotiques des matrices, après un grand nombre d'interactions. Au passage, on introduit un nouveau modèle de matrices densités aléatoires que l'on compare avec les modèles existants dans la littérature. Un problème qui occupe une place centrale dans cette thèse est la conjecture de Nielsen sur la catalyse en théorie quantique de l'information. En collaboration avec Guillaume Aubrun, nous avons progressé vers la preuve de cette conjecture et nous l'avons par la suite généralisée dans différentes directions. L'outil principal utilisé dans ces travaux nous vient de la théorie des probabilités : la théorie des grandes déviations nous permet de comparer stochastiquement des puissances de convolution des mesures de probabilités. Les techniques introduites et le lien avec la théorie des grandes déviations nous ont permis de voir ce problème sous un autre angle et de donner aux théoriciens de l'information quantique un outil de travail puissant. Enfin, toujours en lien avec les matrices aléatoires, cette thèse a donné lieu à deux travaux en probabilités libres. Les ensembles de matrices aléatoires sont des exemples importants et simples où l'on peut observer l'indépendance libre; il est donc naturel de se demander s'il est possible d'obtenir la notion de liberté avec des matrices déterministes. Une telle construction a été proposée par Philippe Biane, en utilisant des sommes de transpositions dans l'algèbre du groupe symétrique. Avec Florent Benaych-Georges, on a pu généraliser les résultats de P. Biane à des cycles quelconques. Notre approche est combinatoire ce qui nous a permis d'aboutir à des formules explicites pour les moments et les cumulants libres des variables à la limite. Grâce à cette même approche nous avons élaboré un modèle analogue en probabilités classiques en remplaçant le groupe symétrique par le groupe abélien des parties d'un ensemble fini, muni de l'opération de différence symétrique. En collaboration avec Stéphane Attal, nous avons construit une approximation de l'espace de Fock libre (qui joue un rôle central en théorie des probabilités non-commutatives) par un produit libre dénombrable d'espaces discrets. Cette idée généralise au cas libre une construction similaire pour l'espace de Fock symétrique, introduite et étudié par S. Attal. En même temps nous avons obtenu une approximation des opérateurs fondamentaux de création, d'annihilation et de jauge par des opérateurs construits à partir des matrices de taille 2. En utilisant ces constructions sont ensuite utilisées pour retrouver quelques approximations connues du mouvement brownien libre et du processus de Poisson libre. Tous ces résultats se généralisent au cas des espaces de Fock de multiplicité supérieure, qui permettent d'approcher des processus multidimensionnels. En conclusion, l'ensemble des travaux scientifiques présentés dans cette thèse se situe à l'intersection de trois grandes directions: les matrices aléatoires, les probabilités libres et la théorie quantique de l'information, l'accent étant mis sur les interactions et sur les liens entre ces domaines.
Cette thèse se trouve à l'intersection de la théorie des matrices aléatoires, des probabilités libres et de la théorie de l'information quantique. La plus grande partie des travaux présentés se concentrent sur les aspects probabilistes de l'information quantique et, en particulier, sur l'usage des matrices aléatoires dans différents modèles en théorie quantique. Une autre partie de cette thèse est dédiée à la théorie des probabilités libres et à ses liens avec les matrices aléatoires et l'information quantique. En théorie quantique de l'information, il existe différents modèles de matrices densités aléatoires. On s'intéresse, dans l'esprit de la théorie des matrices aléatoires, au comportement asymptotique des matrices densités, dans la limite où la taille du système converge vers l'infini. Le point de vue pris dans cette thèse est celui des systèmes quantiques ouverts, où l'espace qui nous intéresse est couplé avec l'environnement et le système composé se trouve dans un état pur uniforme. En prenant la trace partielle sur l'environnement, on obtient des matrices densités aléatoires que l'on étudie dans deux régimes asymptotiques. En exploitant des liens avec l'ensemble des matrices aléatoires dites de Wishart, on obtient les densités spectrales limites et les fluctuations des valeurs propres extrémales. En collaboration avec Clément Pellegrini, on étudie des interactions répétées entre un système quantique et une chaîne de systèmes auxiliaires. Nous avons introduit des éléments aléatoires dans ce modèle, soit en considérant que les états de la chaîne sont des variables indépendantes et identiquement distribuées, soit en choisissant, à chaque interaction, une matrice unitaire d'interaction aléatoire uniforme. On s'intéresse aux propriétés asymptotiques des matrices, après un grand nombre d'interactions. Au passage, on introduit un nouveau modèle de matrices densités aléatoires que l'on compare avec les modèles existants dans la littérature. Un problème qui occupe une place centrale dans cette thèse est la conjecture de Nielsen sur la catalyse en théorie quantique de l'information. En collaboration avec Guillaume Aubrun, nous avons progressé vers la preuve de cette conjecture et nous l'avons par la suite généralisée dans différentes directions. L'outil principal utilisé dans ces travaux nous vient de la théorie des probabilités : la théorie des grandes déviations nous permet de comparer stochastiquement des puissances de convolution des mesures de probabilités. Les techniques introduites et le lien avec la théorie des grandes déviations nous ont permis de voir ce problème sous un autre angle et de donner aux théoriciens de l'information quantique un outil de travail puissant. Enfin, toujours en lien avec les matrices aléatoires, cette thèse a donné lieu à deux travaux en probabilités libres. Les ensembles de matrices aléatoires sont des exemples importants et simples où l'on peut observer l'indépendance libre; il est donc naturel de se demander s'il est possible d'obtenir la notion de liberté avec des matrices déterministes. Une telle construction a été proposée par Philippe Biane, en utilisant des sommes de transpositions dans l'algèbre du groupe symétrique. Avec Florent Benaych-Georges, on a pu généraliser les résultats de P. Biane à des cycles quelconques. Notre approche est combinatoire ce qui nous a permis d'aboutir à des formules explicites pour les moments et les cumulants libres des variables à la limite. Grâce à cette même approche nous avons élaboré un modèle analogue en probabilités classiques en remplaçant le groupe symétrique par le groupe abélien des parties d'un ensemble fini, muni de l'opération de différence symétrique. En collaboration avec Stéphane Attal, nous avons construit une approximation de l'espace de Fock libre (qui joue un rôle central en théorie des probabilités non-commutatives) par un produit libre dénombrable d'espaces discrets. Cette idée généralise au cas libre une construction similaire pour l'espace de Fock symétrique, introduite et étudié par S. Attal. En même temps nous avons obtenu une approximation des opérateurs fondamentaux de création, d'annihilation et de jauge par des opérateurs construits à partir des matrices de taille 2. En utilisant ces constructions sont ensuite utilisées pour retrouver quelques approximations connues du mouvement brownien libre et du processus de Poisson libre. Tous ces résultats se généralisent au cas des espaces de Fock de multiplicité supérieure, qui permettent d'approcher des processus multidimensionnels. En conclusion, l'ensemble des travaux scientifiques présentés dans cette thèse se situe à l'intersection de trois grandes directions: les matrices aléatoires, les probabilités libres et la théorie quantique de l'information, l'accent étant mis sur les interactions et sur les liens entre ces domaines.
Le développement de machines quantiques de tailles modestes accessibles en ligne permet aujourd'hui de réaliser des expériences sur des calculateurs à distance. L'avantage de l'informatique quantique repose sur des phénomènes strictement non classiques, tels que la superposition et l'intrication, qui sont des ressources maintenant bien connues. Le phénomène non-classique de la contextualité est peut-être moins bien établi bien qu'il ouvre aussi des perspectives très intéressntes à travers de nombreuses applications telles que la cryptographie quantique, les codes d'accès aléatoires, les codes correcteurs d'erreurs et l'avantage du coût de la mémoire pour la simulation des mesures quantiques. L'objectif de cette thèse est triple : développer de nouveaux tests résistants au bruit pour démontrer la contextualité avec des ordinateurs quantiques bruités d'échelle intermédiaire ; concevoir des algorithmes quantiques pour calculer les limites classiques de ces tests, avec une meilleure complexité par rapport aux algorithmes existants ; interpreter les invariants algébriques, utilisés pour distinguer les classes d'intrication, en termes d'observables à base d'opérateurs de Pauli. À ces fins, l'utilisation de configurations géométriques telles que les espaces polaires symplectiques et leurs sous-géométries est largement exploitée, permettant d'établir un lien solide entre le domaine, relativement ancien des géométries finies, et les concepts plus récents de la théorie de l'information quantique. Pour le premier objectif, nous utilisons l'apport de la géométrie pour fournir des tests de contextualité qui violent largement les limites classiques sur tous les ordinateurs quantiques IBM. Ces tests démontrent empiriquement l'absence de modèles à variables cachées non contextuelles décrivant le système sous-jacent. C'est un résultat d'intérêt ontologique. Plus précisément, il s'agit de la première violation connue du jeu de pseudotélépathie de Mermin sur de telles machines, et des plus grandes violations du test de Rio Negro. Concernant le deuxième objectif, nous nous appuyons sur les symétries de nos géométries pour construire un algorithme quantique basé sur l'algorithme de recherche de Grover. Cet algorithme identifie une affectation optimale de variables cachées classiques avec une complexité comparable à l'algorithme de Grover. Un tel avantage algorithmique est intéressant dans une grande famille de problèmes, connus sous le nom de Max Lin 2, où plusieurs contraintes sur un ensemble de données ne peuvent pas être satisfaites simultanément. Ainsi, l'étude de la contextualité - qui peut être vue comme une limitation de la satisfaction logique pour décrire les systèmes physiques - peut apporter de nouvelles perspectives à des problèmes où la satisfaction d'instruction logique simultanée n'est pas viable. Enfin, pour le troisième objectif, nous proposons de nombreuses connexions entre les géométries finies et les invariants algébriques, en commençant par des liens entre les quadrangles généralisés et les invariants cubiques de Cartan, puis en montrant comment les géométries maximalement mixtes permettent de reconstruire les polynômes de Mermin, et finalement en décrivant les sous-ensembles minimaux d'opérateurs de Pauli qui permettent de calculer les hyperdéterminants. On peut ainsi, grâce à ces invariants, identifier la classe d'intrication de systèmes de qubits N=2,3,4 par des mesures sans avoir besoin d'une tomographie complète du système. En résumé dans cette thèse, nous abordons une grande variété de questions à l'intersection de la géométrie finie et de l'informatique quantique - de la conception de tests de contextualité à l'étude de la non-localité à travers des invariants algébriques en passant par le calcul quantique de bornes classiques. Les idées proposées dans ce travail pourront être utiles à la fois pour l'étude des fondements de la mécanique quantique et pour son application à l'informatique quantique.
Protocoles de chiffrement quantiques de plusieurs parties en environnements réalistes Cette thèse se situe à l’interface entre la théorie quantique et les expériences, en mettant l’accent sur les protocoles pratiques qui peuvent être mises en place en utilisant la technologie présente. Notre objectif est de contribuer à la construction d’un cadre général pour la conception et la mise en oeuvre de schémas de chiffrement quantiques qui permettront d’améliorer la sécurité des futurs réseaux de télécommunication. En outre, cette thèse veut avancer la recherche pertinente sur la physique quantique et l’informatique, en améliorant notre compréhension du phénomène d’intrication. Les corrélations des états intriqués ne peuvent pas être reproduites par des moyens classiques, ce qui permet d’effectuer des tâches (par exemple la téléportation et le codage super-dense) qui sont autrement impossibles. Il est donc d’une importance majeure d’être capables de vérifier si un état quantique est intriqué. Dans cette thèse, nous montrons comment vérifier efficacement si une source physique peut créer des états intriqués multipartites et les partager avec de nombreuses parties, dont certains sont malhonnêtes et collaborent avec la source. Ce protocole pourrait s’avérer essentiel pour tout type de calcul quantique entre les parties méfiantes et pourrait aussi faciliter la délégation sécurisée des tâches de calcul aux serveurs quantiques puissants qui ne sont pas fiables. Finalement, nous étudions le lien entre la théorie des jeux et la non-localité quantique, dans le cadre de jeux bayésiens. Nous examinons comment l’intrication partagé aide les joueurs gagner un jeu avec une probabilité plus élevée que les ressources classiques pourraient atteindre.
Contextualité quantique, géométries finies & informatique quantique Le développement de machines quantiques de tailles modestes accessibles en ligne permet aujourd'hui de réaliser des expériences sur des calculateurs à distance. L'avantage de l'informatique quantique repose sur des phénomènes strictement non classiques, tels que la superposition et l'intrication, qui sont des ressources maintenant bien connues. Le phénomène non-classique de la contextualité est peut-être moins bien établi bien qu'il ouvre aussi des perspectives très intéressntes à travers de nombreuses applications telles que la cryptographie quantique, les codes d'accès aléatoires, les codes correcteurs d'erreurs et l'avantage du coût de la mémoire pour la simulation des mesures quantiques. L'objectif de cette thèse est triple : développer de nouveaux tests résistants au bruit pour démontrer la contextualité avec des ordinateurs quantiques bruités d'échelle intermédiaire ; concevoir des algorithmes quantiques pour calculer les limites classiques de ces tests, avec une meilleure complexité par rapport aux algorithmes existants ; interpreter les invariants algébriques, utilisés pour distinguer les classes d'intrication, en termes d'observables à base d'opérateurs de Pauli. À ces fins, l'utilisation de configurations géométriques telles que les espaces polaires symplectiques et leurs sous-géométries est largement exploitée, permettant d'établir un lien solide entre le domaine, relativement ancien des géométries finies, et les concepts plus récents de la théorie de l'information quantique. Pour le premier objectif, nous utilisons l'apport de la géométrie pour fournir des tests de contextualité qui violent largement les limites classiques sur tous les ordinateurs quantiques IBM. Ces tests démontrent empiriquement l'absence de modèles à variables cachées non contextuelles décrivant le système sous-jacent. C'est un résultat d'intérêt ontologique. Plus précisément, il s'agit de la première violation connue du jeu de pseudotélépathie de Mermin sur de telles machines, et des plus grandes violations du test de Rio Negro. Concernant le deuxième objectif, nous nous appuyons sur les symétries de nos géométries pour construire un algorithme quantique basé sur l'algorithme de recherche de Grover. Cet algorithme identifie une affectation optimale de variables cachées classiques avec une complexité comparable à l'algorithme de Grover. Un tel avantage algorithmique est intéressant dans une grande famille de problèmes, connus sous le nom de Max Lin 2, où plusieurs contraintes sur un ensemble de données ne peuvent pas être satisfaites simultanément. Ainsi, l'étude de la contextualité - qui peut être vue comme une limitation de la satisfaction logique pour décrire les systèmes physiques - peut apporter de nouvelles perspectives à des problèmes où la satisfaction d'instruction logique simultanée n'est pas viable. Enfin, pour le troisième objectif, nous proposons de nombreuses connexions entre les géométries finies et les invariants algébriques, en commençant par des liens entre les quadrangles généralisés et les invariants cubiques de Cartan, puis en montrant comment les géométries maximalement mixtes permettent de reconstruire les polynômes de Mermin, et finalement en décrivant les sous-ensembles minimaux d'opérateurs de Pauli qui permettent de calculer les hyperdéterminants. On peut ainsi, grâce à ces invariants, identifier la classe d'intrication de systèmes de qubits N=2,3,4 par des mesures sans avoir besoin d'une tomographie complète du système. En résumé dans cette thèse, nous abordons une grande variété de questions à l'intersection de la géométrie finie et de l'informatique quantique - de la conception de tests de contextualité à l'étude de la non-localité à travers des invariants algébriques en passant par le calcul quantique de bornes classiques. Les idées proposées dans ce travail pourront être utiles à la fois pour l'étude des fondements de la mécanique quantique et pour son application à l'informatique quantique.
Nous presentons dans ce travail plusieurs resultats dans differents domaines de l'information quantique. Apres une premiere partie ou nous proposons une introduction au domaine, nous proposons des caracterisations simples et efficaces du phenomene de l'intrication des etats purs. Les deux formes de separabilite etudiees sont la separabilite totale et la p-q separabilite. Ces caracterisations nous ont permis de donner des algorithmes optimaux de detection de la separabilite ayant un gain quadratrique par rapport aux methodes connues. La troisieme partie s'interesse aux jeux quantiques. Nous presentons tout d'abord une analyse fine des jeux octaux classiques et donnons une strategie optimale pour le jeu des dominos. Nous proposons ensuite une quantisation de certains jeux combinatoires, definissant ainsi la famille des jeux octaux quantiques. Nous presentons ainsi un modele formel permettant de parler des jeux quantiques a information totale et proposons une approche qui utilise des pieges pour des jeux quantiques tres etudies, appeles jeux de des a distance. La derniere partie etudie des problemes d'optimisation, en developpant pour cela des outils optimaux de recherche de minima. Ces outils nous ont permis d'analyser la complexite en requetes de certains problemes de graphes. Nous avons ainsi trouve des algorithmes quantiques pour les problemes de connectivite, forte connectivite, arbre couvrant de poids minimal et plus courts chemins a une source donnee. Puis, nous avons prouve leur optimalite en utilisant des techniques de bornes inferieures, determinant ainsi les limites du facteur de gain qu'offre l'informatique quantique pour resoudre ce probleme.