Parallel Repetition in Nonlocal Games
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Authors
Date
2024-12-31
Department
Major/Subject
Mathematics
Mcode
Degree programme
Master's Programme in Engineering Physics
Language
en
Pages
77
Series
Abstract
Nonlocal games are one-round multiplayer games where players answer a verifier’s questions without classical communication, using predetermined strategies. Parallel repetition involves playing these games repeatedly and simultaneously to study how the winning probability changes with the number of repetitions. Classically, the parallel repetition theorem demonstrates that the winning probability decreases exponentially to zero with the number of repetitions. In contrast, for quantum strategies leveraging pre-shared entangled states, only polynomial decay has been proven, leaving the possibility of exponential decay an open question. This thesis explores the concept of parallel repetition in nonlocal games. We begin by presenting the mathematical framework of nonlocal games. We analyse both classical deterministic strategies and quantum strategies to highlight their differences and challenges. We then review the existing literature on attempts to establish exponential decay for parallel repetition in the quantum regime of nonlocal games. Particular emphasis is placed on XOR games, where we provide a detailed proof to illustrate the concept. Finally, we analyse the effects of parallel repetition when different games are played simultaneously instead of repeating the same game, offering insights into how this variation impacts the success probability.Description
Supervisor
Kytölä, KalleThesis advisor
Mancinska, LauraKeywords
nonlocal games, parallel repetition, quantum entanglement, quantum information, quantum computation, multi-prover games