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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMU.1866/3547 |
| Date | 08 1900 |
| Creators | Payette, Tommy |
| Contributors | Salvail, Louis, Brassard, Gilles |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Thèse ou Mémoire numérique / Electronic Thesis or Dissertation |
Page generated in 0.0018 seconds