In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. We look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. Finally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. We look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. Finally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

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.