Rigidity for Monogamy-of-Entanglement Games

• URL: http://arxiv.org/abs/2111.08081v2
• Date: Wed, 1 Mar 2023 20:41:16 GMT
• Title: Rigidity for Monogamy-of-Entanglement Games
• Authors: Anne Broadbent and Eric Culf
• Abstract summary: We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. We also show rigidity for multiple copies of the game played in parallel.
• Score: 0.6091702876917281
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In a monogamy-of-entanglement (MoE) game, two players who do not communicate try to simultaneously guess a referee's measurement outcome on a shared quantum state they prepared. We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis and informs the players of her choice. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. That is, in order to win optimally, the players' strategy must be of a specific form, namely a convex combination of four unentangled optimal strategies generated by the Breidbart state. We extend this to show that strategies that win near-optimally must also be near an optimal state of this form. We also show rigidity for multiple copies of the game played in parallel. We give three applications: (1) We construct for the first time a weak string erasure (WSE) scheme where the security does not rely on limitations on the parties' hardware. Instead, we add a prover, which enables security via the rigidity of this MoE game. (2) We show that the WSE scheme can be used to achieve bit commitment in a model where it is impossible classically. (3) We achieve everlasting-secure randomness expansion in the model of trusted but leaky measurement and untrusted preparation and measurements by two isolated devices, while relying only on the temporary assumption of pseudorandom functions. This achieves randomness expansion without the need for shared entanglement.

Related papers

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  We formulate a new variant of multi-player multi-armed bandit (MAB) model, which captures arrival of requests to each arm and the policy of allocating requests to players. The challenge is how to design a distributed learning algorithm such that players select arms according to the optimal arm pulling profile. We design an iterative distributed algorithm, which guarantees that players can arrive at a consensus on the optimal arm pulling profile in only M rounds.
  arXiv  Detail & Related papers  (2024-08-20T13:57:00Z)
• 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)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  equilibria in multiplayer games are neither unique nor non-exploitable. This paper takes an initial step towards addressing these challenges by focusing on the natural objective of equal share. We design a series of efficient algorithms, inspired by no-regret learning, that provably attain approximate equal share across various settings.
  arXiv  Detail & Related papers  (2024-06-06T15:59:17Z)
• Permissible extensions of classical to quantum games combining three strategies [0.0]
  We study the extension of classical games to the quantum domain. We use the obtained results to extend the classical Prisoner's Dilemma game to a quantum game.
  arXiv  Detail & Related papers  (2024-04-09T10:38:10Z)
• State-Constrained Zero-Sum Differential Games with One-Sided Information [19.964883571758502]
  We study zero-sum differential games with state constraints and one-sided information. Our contribution is an extension to games with state constraints and the derivation of the primal and dual subdynamic principles necessary for computing behavioral strategies.
  arXiv  Detail & Related papers  (2024-03-05T07:51:38Z)
• Device independent security of quantum key distribution from monogamy-of-entanglement games [10.60608983034705]
  We propose a general device independent quantum key distribution protocol for non-local games. We numerically optimize the finite and tripartite secret key rates of our protocol. We show that our protocol is robust for depolarizing noise up to about $2.2%$, providing the first such bound for general attacks for magic square based quantum key distribution.
  arXiv  Detail & Related papers  (2023-12-07T06:48:38Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Parallel repetition of local simultaneous state discrimination [12.984519159674525]
  Local simultaneous state discrimination is a recently introduced problem in quantum information processing. We investigate the advantage of no-signalling strategies over classical ones. We show numerically that for three players and binary values, no-signalling strategies cannot provide any improvement over classical ones.
  arXiv  Detail & Related papers  (2022-11-11T19:33:46Z)
• A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
  We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions. We provide two simple algorithms of solving them with necessarily strong convergence.
  arXiv  Detail & Related papers  (2021-03-24T22:33:11Z)
• 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)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-02-19T21:36:58Z)

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.