Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We show a general connection between these notions and state-independent quantum realizations of strong contextuality in the Abramsky-Brandenburger formulation of contextuality. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work.
Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We show a general connection between these notions and state-independent quantum realizations of strong contextuality in the Abramsky-Brandenburger formulation of contextuality. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work.
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.
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.
The notion of effectus from categorical logic is relevant in the emerging field of categorical probability theory. In some cases, stochastic maps are represented by maps in the Kleisli category of some probability monad. Quantum homomorphisms from combinatorics and quantum information theory are the Kleisli maps of certain sort of quantum monad. We show that the Kleisli category of this quantum monad is an effectus. This gives rise to notions of quantum probabilistic reasoning as predicates, validity, conditioning, and channels.
We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions between quantum CSPs, and we establish a Galois connection between quantum polymorphism minions and quantum relational constructions. By leveraging a contextuality property of quantum polymorphisms, we fully characterise the existence of commutativity gadgets for relational structures, introduced by Ji as a method for achieving quantum soundness of classical CSP reductions. Prior to our work, only a partial classification was known for a subclass of Boolean languages and for non-Boolean languages meeting specific structural conditions [Culf--Mastel, FOCS'25]. As an application of our framework, we prove that the quantum CSPs parameterised by odd cycles and the quantum CSP expressing quantum satisfiability of Siggers clauses are undecidable.
We present two results on the subject of quantum contextuality and cohomology, and non-locality and quantum advantage with shallow circuits. Abramsky et al. showed that a range of examples of quantum contextuality is detected by a cohomological invariant based on Čech cohomology. However, the approach does not give a complete cohomological characterisation of contextuality. A different cohomological approach to contextuality was introduced by Okay et al. Their approach exploits the algebraic structure of the Pauli operators and their qudit generalisations known as Weyl operators. We give an abstract account of this structure, then generalise their approach to any example of contextuality with this structure. We prove at this general level that the approach does not give a more complete characterisation of contextuality than the Čech cohomology approach. Bravyi, Gosset, and König (BGK) gave the first unconditional proof that a restricted class of quantum circuits is more powerful than its classical analogue. The result, for the class of circuits of bounded depth and fan-in (shallow circuits), exploits a particular family of examples of contextuality. BGK's quantum circuit and computational problem are derived from a family of non-local games related to the well-known GHZ non-local game. We present a generalised version of their construction. A systematic way of taking examples of contextuality and producing unconditional quantum advantage results with shallow circuits.
We introduce a category qGph of quantum graphs, whose definition is motivated entirely from noncommutative geometry. For all quantum graphs G and H in qGph, we then construct a quantum graph [G,H] of homomorphisms from G to H, making qGph a closed symmetric monoidal category. We prove that for all finite graphs G and H, the quantum graph [G,H] is nonempty iff the (G,H)-homomorphism game has a winning quantum strategy, directly generalizing the classical case.
The finite quantum graphs in qGph are tracial, real, and self-adjoint, and the morphisms between them are CP morphisms that are adjoint to a unital ∗-homomorphism. We prove that Weaver's two notions of a CP morphism coincide in this context. We also include a short proof that every finite reflexive quantum graph is the confusability quantum graph of a quantum channel.