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.12039 · Studia Mathematica

Products of synchronous games

Laura Mančinska, Vern I. Paulsen, Ivan G. Todorov, Andreas Winter

Published Jan 1, 2023• 6 citations
arXivHTMLPDF

Abstract

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

DOI
10.4064/sm221201-19-4

Related papers

Algebras, Synchronous Games and Chromatic Numbers of Graphs

J. William Helton, Kyle Meyer, Vern I. Paulsen +1 more

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.

arXiv:1703.00960•Mar 2, 2017•33 citations

Perfect Quantum Approximate Strategies for Imitation Games

Liang Hao, T. Yu, Lihong Zhi

We prove that an imitation game has a perfect quantum approximate strategy if and only if there exists a bi-tracial state on the minimal tensor product of two universal C${^*}$-algebras, which induces the perfect correlation. Moreover, we are trying to relate imitation games to the minimal tensor product of two universal C${^*}$-algebras and demonstrate that an imitation game has a perfect quantum approximate strategy if and only if there exist a von Neumann algebra and an amenable tracial state on it, such that the perfect correlation can be induced by the tracial state. However, We encountered some difficulties regarding continuity in the proof process. In section 2 we get some results for special cases, and in section 3 we list our problems.

arXiv:2410.09525•Oct 12, 2024•0 citations

Transfer of quantum game strategies

Gage Hoefer

We develop a method for the transfer of perfect strategies between various classes of two-player, one round cooperative non-local games with quantum inputs and outputs using the simulation paradigm in quantum information theory. We show that such a transfer is possible when canonically associated operator spaces for each game are quantum homomorphic or isomorphic, as defined in the joint work of H. and Todorov (2024). We examine a new class of QNS correlations, needed for the transfer of strategies between games, and characterize them in terms of states on tensor products of canonical operator systems. We define jointly tracial correlations and show they correspond to traces acting on tensor products of canonical ${\rm C}^{*}$-algebras associated with individual game parties. We then make an inquiry into the initial application of such results to the study of concurrent quantum games.

arXiv:2410.09599•Oct 12, 2024•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

Synchronous games with *-isomorphic game algebras

Samuel J. Harris

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.

arXiv:2109.04859•Quantum Information and Computation•Aug 1, 2022•2 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 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
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 prove that an imitation game has a perfect quantum approximate strategy if and only if there exists a bi-tracial state on the minimal tensor product of two universal C∗{^*}∗-algebras, which induces the perfect correlation. Moreover, we are trying to relate imitation games to the minimal tensor product of two universal C∗{^*}∗-algebras and demonstrate that an imitation game has a perfect quantum approximate strategy if and only if there exist a von Neumann algebra and an amenable tracial state on it, such that the perfect correlation can be induced by the tracial state. However, We encountered some difficulties regarding continuity in the proof process. In section 2 we get some results for special cases, and in section 3 we list our problems.
We develop a method for the transfer of perfect strategies between various classes of two-player, one round cooperative non-local games with quantum inputs and outputs using the simulation paradigm in quantum information theory. We show that such a transfer is possible when canonically associated operator spaces for each game are quantum homomorphic or isomorphic, as defined in the joint work of H. and Todorov (2024). We examine a new class of QNS correlations, needed for the transfer of strategies between games, and characterize them in terms of states on tensor products of canonical operator systems. We define jointly tracial correlations and show they correspond to traces acting on tensor products of canonical C∗{\rm C}^{*}C∗-algebras associated with individual game parties. We then make an inquiry into the initial application of such results to the study of concurrent quantum games.
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∗.
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.
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.