Multi-Prover and parallel repetition in non-classical interactive games
Thèse ou mémoire
2009-08 (octroi du grade: 2010-02-04)
Auteur·e·s
Cycle d'études
MaîtriseProgramme
InformatiqueMots-clés
- Preuves intéractives à plusieurs prouveurs
- Multi-prover interactive proofs
- Jeux du cycle impair
- Odd Cycle Games
- Nonlocalité
- Nonlocality
- Complexité du calcul quantique
- Quantum computational complexity
- Intrication
- Entanglement
- Applied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)
Résumé·s
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. Since the introduction of quantum mechanics, many mysteries of nature have
found explanations. Many quantum-mechanical concepts have merged with the
field of computational complexity theory. New ideas and solutions have been
put forward to solve computational problems. In particular, quantum mechanics
has struck down many security proofs of classical protocols.
In this thesis, we survey recent results regarding the implication of quantum
mechanics to computational complexity and more precisely to classes with interaction.
We present the work done in the framework of cooperative games with
imperfect information. We give some differences between classical, quantum
and no-signaling theories and apply them to the specific example of Odd Cycle
Games. We center our attention on two different themes: the effect on a game
of adding more players and of parallel repetition. We observe that depending
of the physical theory considered, the consequences of these changes is very
different.
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Il peut être utilisé dans le cadre d'une utilisation équitable et non commerciale, à des fins d'étude privée ou de recherche, de critique ou de compte-rendu comme le prévoit la Loi. Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.