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

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

Alexandros Chatzinikolaou

math.OAquant-phSubmitted Aug 31, 2026• Announced Sep 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
41 pages, comments welcome

Related papers

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

Quantum No-signalling Correlations and Non-local Games

Ivan G. Todorov, Lyudmila B. Turowska

Abstract We introduce and examine three subclasses of the family of quantum no-signalling (QNS) correlations introduced by Duan and Winter: quantum commuting, quantum and local. We formalise the notion of a universal TRO of a block operator isometry, define an operator system, universal for stochastic operator matrices, and realise it as a quotient of a matrix algebra. We describe the classes of QNS correlations in terms of states on the tensor products of two copies of the universal operator system and specialise the correlation classes and their representations to classical-to-quantum correlations. We study various quantum versions of synchronous no-signalling correlations and show that they possess invariance properties for suitable sets of states. We introduce quantum non-local games as a generalisation of non-local games. We define the operation of quantum game composition and show that the perfect strategies belonging to a certain class are closed under channel composition. We specialise to the case of graph colourings, where we exhibit quantum versions of the orthogonal rank of a graph as the optimal output dimension for which perfect classical-to-quantum strategies of the graph colouring game exist, as well as to non-commutative graph homomorphisms, where we identify quantum versions of non-commutative graph homomorphisms introduced by Stahlke.

arXiv:2009.07016•Communications in Mathematical Physics•May 28, 2024•15 citations

The hypergraph isomorphism game, Hopf algebras, and Galois extensions

Georgios Baziotis, Alexandros Chatzinikolaou, Gage Hoefer

Abstract We develop an algebraic and operational framework for quantum isomorphisms of hypergraphs, using tools from compact quantum group theory. We introduce a new synchronous version of the hypergraph isomorphism game whose game algebra uniformly encodes multiple notions of quantum isomorphisms of hypergraphs. We show that there exist hypergraphs that are quantum isomorphic but not classically isomorphic. For graphs, we show that the ‐algebra of the hypergraph isomorphism game is a quotient of the ‐algebra of the graph isomorphism game. We further prove that the hypergraph game algebra forms a bi‐Galois extension over the quantum automorphism groups of the underlying hypergraphs. This allows us to deduce that the algebraic notion of a quantum isomorphism of hypergraphs coincides with the operational one coming from the existence of perfect quantum strategies. Viewing games themselves as hypergraphs, we analyze isomorphisms and the transfer of strategies within this setting. Finally, we construct a ‐algebra whose representation theory characterizes distinct classes of quantum isomorphisms between nonlocal games.

arXiv:2510.18679•Journal of the London Mathematical Society•Oct 1, 2026•0 citations

Curious properties of free hypergraph C*-algebras

Fritz, Tobias

A finite hypergraph $H$ consists of a finite set of vertices $V(H)$ and a collection of subsets $E(H) \subseteq 2^{V(H)}$ which we consider as partition of unity relations between projection operators. These partition of unity relations freely generate a universal C*-algebra, which we call the "free hypergraph C*-algebra" $C^*(H)$. General free hypergraph C*-algebras were first studied in the context of quantum contextuality. As special cases, the class of free hypergraph C*-algebras comprises quantum permutation groups, maximal group C*-algebras of graph products of finite cyclic groups, and the C*-algebras associated to quantum graph homomorphism, isomorphism, and colouring. Here, we conduct the first systematic study of aspects of free hypergraph C*-algebras. We show that they coincide with the class of finite colimits of finite-dimensional commutative C*-algebras, and also with the class of C*-algebras associated to synchronous nonlocal games. We had previously shown that it is undecidable to determine whether $C^*(H)$ is nonzero for given $H$. We now show that it is also undecidable to determine whether a given $C^*(H)$ is residually finite-dimensional, and similarly whether it only has infinite-dimensional representations, and whether it has a tracial state. It follows that for each one of these properties, there is $H$ such that the question whether $C^*(H)$ has this property is independent of the ZFC axioms, assuming that these are consistent. We clarify some of the subtleties associated with such independence results in an appendix.

arXiv:1808.09220•Journal of Operator Theory•Aug 28, 2018•0 citations

Quantum games and synchronicity

Adina Goldberg

In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.

arXiv:2408.15444•Quantum•Jan 14, 2026•0 citations

Quantum polymorphism characterisation of commutativity gadgets in all quantum models

Eric Culf, Josse van Dobben de Bruyn, Peter Zeman

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.

quant-pharXiv:2604.01408•Apr 3, 2026•0 citations
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.
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.
Abstract We introduce and examine three subclasses of the family of quantum no-signalling (QNS) correlations introduced by Duan and Winter: quantum commuting, quantum and local. We formalise the notion of a universal TRO of a block operator isometry, define an operator system, universal for stochastic operator matrices, and realise it as a quotient of a matrix algebra. We describe the classes of QNS correlations in terms of states on the tensor products of two copies of the universal operator system and specialise the correlation classes and their representations to classical-to-quantum correlations. We study various quantum versions of synchronous no-signalling correlations and show that they possess invariance properties for suitable sets of states. We introduce quantum non-local games as a generalisation of non-local games. We define the operation of quantum game composition and show that the perfect strategies belonging to a certain class are closed under channel composition. We specialise to the case of graph colourings, where we exhibit quantum versions of the orthogonal rank of a graph as the optimal output dimension for which perfect classical-to-quantum strategies of the graph colouring game exist, as well as to non-commutative graph homomorphisms, where we identify quantum versions of non-commutative graph homomorphisms introduced by Stahlke.
Abstract We develop an algebraic and operational framework for quantum isomorphisms of hypergraphs, using tools from compact quantum group theory. We introduce a new synchronous version of the hypergraph isomorphism game whose game algebra uniformly encodes multiple notions of quantum isomorphisms of hypergraphs. We show that there exist hypergraphs that are quantum isomorphic but not classically isomorphic. For graphs, we show that the ‐algebra of the hypergraph isomorphism game is a quotient of the ‐algebra of the graph isomorphism game. We further prove that the hypergraph game algebra forms a bi‐Galois extension over the quantum automorphism groups of the underlying hypergraphs. This allows us to deduce that the algebraic notion of a quantum isomorphism of hypergraphs coincides with the operational one coming from the existence of perfect quantum strategies. Viewing games themselves as hypergraphs, we analyze isomorphisms and the transfer of strategies within this setting. Finally, we construct a ‐algebra whose representation theory characterizes distinct classes of quantum isomorphisms between nonlocal games.
A finite hypergraph HHH consists of a finite set of vertices V(H)V(H)V(H) and a collection of subsets E(H)⊆2V(H)E(H) \subseteq 2^{V(H)}E(H)⊆2V(H) which we consider as partition of unity relations between projection operators. These partition of unity relations freely generate a universal C*-algebra, which we call the "free hypergraph C*-algebra" C∗(H)C^*(H)C∗(H). General free hypergraph C*-algebras were first studied in the context of quantum contextuality. As special cases, the class of free hypergraph C*-algebras comprises quantum permutation groups, maximal group C*-algebras of graph products of finite cyclic groups, and the C*-algebras associated to quantum graph homomorphism, isomorphism, and colouring. Here, we conduct the first systematic study of aspects of free hypergraph C*-algebras. We show that they coincide with the class of finite colimits of finite-dimensional commutative C*-algebras, and also with the class of C*-algebras associated to synchronous nonlocal games. We had previously shown that it is undecidable to determine whether C∗(H)C^*(H)C∗(H) is nonzero for given HHH. We now show that it is also undecidable to determine whether a given C∗(H)C^*(H)C∗(H) is residually finite-dimensional, and similarly whether it only has infinite-dimensional representations, and whether it has a tracial state. It follows that for each one of these properties, there is HHH such that the question whether C∗(H)C^*(H)C∗(H) has this property is independent of the ZFC axioms, assuming that these are consistent. We clarify some of the subtleties associated with such independence results in an appendix.
In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.
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.