Ce mémoire met en évidence un lien formel entre les problèmes physiques de détection d'intrication et les classes de complexité de l'informatique théorique. Plus particulièrement, nous établissons une correspondance entre la plupart des classes de complexité naturelles issues de preuves interactives quantiques (incluant BQP, QMA, QMA(2), QSZK, et QIP), et une intrication ou un problème de détection de corrélation qui est complet pour cette classe. En ce sens, nous pouvons dire que l'intrication, ou le problème de détection de corrélation, capture la puissance expressive de chaque classe de complexité de preuve interactive quantique et que le contraste entre de tels problèmes donne une idée sur les différences entre les classes de preuves interactives quantiques. Il est démontré que la difficulté de la détection d'intrication varie considérablement du fait que la mesure de distance utilisée soit la distance de trace ou LOCC unidirectionnel. Nous fournissons également l'analyse d'un problème similaire, et montrons que celui-ci est décidable par un système de preuve interactive quantique (de deux messages) tout en étant NP-dur ainsi que QSZK-dur, le premier exemple non trivial d'un tel problème.
Ce mémoire met en évidence un lien formel entre les problèmes physiques de détection d'intrication et les classes de complexité de l'informatique théorique. Plus particulièrement, nous établissons une correspondance entre la plupart des classes de complexité naturelles issues de preuves interactives quantiques (incluant BQP, QMA, QMA(2), QSZK, et QIP), et une intrication ou un problème de détection de corrélation qui est complet pour cette classe. En ce sens, nous pouvons dire que l'intrication, ou le problème de détection de corrélation, capture la puissance expressive de chaque classe de complexité de preuve interactive quantique et que le contraste entre de tels problèmes donne une idée sur les différences entre les classes de preuves interactives quantiques. Il est démontré que la difficulté de la détection d'intrication varie considérablement du fait que la mesure de distance utilisée soit la distance de trace ou LOCC unidirectionnel. Nous fournissons également l'analyse d'un problème similaire, et montrons que celui-ci est décidable par un système de preuve interactive quantique (de deux messages) tout en étant NP-dur ainsi que QSZK-dur, le premier exemple non trivial d'un tel problème.
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.
Protocoles pratiques pour les réseaux de communication quantique Dans cette thèse, nous étudions les réseaux des états optiques quantiques intriqués avec différents degrés de complexité, avec une attention particulière portée à leur application dans des scénarios de communication quantique. Le but de la communication quantique est de permettre à deux ou plusieurs parties de communiquer d'une façon qui serait impossible avec de la technologie classique. L'archétype de ce domaine est la distribution de clé quantique ou quantum key distribution (QKD), qui permet à deux agents de partager une clé aléatoire secrète pour effectuer des communications sécurisées, en empêchant, au même temps, qu'un troisième agent malveillant puisse obtenir connaissance de leur clé. Dans ce manuscrit, cependant, nous explorons des scénarios de communication quantique qui vont au-delà de la QKD standard afin de tester les nombreuses possibilités offertes par les réseaux de dispositifs quantiques interconnectés, aussi appelés internet quantique. Spécifiquement, nous présentons trois types de réseaux quantiques, qui correspondent à trois niveaux de complexité d'internet quantique. Dans chaque niveau, nous décrivons le scénario de communication, les exigences physiques nécessaires pour construire l'architecture spécifique et un nouveau protocole qui ne peut pas être reproduit sans des ressources quantiques. Dans cette document, nous veillons particulièrement à la "praticité" des protocoles, notamment le fait que leur implémentation doit être possible dans des conditions réalistes avec technologie existante, au moins comme preuve du principe. Le premier concerne un protocole quantique à preuves interactives qui montre pour la première fois une preuve expérimentale d'un avantage quantique dans un cadre interactif. Dans ce scénario, il y a un prouveur avec de la puissance calculatoire illimitée qui veut convaincre un vérifieur honnête de l'existence d'une certaine solution d'un problème mathématique complexe, en lui envoyant une partie de la preuve sous forme d'états quantiques. Notre construction permet au vérifieur de vérifier l'assertion du prouveur sans recevoir la solution entière. Nous prouvons que sans ressources quantiques, le protocole de vérification exigerait un temps exponentiel en la taille de la solution, menant à un avantage quantique en terme de temps de calcul, avantage que nous avons démontré dans notre laboratoire. Le deuxième porte sur un protocole de vote électronique qui exploite un état quantique multipartite intriqué non fiable pour réaliser une élection sans s'appuyer sur des autorités électorales, dont le résultat peut être vérifié publiquement sans compromettre la robustesse de la construction et qui peut être implémenté aisément avec les technologies de pointe existantes pour un petit nombre de votant. À l'invers des résultats précédents, notre protocole n'exige pas une émission simultanée et marche aussi dans des scénarios bruyants, où la sécurité est limitée par la fidélité de l'état quantique utilisé. Enfin, nous simulons des états comprimés de la lumière de nombreux modes comme des réseaux quantique Gaussien à variables continues avec des topologies complexes, nous caractérisons leur corrélations et nous estimons l'intensification de leur coût pendant que les réseaux grandissent avec une théorie de ressource de compression. Nous prouvons un résultat qui permet de renforcer l'intrication entre deux nœuds du réseau si on mesure les chemins multiples qui les connectent et nous utilisons cet effet pour concevoir un protocole de routage d'intrication dont les performance sont particulièrement efficace dans des réseaux complexes grands.
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.
Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM.
Cette thèse est consacrée à la complexité basée sur le paradigme des preuves interactives. Les classes ainsi définies ont toutes en commun qu’un ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un vérificateur, de puissance bornée, de l’appartenance d’un mot à un langage. Nous abordons ici le modèle classique, où les participants sont des machines de Turing, et le modèle quantique, où ceux-ci sont des circuits quantiques. La revue de littérature que comprend cette thèse s’adresse à un lecteur déjà familier avec la complexité et l’informatique quantique. Cette thèse présente comme résultat la caractérisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les différentes classes sont présentées dans un ordre permettant d’aborder aussi facilement que possible les classes interactives. Le premier chapitre est consacré aux classes de base de la complexité ; celles-ci seront utiles pour situer les classes subséquemment présentées. Les chapitres deux et trois présentent respectivement les classes à un et à plusieurs prouveurs. La présentation du résultat ci-haut mentionné est l’objet du chapitre quatre.
Interaction à deux joueurs en informatique quantique : primitives cryptographiques et complexité en requêtes Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM.