Synchronous games with $*$-isomorphic game algebras

• URL: http://arxiv.org/abs/2109.04859v1
• Date: Fri, 10 Sep 2021 13:19:14 GMT
• Title: Synchronous games with $*$-isomorphic game algebras
• Authors: Samuel J. Harris
• Abstract summary: We 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. 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 exhibit a bisynchronous game with $20$ questions and $20$ answers that has a non-zero game algebra, but no winning commuting strategy, 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.

Related papers

• Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions [0.0]
  We prove the equivalence between the hereditary and $C*$ models questioned in (Helton et al., New York J. Math.) We also extend the quantum-version NP-hardness reduction $texttt3-SAT* leq_p textttClique*$ by exhibiting another instance of such reduction.
  arXiv  Detail & Related papers  (2024-08-19T16:01:21Z)
• The complexity of approximate (coarse) correlated equilibrium for incomplete information games [16.96984593866157]
  We study the complexity of decentralized learning of approximate correlated equilibria in incomplete information games. Our lower bound holds even for the easier solution concept of $epsilon$-approximate $mathitco$ correlated equilibrium.
  arXiv  Detail & Related papers  (2024-06-04T14:35:27Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  We show that quantum graph parameters encode winning strategies for all possible synchronous non-local games. Winning strategies for a synchronous game can be transformed into winning strategies for an associated graph coloring game.
  arXiv  Detail & Related papers  (2023-05-29T14:28:28Z)
• Quantum free games [2.298932494750101]
  We show a BellQMA(2) protocol for 3SAT on $n$ variables, where the total amount of communication is $tildeO(sqrtn)
  arXiv  Detail & Related papers  (2023-02-08T20:32:24Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games. This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
  arXiv  Detail & Related papers  (2022-02-03T18:18:28Z)
• The connection between the $PQ$ penny flip game and the dihedral groups [0.0]
  We show that the PQ penny flip game can be associated with the dihedral group $D_8$. We establish precisely two different sequences of states that can guaranteed Q's win with probability $1.0$. We consider general extensions of the game with the quantum player having $U(2)$ at his disposal.
  arXiv  Detail & Related papers  (2021-04-25T01:41:36Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. We propose an optimistic variant of the emphNash Q-learning algorithm with sample complexity $tildemathcalO(SAB)$, and a new emphNash V-learning algorithm with sample complexity $tildemathcalO(S(A+B))$.
  arXiv  Detail & Related papers  (2020-06-22T05:00:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.