Complexité de Kolmogorov et corrélations quantiques; étude du carré magique
Thesis or Dissertation
2019-08 (degree granted: 2020-03-25)
Author(s)
Advisor(s)
Level
Master'sDiscipline
PhysiqueKeywords
- corrélations quantiques
- informatique quantique
- intrication
- complexité de Kolmogorov
- théorème des répétitions parallèles
- boîtes Popescu-Rohrlich
- carré magique
- Quantum correlations
- Quantum information
- Entanglement
- Kolmogorov complexity
- Parallel repetition theorem
- Popescu-Rohrlich boxes
- Magic square
- Physics - Theory / Physique - Théorie (UMI : 0753)
Abstract(s)
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. Quantum information, this intriguing marriage between computer science and physics, is a
promising field of research for future technologies as well as a better understanding of our
universe. Entanglement is at the very heart of this new way of understanding information.
This thesis focuses on quantum correlations that are observed in nature. They have been
studied in great detail by, among others, John Bell. More specifically, two non-signaling
games, in which these correlations arise, are studied: the CHSH game, which is probably
the best-known example of such games, and the magic square pseudotelepathy game. To
do so, two points of view will be adopted: probabilistic and algorithmic. The first is
motivated by prediction (what could have happened) and the second focuses on the intrinsic
information about an object (what happened). Therefore, the concepts of randomness and
information are first addressed from Shannon’s point of view (probabilistic approach) and
second from Kolmogorov’s point of view (algorithmic approach). Kolmogorov complexity is
used to quantify information in a factual way. Furthermore, the particular case in which
multiple repetitions of a game are played in parallel in a classical world is considered.
The parallel repetition theorem, an important result on the subject proven by Ran Raz,
is presented and used in the algorithmic study of the CHSH game and the magic square game.
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.