We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on (i) the size of the shared quantum system used in the quantum strategy, and (ii) structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies.A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size.
We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on (i) the size of the shared quantum system used in the quantum strategy, and (ii) structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies.A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size.
We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's d-to-1 games: for every d≥4, every ε>0, and every k∈N, there is a d-to-1 label-cover game of classical value less than ε that admits a perfect quantum strategy using finite-dimensional shared entanglement with measurement contexts of radius at least k. As a consequence, there exist graphs whose quantum chromatic number χq is 3 and whose classical chromatic number χ is arbitrarily large. This is the first improvement on the quantum chromatic gap since the work of Brassard, Cleve, and Tapp [Phys. Rev. Lett.'99], which produced graphs for which χ grows exponentially in χq.
To prove the conjecture, we proceed as follows. We start with a ``stretched'' version of the Mermin--Peres magic square, obtained by spacing out its equations and linking them with additional long equation wires. This operation increases the radius of the initial measurement contexts of a perfect quantum strategy for the game, while preserving classical unsatisfiability. We then apply parallel repetition to make the classical value small, and we turn the system into a pseudo-telepathic multi-layered Kneser hypergraph via a PCP construction of Dinur, Guruswami, Khot, and Regev [STOC'03]. Finally, we feed the resulting hypergraph into the reduction of Fei, Minzer, and Wang from hypergraph colouring to 4-to-1 games, we establish quantum completeness of this reduction, and we show that it preserves context radius.
We investigate quantum relaxations of two key decision problems in computer science: the constraint satisfaction problem (CSP) and the structure isomorphism problem. CSP asks whether a homomorphism exists between two relational structures, while structure isomorphism seeks an isomorphism between them. In recent years, it has become increasingly apparent that many special cases of CSP can be reformulated in terms of the existence of perfect classical strategies in non-local games, a key topic of study in quantum information theory. These games have allowed us to study quantum advantage in relation to many important decision problems, such as the k-colouring problem, and the problem of solving binary constraint systems. Abramsky et al. (2017) have shown that all of these games can be seen as special instances of a non-local CSP game. Moreover, they show that perfect quantum strategies in this CSP game can be viewed as Kleisli morphisms of a graded monad on the category of relational structures, which they dub the quantum monad. In this way, the quantum monad provides a categorical characterisation of quantum advantage for the non-local CSP game. In this work we solidify and expand the results of Abramsky et al., answering several of their open questions. Firstly, we compare the definition of quantum graph homomorphisms arising from this work with an earlier definition of the concept due to Mančinska and Roberson and show that there are graphs which exhibit quantum advantage under one definition but not the other. Our second contribution is to extend the results of Abramsky et al. which only hold in the tensor product framework of quantum mechanics to the commuting operator framework. Next, we study a non-local structure isomorphism game, which generalises the well-studied graph isomorphism game. We show how the construction of the quantum monad can be refined to provide categorical semantics for quantum strategies in this game. This results in a category where morphisms coincide with quantum homomorphisms and isomorphisms coincide with quantum isomorphisms.
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers. Using our approximation by a semidefinite program we also show a parallel repetition theorem for unique entangled games.
We show that the value of a general two-prover quantum game cannot be computed by a semi-definite program ofvpolynomial size (unless P=NP), a method that has been successful in more restricted quantum games. More precisely, we show that proof of membership in the NP-complete problem GAP-3D-Matching can be obtained by a 2-prover, 1-round quantum interactive proof system where the provers share entanglement, with perfect completeness and soundness s=1-2^(-O(n)), and such that the space of the verifier and the size of the messages are O(log n). This implies that QMIP^*_{log n,1,1-2^(-O(n))} \nsubseteq P unless P = NP and provides the first non-trivial lower bound on the power of entangled quantum provers, albeit with an exponentially small gap. The gap achievable by our proof system might in fact be larger, provided a certain conjecture on almost commuting versus nearly commuting projector matrices is true.
Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension d satisfies every prescribed winning constraint, whereas a classical d-level message cannot. We establish three structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a d-level message is equivalent to d-colorability, perfect d-dimensional quantum realization is equivalent to a d-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. Third, with at most two Bob inputs every perfect qutrit strategy admits a perfect classical-trit realization. An explicit seven-preparation qutrit game with three Bob inputs satisfies C3=20<Q3=S=21, so three Bob inputs are necessary and sufficient in dimension three. Conversely, a two-input, six-output game in dimension five satisfies C5=39<Q5=S=40. Thus the smallest dimension admitting a two-input perfect same-dimensional separation is either four or five; the four-dimensional case remains open. As a flagship binary application, the 13-ray qutrit graph yields a compressed game (X,Y,B)=(13,8,2) with C3=39<Q3=S=40, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.
This thesis investigates relaxations of two key decision problems in computer science: the constraint satisfaction problem (CSP) and the structure isomorphism problem. CSP asks whether a homomorphism exists between two relational structures, while structure isomorphism seeks an isomorphism between them. By adopting a categorical approach, we add to a growing list of results showing that relaxations of these problems, studied in universal algebra, finite model theory, and quantum information can all be captured abstractly using (co)monads. In particular, we will show that distribution minion monads capture many important minion tests from universal algebra, and that the quantum monad can be used to capture quantum homomorphisms and isomorphisms from quantum information. These results add to the already well-established connection between game comonads and Spoiler-Duplicator games from finite model theory. A key focus is the exploration of distributive laws, the existence of which enables the combination of comonads and monads, potentially leading to novel relaxations of CSP and structure isomorphism that integrate ideas from different domains. We establish a no-go theorem, showing that game comonads like the Ehrenfeucht-Fraïssé and pebbling comonads do not distribute over many important distribution minion monads, such as the basic linear programming and arc-consistency monads. On the positive side, we identify sufficient conditions under which a distributive law between game comonads and distribution minion monads exists. Neither our no-go theorems nor our positive results apply to the quantum monad. Thus, it remains an open question whether any game comonads distribute over the quantum monad. In addition, we prove several novel results related to quantum advantage. Firstly, we compare two existing definitions of quantum graph homomorphisms, and show that there are graphs where quantum advantage manifests under one definition but not the other. Secondly, we extend existing characterisations of tensor product strategies for the non-local CSP and structure isomorphism games to the more general class of commuting operator strategies. Finally, we introduce quantum versions of one-sided Spoiler-Duplicator games and show that quantum advantage is possible in such games. This result suggests that there is scope for adapting further tools from finite model theory to improve our understanding of quantum homomorphisms and quantum isomorphisms.