Quantum Games, Graphs, and Gödel

Abstract

This thesis explores the quantum extension of a fundamental theme in theoretical computer science: the interplay between graph theory, computational complexity, and multiprover interactive proof systems. Specifically, we examine the connections between quantum graph properties, computability theory, and entangled nonlocal games.Building on prior work that defined quantum variants of graph homomorphisms, isomorphism, and chromatic, independence, and clique numbers, we introduce quantum perfect matching properties for graphs. We characterize these properties by quantizing a classical relationship between perfect matchings and the independence number of line graphs. We then investigate the complexity of determining whether a nonlocal game is perfectly winnable with an entangled strategy. While the landmark result ???* = ?? established the undecidability of this problem, we show that it is doubly undecidable, proving its completeness for the class Π2 in the second level of the arithmetical hierarchy. This result is achieved by further developing the iterated compression technique. Additionally, we define a family of nonlocal games generalizing the CHSH game and analyze their rigidity properties using a novel noncommutative sum-of-squares framework. This approach allows us to prove rigidity for games with quantum values bounded away from 1. Finally, we study synchronous strategies, which are used throughout the literature and the rest of this thesis. We look at synchronous strategies in less studied contexts of non-synchronous games and synchronous games which are not perfectly winnable.