Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Multi-Prover and parallel repetition in non-classical interactive games

Tommy Payette

Published Aug 1, 2009• 0 citations
Publisher

Abstract

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

DOI
10.71781/9824

Related papers

Complexity measures through the lens of two-player games and signatures of the hypercube

Anupa Sunny

Les mesures complexes à travers le prisme des jeux à deux joueurs et des signatures de l'hypercube Les mesures de complexité des fonctions booléennes capturent divers aspects de la difficulté du calcul d'une fonction et leur étude consiste à trouver des connexions entre différentes mesures de complexité. Dans la première partie de cette thèse, nous introduisons et étudions la complexité de jeux de certificats, une mesure de complexité basée sur la probabilité de gagner un jeu dans lequel deux joueurs reçoivent des entrées avec des valeurs de fonctions différentes et doivent produire un indice i pour lequel leurs entrées diffèrent, sans communiquer. Nous donnons des bornes supérieures et inférieures pour les stratégies à base de pièces privées, de pièces publiques, d'intrication partagée et de non-signalisation, et nous prouvons quelques résultats de séparations. D'une part, nous montrons que la complexité dans le cas des pièces publiques est majorée par les complexités de requête aléatoire et de certificat. D'autre part, nous montrons qu'elle est minorée par la complexité fractionnelle de certificat, ce qui en fait un bon candidat pour trouver des bornes inférieures fortes sur la complexité de requête aléatoire. La complexité dans le cas des pièces privées est minorée par la complexité de requête aléatoire à erreur nulle. Nous utilisons la non-signalisation, une notion d'information quantique, pour minorer par n la complexité de jeux de certificats quantiques de la fonction OR, dont la complexité de requête quantique est de Θ(√n), puis nous montrons que ce "goulot d'étranglement de non-signalisation" s'applique à toutes les fonctions à sensibilité, à sensibilité de bloc ou à sensibilité de bloc fractionnaire élevée. Nous considérons également la version mono-bit des jeux de certificats, où les entrées des deux joueurs sont restreints à une distance de Hamming de 1. Nous prouvons que la version mono-bit de la complexité de jeux de certificats avec aléa partagé est égale à la sensibilité à un facteur constant près, ce qui donne une nouvelle caractérisation de la sensibilité. D'autre part, la version mono-bit de la complexité de jeux de certificats avec aléa privé est égale à λ2, où λ est la sensibilité spectrale. Dans la deuxième partie de cette thèse, nous revisitons la célèbre preuve de la conjecture de la sensibilité par Hao Huang. En utilisant des techniques spectrales, Huang a prouvé que tout sous-graphe de l'hypercube Hn de dimension n induit sur plus de la moitié des sommets a un degré maximal d'au moins √n. Combiné avec des travaux antérieurs, ce résultat a complété une preuve de la conjecture de la sensibilité. Nous en donnons une preuve alternative en utilisant seulement la dépendance linéaire des vecteurs associés aux sommets de l'hypercube. Notre approche permet de mieux comprendre les propriétés structurelles du sous-graphe induit, en plus du plus grand degré. En particulier, nous prouvons que dans tout sous-graphe induit de Hn avec plus de la moitié du nombre de sommets, il existe deux sommets, l'un de parité impaire et l'autre de parité paire, chacun ayant au moins n sommets à une distance au plus égale à 2. Comme application, nous montrons que pour toute fonction booléenne f, le degré polynomial est majoré par le produit de la sensibilité 0 et de la sensibilité 1, s0(f)s1(f), une affirmation strictement plus forte qui implique le théorème de Huang. Nous obtenons également des relations structurelles pour les sous-graphes induits à distance 3. Un ingrédient clé de la preuve de Huang était des hypercubes signés avec la propriété que chaque cycle de longueur 4 est affecté d'un signe négatif. Nous examinons en détail cette signature et donnons une signature quasi-optimale qui utilise le nombre minimum de bords négatifs tout en garantissant que chaque cycle de longueur 4 est négatif. Ce problème s'avère être lié à l'un des problèmes d'Erdös sur le plus grand sous-graphe de l'hypercube exempt de 4-cycles.

•Feb 15, 2023•0 citations

The use of entanglement in non-cooperative games, and the computational power of indefinite causal order

Pierre Pocreau

L'utilisation de l'intrication dans les jeux non-coopératifs, et la puissance de calcul des ordres causaux indéfinis Cette thèse explore deux phénomènes fondamentaux en physique : la non-localité, étudiée à travers l'utilisation de l'intrication dans les jeux non coopératifs; et la possibilité d'ordres causaux indéfinis, remettant en question l'hypothèse courante selon laquelle les procédures computationnelles doivent être exécutées dans un ordre séquentiel bien défini.Nos objectifs sont doubles. Nous cherchons d'abord à mieux comprendre l'utilisation de l'intrication dans les jeux multipartites avec intérêts conflictuels. Ces situations sont rarement abordées en théorie de l'information quantique, mais elles sont centrales en théorie des jeux, où intervient la notion d'équilibre de Nash. Renforcer le lien entre ces deux domaines pourrait offrir de nouvelles perspectives sur l'utilisation de l'intrication dans des scénarios non locaux. Nous analysons en particulier deux types de ressources quantiques : l'une où les joueurs ont un accès direct à un état quantique intriqué, et une seconde, que nous introduisons ici, où ils reçoivent des conseils classiques issus de dispositifs quantiques. Bien que ces deux ressources soient équivalentes dans des contextes coopératifs, nous montrons qu'elles diffèrent dans les jeux à intérêts conflictuels, menant à des équilibres de Nash distincts et à des solutions potentiellement différentes en termes de bien-être social.Dans la seconde partie, nous cherchons à mieux comprendre la puissance de calcul des ordres causaux indéfinis. Alors que le modèle standard des circuits quantiques suppose que les opérations sont appliquées selon un ordre causal bien défini, la possibilité de relaxer cette contrainte pour permettre des procédures de calcul causalement indéfinis a récemment suscité un vif intérêt, notamment via le formalisme des supermaps quantiques. Plusieurs avantages ad hoc, tant computationnels qu'en traitement de l'information, ont été mis en évidence, soulevant la question de savoir si de tels avantages peuvent être démontrés dans un cadre unifié de théorie de la complexité. Les supermaps étant mieux comprises comme un modèle de calcul utilisant des boîtes noires, nous commençons par étendre la notion de complexité de requête des fonctions booléennes au cadre computationnel généralisé des supermaps, tant dans le cas classique que quantique. Ensuite, en utilisant des supermaps à plusieurs tours (multi-round), nous définissons également des protocoles de communication bipartites et multipartites avec communication causalement indéfinie, ainsi que la notion généralisée de complexité de communication des fonctions booléennes qui en découle. En étendant ces différentes mesures de complexité aux scénarios causalement indéfinis, nous évaluons les limites et les avantages des ordres causaux indéfinis dans un cadre rigoureux de théorie de la complexité, le même cadre dans lequel sont habituellement formulées les séparations entre ordinateurs classiques et quantiques.

•Oct 6, 2025•0 citations

Interactive Quantum Information Theory

Dave Touchette

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.

•Nov 26, 2014•0 citations

Quantum cryptographic primitives in realistic conditions

Anna Pappa

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.

•Jul 10, 2014•0 citations

Two-player interaction in quantum computing : cryptographic primitives & query complexity

Loïck Magnin

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.

•Dec 5, 2011•1 citation

Compatibility and Nonlocality

Faedi Loulidi

Compatibilité et non-localité L'un des concepts majeurs introduit par la théorie quantique est celui de la compatibilité des mesures quantiques. Il existe certains types de mesures qui ne peuvent pas être effectuées en même temps. Ainsi, on dit que les mesures sont compatibles si on peut mesurer en même temps et d'autre sont incompatibles. L'autre concept majeur de la mécanique quantique est celui de la nonlocalité qui est l'un des concepts les plus contre-intuitifs de la physique quantique. Ce concept majeur est dû à John Bell qui a montré que la mécanique quantique est intrinsèquement non locale. Ainsi, on parle de violation des inégalités de Bell par la mécanique quantique. Aujourd'hui, la nonlocalité est comprise à travers les jeux nonlocaux. Un jeux nonlocal consiste en deux joueurs ou plus Alice et Bob jouant contre un arbitre. Ce dernier posera un certain nombre de questions aux joueurs qui devront générer un certain nombre de réponses en utilisant une stratégie classique ou quantique. Il se trouve que le maximum des réponses qu'Alice et Bob peuvent générer est intrinsèquement relié à une norme tensorielle caractérisant le jeu. Dans ce formalisme, l'utilisation des stratégies classiques est relié à la norme de la matrice du jeux lui-même, ainsi la violation des inégalités de Bell se traduit par une inégalité stricte entre les normes tensorielles. Le but de cette thèse consiste à comprendre l'incompatibilité des mesures quantiques ainsi que le lien avec les inégalités de Bell. Dans un premier temps, nous avons introduit la compatibilité des mesures quantiques sous un nouveau point de vue, et analysé les types de bruit qu'on peut effectuer à fin de rendre le système compatible. Ce nouveau point de vue consiste à comprendre et à analyser l'effet de la dimension de l'espace de Hilbert sur l'incompatibilité des mesures. Par ailleurs à fin de rendre des mesures compatibles, on peut introduire l'effet d'un bruit. Comme application, certains états connu sous le nom de MUB sont de nature incompatible, on montre même si on rajoute du bruit aux MUB celle-ci restant incompatible, il existe une isométrie et un espace de Hilbert de dimension plus petite rendant les MUB compatibles. Dans un deuxième temps, nous avons analysé le lien intrinsèque reliant l'incompatibilité des mesures quantique et la violation des inégalités de Bell. Pour cela, on a considéré le cadre des jeux nonlocaux, où les mesures d'Alice sont fixées. Il est connu qu'une violation des inégalités de Bell nécessite l'utilisation des mesures incompatibles. Par ailleurs, si Alice veut savoir si elle observera une violation des inégalités de Bell si elle utilise des mesures incompatibles. Pour cela, elle doit calculer deux normes tensorielles d'un tenseur construit à partir de ses mesures. Ces normes tensorielles vont caractériser d'une part la compatibilité des mesures d'Alice et d'autre part la violation des inégalités de Bell. Dans ce cadre naturel, comprendre le lien entre incompatibilité des mesures quantiques et la violation des inégalités de Bell, revient à comparer les deux normes tensorielles. Or, il se trouve que pour le jeu CHSH ces deux normes sont égales, mais on peut montrer généralement qu'elles ne le sont pas. On peut se demander s'il existe d'autre types de jeux satisfaisant cette égalité des normes tensorielles ? Il se trouve que nous avons montré qu'avec des conditions suffisantes, seul le jeux CHSH à constante multiplicative près donne l'égalité entre les normes tensorielles.

•Feb 22, 2023•0 citations
Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.
Les mesures complexes à travers le prisme des jeux à deux joueurs et des signatures de l'hypercube Les mesures de complexité des fonctions booléennes capturent divers aspects de la difficulté du calcul d'une fonction et leur étude consiste à trouver des connexions entre différentes mesures de complexité. Dans la première partie de cette thèse, nous introduisons et étudions la complexité de jeux de certificats, une mesure de complexité basée sur la probabilité de gagner un jeu dans lequel deux joueurs reçoivent des entrées avec des valeurs de fonctions différentes et doivent produire un indice i pour lequel leurs entrées diffèrent, sans communiquer. Nous donnons des bornes supérieures et inférieures pour les stratégies à base de pièces privées, de pièces publiques, d'intrication partagée et de non-signalisation, et nous prouvons quelques résultats de séparations. D'une part, nous montrons que la complexité dans le cas des pièces publiques est majorée par les complexités de requête aléatoire et de certificat. D'autre part, nous montrons qu'elle est minorée par la complexité fractionnelle de certificat, ce qui en fait un bon candidat pour trouver des bornes inférieures fortes sur la complexité de requête aléatoire. La complexité dans le cas des pièces privées est minorée par la complexité de requête aléatoire à erreur nulle. Nous utilisons la non-signalisation, une notion d'information quantique, pour minorer par n la complexité de jeux de certificats quantiques de la fonction OR, dont la complexité de requête quantique est de Θ(√n), puis nous montrons que ce "goulot d'étranglement de non-signalisation" s'applique à toutes les fonctions à sensibilité, à sensibilité de bloc ou à sensibilité de bloc fractionnaire élevée. Nous considérons également la version mono-bit des jeux de certificats, où les entrées des deux joueurs sont restreints à une distance de Hamming de 1. Nous prouvons que la version mono-bit de la complexité de jeux de certificats avec aléa partagé est égale à la sensibilité à un facteur constant près, ce qui donne une nouvelle caractérisation de la sensibilité. D'autre part, la version mono-bit de la complexité de jeux de certificats avec aléa privé est égale à λ2, où λ est la sensibilité spectrale. Dans la deuxième partie de cette thèse, nous revisitons la célèbre preuve de la conjecture de la sensibilité par Hao Huang. En utilisant des techniques spectrales, Huang a prouvé que tout sous-graphe de l'hypercube Hn de dimension n induit sur plus de la moitié des sommets a un degré maximal d'au moins √n. Combiné avec des travaux antérieurs, ce résultat a complété une preuve de la conjecture de la sensibilité. Nous en donnons une preuve alternative en utilisant seulement la dépendance linéaire des vecteurs associés aux sommets de l'hypercube. Notre approche permet de mieux comprendre les propriétés structurelles du sous-graphe induit, en plus du plus grand degré. En particulier, nous prouvons que dans tout sous-graphe induit de Hn avec plus de la moitié du nombre de sommets, il existe deux sommets, l'un de parité impaire et l'autre de parité paire, chacun ayant au moins n sommets à une distance au plus égale à 2. Comme application, nous montrons que pour toute fonction booléenne f, le degré polynomial est majoré par le produit de la sensibilité 0 et de la sensibilité 1, s0(f)s1(f), une affirmation strictement plus forte qui implique le théorème de Huang. Nous obtenons également des relations structurelles pour les sous-graphes induits à distance 3. Un ingrédient clé de la preuve de Huang était des hypercubes signés avec la propriété que chaque cycle de longueur 4 est affecté d'un signe négatif. Nous examinons en détail cette signature et donnons une signature quasi-optimale qui utilise le nombre minimum de bords négatifs tout en garantissant que chaque cycle de longueur 4 est négatif. Ce problème s'avère être lié à l'un des problèmes d'Erdös sur le plus grand sous-graphe de l'hypercube exempt de 4-cycles.
L'utilisation de l'intrication dans les jeux non-coopératifs, et la puissance de calcul des ordres causaux indéfinis Cette thèse explore deux phénomènes fondamentaux en physique : la non-localité, étudiée à travers l'utilisation de l'intrication dans les jeux non coopératifs; et la possibilité d'ordres causaux indéfinis, remettant en question l'hypothèse courante selon laquelle les procédures computationnelles doivent être exécutées dans un ordre séquentiel bien défini.Nos objectifs sont doubles. Nous cherchons d'abord à mieux comprendre l'utilisation de l'intrication dans les jeux multipartites avec intérêts conflictuels. Ces situations sont rarement abordées en théorie de l'information quantique, mais elles sont centrales en théorie des jeux, où intervient la notion d'équilibre de Nash. Renforcer le lien entre ces deux domaines pourrait offrir de nouvelles perspectives sur l'utilisation de l'intrication dans des scénarios non locaux. Nous analysons en particulier deux types de ressources quantiques : l'une où les joueurs ont un accès direct à un état quantique intriqué, et une seconde, que nous introduisons ici, où ils reçoivent des conseils classiques issus de dispositifs quantiques. Bien que ces deux ressources soient équivalentes dans des contextes coopératifs, nous montrons qu'elles diffèrent dans les jeux à intérêts conflictuels, menant à des équilibres de Nash distincts et à des solutions potentiellement différentes en termes de bien-être social.Dans la seconde partie, nous cherchons à mieux comprendre la puissance de calcul des ordres causaux indéfinis. Alors que le modèle standard des circuits quantiques suppose que les opérations sont appliquées selon un ordre causal bien défini, la possibilité de relaxer cette contrainte pour permettre des procédures de calcul causalement indéfinis a récemment suscité un vif intérêt, notamment via le formalisme des supermaps quantiques. Plusieurs avantages ad hoc, tant computationnels qu'en traitement de l'information, ont été mis en évidence, soulevant la question de savoir si de tels avantages peuvent être démontrés dans un cadre unifié de théorie de la complexité. Les supermaps étant mieux comprises comme un modèle de calcul utilisant des boîtes noires, nous commençons par étendre la notion de complexité de requête des fonctions booléennes au cadre computationnel généralisé des supermaps, tant dans le cas classique que quantique. Ensuite, en utilisant des supermaps à plusieurs tours (multi-round), nous définissons également des protocoles de communication bipartites et multipartites avec communication causalement indéfinie, ainsi que la notion généralisée de complexité de communication des fonctions booléennes qui en découle. En étendant ces différentes mesures de complexité aux scénarios causalement indéfinis, nous évaluons les limites et les avantages des ordres causaux indéfinis dans un cadre rigoureux de théorie de la complexité, le même cadre dans lequel sont habituellement formulées les séparations entre ordinateurs classiques et quantiques.
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.
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.
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.
Compatibilité et non-localité L'un des concepts majeurs introduit par la théorie quantique est celui de la compatibilité des mesures quantiques. Il existe certains types de mesures qui ne peuvent pas être effectuées en même temps. Ainsi, on dit que les mesures sont compatibles si on peut mesurer en même temps et d'autre sont incompatibles. L'autre concept majeur de la mécanique quantique est celui de la nonlocalité qui est l'un des concepts les plus contre-intuitifs de la physique quantique. Ce concept majeur est dû à John Bell qui a montré que la mécanique quantique est intrinsèquement non locale. Ainsi, on parle de violation des inégalités de Bell par la mécanique quantique. Aujourd'hui, la nonlocalité est comprise à travers les jeux nonlocaux. Un jeux nonlocal consiste en deux joueurs ou plus Alice et Bob jouant contre un arbitre. Ce dernier posera un certain nombre de questions aux joueurs qui devront générer un certain nombre de réponses en utilisant une stratégie classique ou quantique. Il se trouve que le maximum des réponses qu'Alice et Bob peuvent générer est intrinsèquement relié à une norme tensorielle caractérisant le jeu. Dans ce formalisme, l'utilisation des stratégies classiques est relié à la norme de la matrice du jeux lui-même, ainsi la violation des inégalités de Bell se traduit par une inégalité stricte entre les normes tensorielles. Le but de cette thèse consiste à comprendre l'incompatibilité des mesures quantiques ainsi que le lien avec les inégalités de Bell. Dans un premier temps, nous avons introduit la compatibilité des mesures quantiques sous un nouveau point de vue, et analysé les types de bruit qu'on peut effectuer à fin de rendre le système compatible. Ce nouveau point de vue consiste à comprendre et à analyser l'effet de la dimension de l'espace de Hilbert sur l'incompatibilité des mesures. Par ailleurs à fin de rendre des mesures compatibles, on peut introduire l'effet d'un bruit. Comme application, certains états connu sous le nom de MUB sont de nature incompatible, on montre même si on rajoute du bruit aux MUB celle-ci restant incompatible, il existe une isométrie et un espace de Hilbert de dimension plus petite rendant les MUB compatibles. Dans un deuxième temps, nous avons analysé le lien intrinsèque reliant l'incompatibilité des mesures quantique et la violation des inégalités de Bell. Pour cela, on a considéré le cadre des jeux nonlocaux, où les mesures d'Alice sont fixées. Il est connu qu'une violation des inégalités de Bell nécessite l'utilisation des mesures incompatibles. Par ailleurs, si Alice veut savoir si elle observera une violation des inégalités de Bell si elle utilise des mesures incompatibles. Pour cela, elle doit calculer deux normes tensorielles d'un tenseur construit à partir de ses mesures. Ces normes tensorielles vont caractériser d'une part la compatibilité des mesures d'Alice et d'autre part la violation des inégalités de Bell. Dans ce cadre naturel, comprendre le lien entre incompatibilité des mesures quantiques et la violation des inégalités de Bell, revient à comparer les deux normes tensorielles. Or, il se trouve que pour le jeu CHSH ces deux normes sont égales, mais on peut montrer généralement qu'elles ne le sont pas. On peut se demander s'il existe d'autre types de jeux satisfaisant cette égalité des normes tensorielles ? Il se trouve que nous avons montré qu'avec des conditions suffisantes, seul le jeux CHSH à constante multiplicative près donne l'égalité entre les normes tensorielles.