Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1705.07310 · Leibniz international proceedings in informatics

The Quantum Monad on Relational Structures

Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, Octavio Zapata

Published Jan 1, 2017• 43 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.mfcs.2017.35

Related papers

Quantum Relaxations of CSP and Structure Isomorphism

Karamlou, Amin

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.

•Jan 1, 2025•2 citations

k-partite quantum homomorphisms

Amin Karamlou

$k$-partite XOR games and linear binary constraint system (BCS) games arise from systems of linear equations over $\mathbb{Z}_2$, providing distinct quantum relaxations of the same classical constraint satisfaction problem (CSP). Linear BCS games have been generalised to synchronous homomorphism games on arbitrary relational structures, with compositional semantics provided by the quantum monad. We introduce $k$-partite homomorphism games, extending $k$-XOR games from linear systems to arbitrary relational structures. This yields a framework for studying multipartite quantum CSPs and quantum homomorphisms. We characterise perfect strategies in both the tensor-product and commuting-operator models as Kleisli morphisms of suitable state-dependent graded quantum monads on a category of $k$-partite relational structures. We then study quantum advantage in the pseudotelepathic sense: the existence of a perfect quantum strategy without a perfect classical strategy. We show that synchronous and $k$-partite quantum advantage are incomparable at the level of CSP instances. The GHZ instance admits three-player quantum advantage but no synchronous commuting-operator advantage, whereas the magic-square instance admits synchronous quantum advantage but no $k$-partite commuting-operator advantage for any number of players or proper colouring. We also exhibit an explicit six-element template whose CSP is NP-complete and admits two-player quantum advantage. Finally, we prove that no bounded-width CSP template admits $k$-partite quantum advantage, even in the commuting-operator model.

arXiv:2611.15839•Nov 11, 2026•0 citations

Composing classical and quantum relaxations of CSP and structure isomorphism

Mohammad Karamlou

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.

•Jan 1, 2025•0 citations

Logical aspects of probability and quantum computation

Zapata Fonseca, Octavio Baltasar

Most of the work presented in this document can be read as a sequel to previous work of the author and collaborators, which has been published and appears in [DSZ16, DSZ17, ABdSZ17]. In [ABdSZ17], the mathematical description of quantum homomorphisms of graphs and more generally of relational structures, using the language of category theory is given. In particular, we introduced the concept of ‘quantum’ monad. In this thesis we show that the quantum monad fits nicely into the categorical framework of effectus theory, developed by Jacobs et al. [Jac15, CJWW15]. Effectus theory is an emergent field in categorical logic aiming to describe logic and probability, from the point of view of classical and quantum computation. The main contribution in the first part of this document prove that the Kleisli category of the quantum monad on relational structures is an effectus. The second part is rather different. There, distinct facets of the equivalence relation on graphs called cospectrality are described: algebraic, combinatorial and logical relations are presented as sufficient conditions on graphs for having the same spectrum (i.e. being ‘cospectral’). Other equivalence of graphs (called fractional isomorphism) is also related using some ‘game’ comonads from Abramsky et al. [ADW17, Sha17, AS18]. We also describe a sufficient condition for a pair of graphs to be cospectral using the quantum monad: two Kleisli morphisms (going in opposite directions) between them satisfying certain compatibility requirement.

•Jan 1, 2019•1 citation

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction

Lorenzo Ciardo, Gideo Joubert, Antoine Mottet

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.

quant-pharXiv:2511.23445•Dec 1, 2025•5 citations

Effectus of Quantum Probability on Relational Structures

Octavio Zapata

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.

arXiv:2005.00209•Electronic Proceedings in Theoretical Computer Science•Apr 30, 2020•0 citations
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.
kkk-partite XOR games and linear binary constraint system (BCS) games arise from systems of linear equations over Z2\mathbb{Z}_2Z2​, providing distinct quantum relaxations of the same classical constraint satisfaction problem (CSP). Linear BCS games have been generalised to synchronous homomorphism games on arbitrary relational structures, with compositional semantics provided by the quantum monad. We introduce kkk-partite homomorphism games, extending kkk-XOR games from linear systems to arbitrary relational structures. This yields a framework for studying multipartite quantum CSPs and quantum homomorphisms. We characterise perfect strategies in both the tensor-product and commuting-operator models as Kleisli morphisms of suitable state-dependent graded quantum monads on a category of kkk-partite relational structures. We then study quantum advantage in the pseudotelepathic sense: the existence of a perfect quantum strategy without a perfect classical strategy. We show that synchronous and kkk-partite quantum advantage are incomparable at the level of CSP instances. The GHZ instance admits three-player quantum advantage but no synchronous commuting-operator advantage, whereas the magic-square instance admits synchronous quantum advantage but no kkk-partite commuting-operator advantage for any number of players or proper colouring. We also exhibit an explicit six-element template whose CSP is NP-complete and admits two-player quantum advantage. Finally, we prove that no bounded-width CSP template admits kkk-partite quantum advantage, even in the commuting-operator model.
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.
Most of the work presented in this document can be read as a sequel to previous work of the author and collaborators, which has been published and appears in [DSZ16, DSZ17, ABdSZ17]. In [ABdSZ17], the mathematical description of quantum homomorphisms of graphs and more generally of relational structures, using the language of category theory is given. In particular, we introduced the concept of ‘quantum’ monad. In this thesis we show that the quantum monad fits nicely into the categorical framework of effectus theory, developed by Jacobs et al. [Jac15, CJWW15]. Effectus theory is an emergent field in categorical logic aiming to describe logic and probability, from the point of view of classical and quantum computation. The main contribution in the first part of this document prove that the Kleisli category of the quantum monad on relational structures is an effectus. The second part is rather different. There, distinct facets of the equivalence relation on graphs called cospectrality are described: algebraic, combinatorial and logical relations are presented as sufficient conditions on graphs for having the same spectrum (i.e. being ‘cospectral’). Other equivalence of graphs (called fractional isomorphism) is also related using some ‘game’ comonads from Abramsky et al. [ADW17, Sha17, AS18]. We also describe a sufficient condition for a pair of graphs to be cospectral using the quantum monad: two Kleisli morphisms (going in opposite directions) between them satisfying certain compatibility requirement.
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.
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.