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:2109.04859 · Quantum Information and Computation

Synchronous games with *-isomorphic game algebras

Samuel J. Harris

Published Aug 1, 2022• 2 citations
arXivHTMLPDF

Abstract

We establish several strong equivalences of synchronous non-local games, in the sense that the corresponding game algebras are $*$-isomorphic. We first show that the game algebra of any synchronous game on $n$ inputs and $k$ outputs is $*$-isomorphic to the game algebra of an associated bisynchronous game on $nk$ inputs and $nk$ outputs. As a result, we show that there are bisynchronous games with equal question and answer sets, whose optimal strategies only exist in the quantum commuting model, and not in the quantum approximate model. Moreover, we show that there are bisynchronous games with equal question and answer sets that have non-zero game algebras, but no winning quantum commuting strategies, resolving a problem of V.I. Paulsen and M. Rahaman. We also exhibit a $*$-isomorphism between any synchronous game algebra with $n$ questions and $k>3$ answers and a synchronous game algebra with $n(k-2)$ questions and $3$ answers.

DOI
10.26421/qic22.11-12-2

Related papers

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

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions

Entong He

We review the correspondence between synchronous games and their associated $*$-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellensätze (Watts, Helton and Klep, Annales Henri Poincaré 2023), we build computational tools that check the non-existence of perfect $C^*$ and algebraic strategies of synchronous games using Gröbner basis methods and semidefinite programming. We prove the equivalence between the hereditary and $C^*$ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction $\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*$ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction $\texttt{3-SAT}^* \leq_p \texttt{Clique}^*$.

arXiv:2408.10114•Aug 19, 2024•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

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

Transitive nonlocal games

Prem Nigam Kar, Jitendra Prakash, David E. Roberson

We study a class of nonlocal games, called transitive games, for which the set of perfect strategies forms a semigroup. We establish several interesting correspondences of bisynchronous transitive games with the theory of compact quantum groups. In particular, we associate a quantum permutation group with each bisynchronous transitive game and vice versa. We prove that the existence of a C*-strategy, the existence of a quantum commuting strategy, and the existence of a classical strategy are all equivalent for bisynchronous transitive games. We then use some of these correspondences to establish necessary and sufficient conditions for some classes of correlations, that arise as perfect strategies of transitive games, to be nonlocal.

arXiv:2312.12040•Journal of Mathematical Physics•Jul 1, 2024•0 citations

A Characterization of Perfect Strategies for Mirror Games

Sizhuo Yan, Jianting Yang, T. Yu +1 more

We associate mirror games with the universal game algebra and use the *-representation to describe quantum commuting operator strategies. We provide an algebraic characterization of whether or not a mirror game has perfect commuting operator strategies. This new characterization uses a smaller algebra introduced by Paulsen and others for synchronous games and the noncommutative Nullstellensatz developed by Cimpric, Helton and collaborators. An algorithm based on noncommutative Gröbner basis computation and semidefinite programming is given for certifying that a given mirror game has no perfect commuting operator strategies.

arXiv:2302.04557•International Symposium on Symbolic and Algebraic Computation•Jul 5, 2023•4 citations
We establish several strong equivalences of synchronous non-local games, in the sense that the corresponding game algebras are ∗*∗-isomorphic. We first show that the game algebra of any synchronous game on nnn inputs and kkk outputs is ∗*∗-isomorphic to the game algebra of an associated bisynchronous game on nknknk inputs and nknknk outputs. As a result, we show that there are bisynchronous games with equal question and answer sets, whose optimal strategies only exist in the quantum commuting model, and not in the quantum approximate model. Moreover, we show that there are bisynchronous games with equal question and answer sets that have non-zero game algebras, but no winning quantum commuting strategies, resolving a problem of V.I. Paulsen and M. Rahaman. We also exhibit a ∗*∗-isomorphism between any synchronous game algebra with nnn questions and k>3k>3k>3 answers and a synchronous game algebra with n(k−2)n(k-2)n(k−2) questions and 333 answers.
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.
We review the correspondence between synchronous games and their associated ∗*∗-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellensätze (Watts, Helton and Klep, Annales Henri Poincaré 2023), we build computational tools that check the non-existence of perfect C∗C^*C∗ and algebraic strategies of synchronous games using Gröbner basis methods and semidefinite programming. We prove the equivalence between the hereditary and C∗C^*C∗ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction 3-SAT∗≤p3-Coloring∗\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*3-SAT∗≤p​3-Coloring∗ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction 3-SAT∗≤pClique∗\texttt{3-SAT}^* \leq_p \texttt{Clique}^*3-SAT∗≤p​Clique∗.
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.
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.
We study a class of nonlocal games, called transitive games, for which the set of perfect strategies forms a semigroup. We establish several interesting correspondences of bisynchronous transitive games with the theory of compact quantum groups. In particular, we associate a quantum permutation group with each bisynchronous transitive game and vice versa. We prove that the existence of a C*-strategy, the existence of a quantum commuting strategy, and the existence of a classical strategy are all equivalent for bisynchronous transitive games. We then use some of these correspondences to establish necessary and sufficient conditions for some classes of correlations, that arise as perfect strategies of transitive games, to be nonlocal.
We associate mirror games with the universal game algebra and use the *-representation to describe quantum commuting operator strategies. We provide an algebraic characterization of whether or not a mirror game has perfect commuting operator strategies. This new characterization uses a smaller algebra introduced by Paulsen and others for synchronous games and the noncommutative Nullstellensatz developed by Cimpric, Helton and collaborators. An algorithm based on noncommutative Gröbner basis computation and semidefinite programming is given for certifying that a given mirror game has no perfect commuting operator strategies.