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:2604.01408

Quantum polymorphism characterisation of commutativity gadgets in all quantum models

Eric Culf, Josse van Dobben de Bruyn, Peter Zeman

quant-phcs.CCmath.OASubmitted Apr 1, 2026• Announced Apr 3, 2026• 0 citations
v1 · Apr 1, 2026v2 · Sep 22, 2026
arXivHTMLPDF

Abstract

Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal games. We develop a general framework for commutativity gadgets in the setting of quantum homomorphisms between finite relational structures. Building on the notion of quantum homomorphism spaces, we introduce a uniform notion of commutativity gadget capturing the finite-dimensional quantum, quantum approximate, and commuting-operator models. In the robust setting, we use the weighted-algebra formalism for approximate quantum homomorphisms to capture corresponding notions of robust commutativity gadgets. Our main results characterize both non-robust and robust commutativity gadgets purely in terms of quantum polymorphism spaces: in any model, existence of a commutativity gadget is equivalent to the collapse of the corresponding quantum polymorphisms to classical ones at arity $|A|^2$, and robust gadgets are characterized by stable commutativity of the appropriate weighted polymorphism algebra. We use this characterisation to show relations between the classes of commutativity gadget, notably that existence of a robust commutativity gadget is equivalent to the existence of a corresponding non-robust one. Finally, we prove that quantum polymorphisms of complete graphs $K_n$ have a very special structure, wherein the noncommutative behaviour only comes from the quantum permutation group $S_n^+$. Combining this with techniques from combinatorial group theory, we construct separations between commutativity-gadget classes: we exhibit a relational structure admitting a finite-dimensional commutativity gadget but no quantum approximate gadget, and, conditional on the existence of a non-hyperlinear group, a structure admitting a quantum approximate commutativity gadget but no commuting-operator gadget.

Comments
44 pages, 3 figures

Related papers

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•0 citations

Existence and nonexistence of commutativity gadgets for entangled CSPs

Eric Culf, Josse van Dobben de Bruyn, Matthijs Vernooij +1 more

Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSPs. This has been done, for instance, for NP-complete boolean CSPs and 3-colouring in the work of Culf and Mastel. For many CSPs over larger alphabets, including $k$-colouring when $k \geq 4$, it is not known whether or not commutativity gadgets exist, or if the entangled CSP is decidable. In this paper, we initiate a systematic study of commutativity gadgets and prove the first known obstruction to their existence. We do this by extending the definition of the quantum automorphism group of a graph to the quantum endomorphism monoid of a CSP, and showing that a CSP with non-classical quantum endomorphism monoid does not admit a commutativity gadget. As a consequence of this, we get that no commutativity gadget exists for $k$-colouring when $k \geq 4$. However, we construct a commutativity gadget for an alternate way of presenting $k$-colouring as a nonlocal game, the oracular setting. Furthermore, we prove an easy to check sufficient condition for the quantum endomorphism monoid to be non-classical, extending a result of Schmidt for the quantum automorphism group of a graph, and use this to give examples of CSPs that do not admit a commutativity gadget. We also show that existence of commutativity gadgets and oracular commutativity gadgets is equivalent for graphs with no four-cycle; and that the odd cycles and the odd graphs have a commutative quantum endomorphism monoid, leaving open the possibility that they might admit a commutativity gadget.

arXiv:2509.07835•Sep 9, 2025•0 citations

Non-local game homomorphisms

Gage Hoefer

In the past few decades, the connections between non-local games arising in quantum information theory and the theory of operator algebras have undergone a phase of significant development. Operator algebras provide a particularly fruitful framework for approaching questions of non-locality in quantum systems, as the input-output behavior of measurements on bipartite quantum systems can be encoded through noncommutative operator algebras and their state spaces. This thesis is the compilation of a series of papers, written by the author in collaboration with Ivan G. Todorov, utilizing this framework by using the theory of operator algebras and completely positive maps to study questions involving non-local games. ☐ Using the simulation paradigm from information theory, we define a quantized version of homomorphisms and isomorphisms between classical hypergraphs, generalizing quantum homomorphisms and isomorphisms of graphs from the literature. We show that these quantum homomorphisms and isomorphisms constitute pre-orders and equivalence relations, respectively. We use quantum homomorphisms of hypergraphs to provide multiple examples of strict separation between correlation classes of varying types. Specializing to the case when our underlying hypergraphs arise from classical non-local games, we define quantum non-local game homomorphisms and isomorphisms. We also show how the existence of a homomorphism or isomorphism of some fixed type between games is reflected in a comparison of optimal and asymptotic game values with respect to this type. These non-local game homomorphisms are defined via a new class of non-signalling correlations which we introduce here. We develop the multivariate tensor product theory in the category of operator systems, which we then use to provide a characterization of game homomorphisms in terms of state spaces for various tensor products of canonically associated operator systems. We then apply these results to the study of synchronous non-local games, defining jointly synchronous correlations and showing how they correspond to tracial states of tensor products of C*-algebras canonically associated to each game party. ☐ We then move to a second level of quantization by proposing a "quantized" notion of hypergraphs (where "quantum" here is in the sense of a non-commutative analogue for a discrete combinatorial object), and introduce quantum homomorphisms between these quantum objects. We provide an initial foray into the properties quantum morphisms between quantum hypergraphs display, showing they satisfy analogous properties to quantum homomorphisms between classical hypergraphs. We also indicate initial connections these quantum homomorphisms between quantum hypergraphs have to the study of quantum input-output games. We end the thesis showing that homomorphisms of a local type between quantum hypergraphs is closely related, and in some cases identical, to the TRO equivalence of finite-dimensionally acting operator spaces canonically associated with each hypergraph. This suggests a quantum information theoretic approach to Morita equivalence in the category of operator spaces.

•Feb 16, 2026•0 citations

A compositional approach to quantum functions

Benjamin Musto, David Reutter, Dominic Verdon

We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.

arXiv:1711.07945•Journal of Mathematical Physics•Aug 1, 2018•53 citations

Quantum non-local games: Quantum relations, projection lattices and rule operators

Alexandros Chatzinikolaou

Quantum non-local games with quantum inputs or outputs have been formulated in several different languages, including rank-one and quantum XOR games, support maps between projection lattices, probabilistic quantum hypergraphs, and Frobenius-algebraic rule operators on finite quantum sets. We give a unified operator-algebraic comparison of these models by assigning to each rule its winning transformation space: the operator space of transformations accepted with certainty. We introduce \(\mathcal R\)-projection-test quantum games with finite-dimensional input and output von Neumann algebras and an arbitrary, possibly infinite-dimensional, referee von Neumann algebra \(\mathcal R\). Their winning transformation spaces are precisely operator spaces with a natural bimodule structure, equivalently rectangular quantum relations. We compare this formalism with projection-lattice games, hypergraph quantum games, and the graphical rule-operator definition. Projection-lattice games capture exactly the reflexive winning bimodules. Hypergraph quantum games admit value-preserving projection-test realisations, and, after passing to perfect transformations, describe the same reflexive part as projection-lattice games. Using Daws' technique, we also translate rule operators to projections in tensor products of finite-dimensional von Neumann algebras. This identification places graphical rules in the same operator-bimodule framework and preserves both values and perfectness. Finally, we compare concurrency with the synchronicity conditions of Goldberg and of Bochniak--Kasprzak--Sołtan. The framework is illustrated by classical, rank-one, quantum XOR, colouring, and quantum graph homomorphism and isomorphism games.

math.OACross-listedarXiv:2608.30507•Sep 1, 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
Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal games. We develop a general framework for commutativity gadgets in the setting of quantum homomorphisms between finite relational structures. Building on the notion of quantum homomorphism spaces, we introduce a uniform notion of commutativity gadget capturing the finite-dimensional quantum, quantum approximate, and commuting-operator models. In the robust setting, we use the weighted-algebra formalism for approximate quantum homomorphisms to capture corresponding notions of robust commutativity gadgets.
Our main results characterize both non-robust and robust commutativity gadgets purely in terms of quantum polymorphism spaces: in any model, existence of a commutativity gadget is equivalent to the collapse of the corresponding quantum polymorphisms to classical ones at arity ∣A∣2|A|^2∣A∣2, and robust gadgets are characterized by stable commutativity of the appropriate weighted polymorphism algebra. We use this characterisation to show relations between the classes of commutativity gadget, notably that existence of a robust commutativity gadget is equivalent to the existence of a corresponding non-robust one.
Finally, we prove that quantum polymorphisms of complete graphs KnK_nKn​ have a very special structure, wherein the noncommutative behaviour only comes from the quantum permutation group Sn+S_n^+Sn+​. Combining this with techniques from combinatorial group theory, we construct separations between commutativity-gadget classes: we exhibit a relational structure admitting a finite-dimensional commutativity gadget but no quantum approximate gadget, and, conditional on the existence of a non-hyperlinear group, a structure admitting a quantum approximate commutativity gadget but no commuting-operator gadget.
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.
Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSPs. This has been done, for instance, for NP-complete boolean CSPs and 3-colouring in the work of Culf and Mastel. For many CSPs over larger alphabets, including kkk-colouring when k≥4k \geq 4k≥4, it is not known whether or not commutativity gadgets exist, or if the entangled CSP is decidable. In this paper, we initiate a systematic study of commutativity gadgets and prove the first known obstruction to their existence. We do this by extending the definition of the quantum automorphism group of a graph to the quantum endomorphism monoid of a CSP, and showing that a CSP with non-classical quantum endomorphism monoid does not admit a commutativity gadget. As a consequence of this, we get that no commutativity gadget exists for kkk-colouring when k≥4k \geq 4k≥4. However, we construct a commutativity gadget for an alternate way of presenting kkk-colouring as a nonlocal game, the oracular setting. Furthermore, we prove an easy to check sufficient condition for the quantum endomorphism monoid to be non-classical, extending a result of Schmidt for the quantum automorphism group of a graph, and use this to give examples of CSPs that do not admit a commutativity gadget. We also show that existence of commutativity gadgets and oracular commutativity gadgets is equivalent for graphs with no four-cycle; and that the odd cycles and the odd graphs have a commutative quantum endomorphism monoid, leaving open the possibility that they might admit a commutativity gadget.
In the past few decades, the connections between non-local games arising in quantum information theory and the theory of operator algebras have undergone a phase of significant development. Operator algebras provide a particularly fruitful framework for approaching questions of non-locality in quantum systems, as the input-output behavior of measurements on bipartite quantum systems can be encoded through noncommutative operator algebras and their state spaces. This thesis is the compilation of a series of papers, written by the author in collaboration with Ivan G. Todorov, utilizing this framework by using the theory of operator algebras and completely positive maps to study questions involving non-local games. ☐ Using the simulation paradigm from information theory, we define a quantized version of homomorphisms and isomorphisms between classical hypergraphs, generalizing quantum homomorphisms and isomorphisms of graphs from the literature. We show that these quantum homomorphisms and isomorphisms constitute pre-orders and equivalence relations, respectively. We use quantum homomorphisms of hypergraphs to provide multiple examples of strict separation between correlation classes of varying types. Specializing to the case when our underlying hypergraphs arise from classical non-local games, we define quantum non-local game homomorphisms and isomorphisms. We also show how the existence of a homomorphism or isomorphism of some fixed type between games is reflected in a comparison of optimal and asymptotic game values with respect to this type. These non-local game homomorphisms are defined via a new class of non-signalling correlations which we introduce here. We develop the multivariate tensor product theory in the category of operator systems, which we then use to provide a characterization of game homomorphisms in terms of state spaces for various tensor products of canonically associated operator systems. We then apply these results to the study of synchronous non-local games, defining jointly synchronous correlations and showing how they correspond to tracial states of tensor products of C*-algebras canonically associated to each game party. ☐ We then move to a second level of quantization by proposing a "quantized" notion of hypergraphs (where "quantum" here is in the sense of a non-commutative analogue for a discrete combinatorial object), and introduce quantum homomorphisms between these quantum objects. We provide an initial foray into the properties quantum morphisms between quantum hypergraphs display, showing they satisfy analogous properties to quantum homomorphisms between classical hypergraphs. We also indicate initial connections these quantum homomorphisms between quantum hypergraphs have to the study of quantum input-output games. We end the thesis showing that homomorphisms of a local type between quantum hypergraphs is closely related, and in some cases identical, to the TRO equivalence of finite-dimensionally acting operator spaces canonically associated with each hypergraph. This suggests a quantum information theoretic approach to Morita equivalence in the category of operator spaces.
We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.
Quantum non-local games with quantum inputs or outputs have been formulated in several different languages, including rank-one and quantum XOR games, support maps between projection lattices, probabilistic quantum hypergraphs, and Frobenius-algebraic rule operators on finite quantum sets. We give a unified operator-algebraic comparison of these models by assigning to each rule its winning transformation space: the operator space of transformations accepted with certainty. We introduce R\mathcal RR-projection-test quantum games with finite-dimensional input and output von Neumann algebras and an arbitrary, possibly infinite-dimensional, referee von Neumann algebra R\mathcal RR. Their winning transformation spaces are precisely operator spaces with a natural bimodule structure, equivalently rectangular quantum relations. We compare this formalism with projection-lattice games, hypergraph quantum games, and the graphical rule-operator definition. Projection-lattice games capture exactly the reflexive winning bimodules. Hypergraph quantum games admit value-preserving projection-test realisations, and, after passing to perfect transformations, describe the same reflexive part as projection-lattice games. Using Daws' technique, we also translate rule operators to projections in tensor products of finite-dimensional von Neumann algebras. This identification places graphical rules in the same operator-bimodule framework and preserves both values and perfectness. Finally, we compare concurrency with the synchronicity conditions of Goldberg and of Bochniak--Kasprzak--Sołtan. The framework is illustrated by classical, rank-one, quantum XOR, colouring, and quantum graph homomorphism and isomorphism games.
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.