Winning Rates of $(n,k)$ Quantum Coset Monogamy Games

• URL: http://arxiv.org/abs/2501.17736v1
• Date: Wed, 29 Jan 2025 16:21:34 GMT
• Title: Winning Rates of $(n,k)$ Quantum Coset Monogamy Games
• Authors: Michael Schleppy, Emina Soljanin,
• Abstract summary: We formulate the $(n,k)$ Coset Monogamy Game, in which two players must extract complementary information from a random coset state without communicating. Our game generalizes those considered in previous works that deal with the case of equal information size $(k=fracn2)$.
• Score: 9.029985847202669
• License:
• Abstract: We formulate the $(n,k)$ Coset Monogamy Game, in which two players must extract complementary information of unequal size ($k$ bits vs. $n-k$ bits) from a random coset state without communicating. The complementary information takes the form of random Pauli-X and Pauli-Z errors on subspace states. Our game generalizes those considered in previous works that deal with the case of equal information size $(k=\frac{n}{2})$. We prove a convex upper bound of the information-theoretic winning rate of the $(n,k)$ Coset Monogamy Game in terms of the subspace rate $R=\frac{k}{n}\in [0,1]$. This bound improves upon previous results for the case of $R=\frac{1}{2}$. We also prove the achievability of an optimal winning probability upper bound for the class of unentangled strategies of the $(n,k)$ Coset Monogamy Game.

Related papers

• Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem [0.0]
  We prove that to each synchronous non-local game $mathcalG=(I,O,lambda)$ with $|I|=n$ and $O=m geq 3$, there is an associated graph $G_lambda$. We also prove that there exists an $alpha in (0,1)$ for which determining whether the non-commutative Max-$3$-Cut of a graph is $E|$ or less than $alpha |E|$ is RE-hard.
  arXiv  Detail & Related papers  (2024-12-27T02:05:37Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  An equilibrium can be computed at a fast rate of $O(log T)$ when all players follow the optimistic follow-the-regularized-leader (OFTRL) We present corrupted learning dynamics that adaptively find an equilibrium at a rate that depends on the extent to which each player deviates from the strategy suggested by the prescribed algorithm.
  arXiv  Detail & Related papers  (2024-12-10T02:23:44Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  We consider a contextual bandit problem with $S$ contexts and $K$ actions. We give an algorithm that outputs an $epsilon$-optimal policy after using at most $widetilde O(r (S +K )/epsilon2)$ samples. In the regret setting, we give an algorithm whose cumulative regret up to time $T$ is bounded by $widetilde O(sqrtr3(S+K)T)$.
  arXiv  Detail & Related papers  (2023-06-22T17:20:30Z)
• Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
  This paper makes progress towards learning Nash equilibria in two-player zero-sum Markov games from offline data. We propose a pessimistic model-based algorithm with Bernstein-style lower confidence bounds -- called VI-LCB-Game.
  arXiv  Detail & Related papers  (2022-06-08T17:58:06Z)
• 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)
• Nonlocal games with noisy maximally entangled states are decidable [5.076419064097734]
  This paper considers a special class of nonlocal games $(G,psi)$, where $G$ is a two-player one-round game. In the game $(G,psi)$, the players are allowed to share arbitrarily many copies of $psi$. It is feasible to approximately compute $omega*(G,psi)$ to an arbitrarily precision.
  arXiv  Detail & Related papers  (2021-08-20T12:25:55Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Monogamy relations and upper bounds for the generalized $W$-class states using R\'{e}nyi-$\alpha$ entropy [0.0]
  We investigate monogamy relations and upper bounds for generalized $W$-class states related to the R'enyi-$alpha$ entropy. We apply our results into quantum games and present a new bound of the nonclassicality of quantum games restricting to generalized $W$-class states.
  arXiv  Detail & Related papers  (2020-04-30T09:27:40Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.