3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time

• URL: http://arxiv.org/abs/2010.16290v2
• Date: Wed, 9 Aug 2023 01:12:46 GMT
• Title: 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
• Authors: Adam Bene Watts and J. William Helton
• Abstract summary: We consider 3XOR games with perfect commuting operator strategies. We show existence of a perfect commuting operator strategy for the game can be decided in time.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider 3XOR games with perfect commuting operator strategies. Given any 3XOR game, we show existence of a perfect commuting operator strategy for the game can be decided in polynomial time. Previously this problem was not known to be decidable. Our proof leads to a construction, showing a 3XOR game has a perfect commuting operator strategy iff it has a perfect tensor product strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect 3XOR games the advantage of a quantum strategy over a classical strategy (defined by the quantum-classical bias ratio) is bounded. This is in contrast to the general 3XOR case where the optimal quantum strategies can require high dimensional states and there is no bound on the quantum advantage. To prove these results, we first show equivalence between deciding the value of an XOR game and solving an instance of the subgroup membership problem on a class of right angled Coxeter groups. We then show, in a proof that consumes most of this paper, that the instances of this problem corresponding to 3XOR games can be solved in polynomial time.

Related papers

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
  arXiv  Detail & Related papers  (2024-06-23T00:27:28Z)
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [10.187610891144452]
  We show that the compiler proposed by Kalai et al. is sound for any two-player XOR game. Using our techniques, we obtain several additional results, including tight bounds on the compiled value of parallel-repeated XOR games.
  arXiv  Detail & Related papers  (2024-02-27T08:24:21Z)
• Repeated quantum game as a stochastic game: Effects of the shadow of the future and entanglement [0.0]
  We present a systematic investigation of the quantum games, constructed using a novel repeated game protocol. We find that how two pure strategies fare against each other is crucially dependent on the discount factor. In the quantum game setup, always-defect strategy can be beaten by the tit-for-tat strategy for high enough discount factor.
  arXiv  Detail & Related papers  (2023-12-08T15:54:51Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• On the power of quantum entanglement in multipartite quantum XOR games [3.655021726150368]
  In particular, quantum entanglement can be a much more powerful resource than local operations and classical communication to play these games. This result shows a strong contrast to the bipartite case, where it was recently proved that the entangled bias is always upper bounded by a universal constant times the one-way classical communication bias.
  arXiv  Detail & Related papers  (2023-02-23T06:26:37Z)
• Satisfiability Phase Transtion for Random Quantum 3XOR Games [0.0]
  We numerically study the behavior of randomly generated 3XOR games with large numbers of questions. Our experiments strongly indicate that the probability of a randomly generated game being pseudotelpathic stays far from 1. We also find strong evidence that randomly generated 3XOR games undergo both a quantum and classical "phase transition"
  arXiv  Detail & Related papers  (2022-09-10T12:54:53Z)
• Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states [0.0]
  In particular, we show that near-perfect quantum strategies are approximate representations of the corresponding BCS algebra in the little Frobenius norm. For the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding *-algebra associated with the game.
  arXiv  Detail & Related papers  (2022-03-04T19:05:58Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.