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

Algebras, Synchronous Games and Chromatic Numbers of Graphs

J. William Helton, Kyle Meyer, Vern I. Paulsen, Matthew Satriano

Published Mar 2, 2017• 33 citations
arXivHTMLPDF

Abstract

We associate to each synchronous game an algebra whose representations determine if the game has a perfect deterministic strategy, perfect quantum strategy or one of several other perfect strategies. when applied to the graph coloring game, this leads to characterizations in terms of properties of an algebra of various quantum chromatic numbers that have been studied in the literature. This allows us to develop a correspondence between various chromatic numbers of a graph and ideals in this algebra which can then be approached via various Grobner basis methods.

DOI
10.48550/arxiv.1703.00960

Related papers

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

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

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

Synchronous correlation matrices and Connes’ embedding conjecture

Kenneth J. Dykema, Vern Paulsen

In the work of Paulsen et al. [J. Funct. Anal. (in press); preprint arXiv:1407.6918], the concept of synchronous quantum correlation matrices was introduced and these were shown to correspond to traces on certain C*-algebras. In particular, synchronous correlation matrices arose in their study of various versions of quantum chromatic numbers of graphs and other quantum versions of graph theoretic parameters. In this paper, we develop these ideas further, focusing on the relations between synchronous correlation matrices and microstates. We prove that Connes’ embedding conjecture is equivalent to the equality of two families of synchronous quantum correlation matrices. We prove that if Connes’ embedding conjecture has a positive answer, then the tracial rank and projective rank are equal for every graph. We then apply these results to more general non-local games.

arXiv:1503.07207•Journal of Mathematical Physics•Dec 10, 2015•28 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

Products of synchronous games

Laura Mančinska, Vern I. Paulsen, Ivan G. Todorov +1 more

We show that the $^*$-algebra of the product of two synchronous games is the tensor product of the corresponding $^*$-algebras. We prove that the product game has a perfect C$^*$-strategy if and only if each of the individual games does, and that in this

arXiv:2109.12039•Studia Mathematica•Jan 1, 2023•6 citations
We associate to each synchronous game an algebra whose representations determine if the game has a perfect deterministic strategy, perfect quantum strategy or one of several other perfect strategies. when applied to the graph coloring game, this leads to characterizations in terms of properties of an algebra of various quantum chromatic numbers that have been studied in the literature. This allows us to develop a correspondence between various chromatic numbers of a graph and ideals in this algebra which can then be approached via various Grobner basis methods.
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.
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 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.
In the work of Paulsen et al. [J. Funct. Anal. (in press); preprint arXiv:1407.6918], the concept of synchronous quantum correlation matrices was introduced and these were shown to correspond to traces on certain C*-algebras. In particular, synchronous correlation matrices arose in their study of various versions of quantum chromatic numbers of graphs and other quantum versions of graph theoretic parameters. In this paper, we develop these ideas further, focusing on the relations between synchronous correlation matrices and microstates. We prove that Connes’ embedding conjecture is equivalent to the equality of two families of synchronous quantum correlation matrices. We prove that if Connes’ embedding conjecture has a positive answer, then the tracial rank and projective rank are equal for every graph. We then apply these results to more general non-local games.
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.
We show that the ∗^*∗-algebra of the product of two synchronous games is the tensor product of the corresponding ∗^*∗-algebras. We prove that the product game has a perfect C∗^*∗-strategy if and only if each of the individual games does, and that in this