Location
QNC 2101
Candidate
Eric Culf | Applied Mathematics, University of Waterloo
Title
Entangled Constraint Satisfaction Problems: Reductions, Complexity, and Approximation Algorithms
Abstract
The result MIP* = RE shows that the problem of approximating the quantum value of a nonlocal game is undecidable. This thesis studies how this undecidability may be distilled to well-structured classes of nonlocal games, specifically those coming from constraint satisfaction problems (CSPs). A CSP is a decision problem where one must decide if a given set of constraints may be simultaneously satisfied; presenting it as a nonlocal game gives rise to an entangled CSP where the possible solutions are generalised to operator assignments. Many computational problems may be presented as CSPs, such as graph colouring. This work studies the various families of entangled CSP that arise due to the noncommutativity of quantum mechanics --- notably non-oracular CSPs, where the players only receive variables as questions, and oracular CSPs, where the players also receive constraints.
We study how reductions between CSPs may be made quantum-sound. First, we develop the theory of commutativity gadgets, which allow any classical constraint expressible by the CSP to be expressed in the entangled setting. This allows for classical reductions between CSPs to lift to gap-preserving reductions between entangled CSPs. We fully characterise the existence of commutativity gadgets by means of entangled polymorphisms of the CSP, a type of quantum symmetry, and use this show to equivalences and separations between commutativity gadgets in different models. Second, we extend the most powerful classical reduction between CSPs, based on minion homomorphisms of the polymorphism spaces, to the setting of gapped entangled CSPs. We apply both techniques to show that entangled graph k-colouring is undecidable for all k >= 3.
Famously, XOR games, which correspond to the CSP of boolean linear equations with two variables per equation, have a classical value which is NP-hard to approximate but a quantum value that can be approximated in polynomial time. We define the tilted XOR games, which correspond to the boolean linear CSP with one or two variables per equation. Though these are qualitatively close to XOR games, we show that their quantum value is undecidable to approximate, by quantising the classical reduction from linear system games to XOR games. This gives the first example of binary nonlocal games, where both players answer a single bit, whose quantum value is undecidable to approximate.
Finally, we study approximation algorithms for entangled CSPs. We develop an algorithm to approximate the quantum value of Max-k-Cut, the optimisation analogue of graph k-colouring. For k = 3 and k = 4, we find approximation ratios that are strictly better than for classical colouring, despite the problems being significantly harder. Our algorithm consists of a relaxation to a semidefinite program, followed by a randomised rounding using a Haar-random unitary. To analyse the algorithm, we make use of ideas from free probability to simplify the behaviour of the rounding in the limit of large dimension.