The curious case of "XOR repetition" of monogamy-of-entanglement games

• URL: http://arxiv.org/abs/2509.01831v1
• Date: Mon, 01 Sep 2025 23:20:35 GMT
• Title: The curious case of "XOR repetition" of monogamy-of-entanglement games
• Authors: Andrea Coladangelo, Qipeng Liu, Ziyi Xie,
• Abstract summary: We consider "decision" variants of a monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner.<n>We show that the optimal advantage over random guessing decays exponentially in $n$ for the restricted class of adversaries that do not share entanglement.
• Score: 5.3543990359738585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we consider "decision" variants of a monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner [New Journal of Physics '13]. In its original "search" variant, Alice prepares a (possibly entangled) state on registers $\mathsf{ABC}$; register $\mathsf{A}$, consisting of $n$ qubits, is sent to a Referee, while $\mathsf{B}$ and $\mathsf{C}$ are sent to Bob and Charlie; the Referee then measures each qubit in the standard or Hadamard basis (chosen uniformly at random). The basis choices are sent to Bob and Charlie, whose goal is to simultaneously guess the Referee's $n$-bit outcome string $x$. Tomamichel et al. show that the optimal winning probability is $\cos^{2n} {(\frac{\pi}{8})}$, following a perfect parallel repetition theorem. We consider the following "decision" variants of this game: - Variant 1, "XOR repetition": Bob and Charlie's goal is to guess the XOR of all the bits of $x$. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in $n$. Surprisingly, we show that this conjecture is false, and, in fact, there is no decay at all: there exists a strategy that wins with probability $\cos^2{(\frac{\pi}{8})} \approx 0.85$ for any $n$. - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random $n$-bit string $r$ that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of $r\cdot x$. We show that the optimal advantage over random guessing decays exponentially in $n$ for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and \c{C}akan et al.; we give a more direct proof. Additionally, we put forward a reasonably concrete conjecture that is equivalent to exponential decay for general adversaries.

Related papers

• Winning Rates of $(n,k)$ Quantum Coset Monogamy Games [9.029985847202669]
  We formulate the $(n,k)$ Coset Monogamy Game, in which two players must extract complementary information from a random coset state without communicating.<n>Our game generalizes those considered in previous works that deal with the case of equal information size $(k=fracn2)$.
  arXiv  Detail & Related papers  (2025-01-29T16:21:34Z)
• 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$.<n>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)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  We study the task of online learning in the presence of Massart noise. We present a computationally efficient algorithm that achieves mistake bound $eta T + o(T)$. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least $(1-1/k) Delta T - o(T)$ bigger than choosing a random action at every round.
  arXiv  Detail & Related papers  (2024-05-21T17:31:10Z)
• Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
  We revisit the noisy binary search model of Karp and Kleinberg. We produce an algorithm that succeeds with probability $1-delta$ from [ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta) right.
  arXiv  Detail & Related papers  (2023-11-01T20:45:13Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• 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)
• Experimental test of Tsirelson's bound with a single photonic qubit [8.8709589922781]
  In the Clauser-Horne-Shimony-Holt game, two space-like separated players, Alice and Bob are each assigned a classical bit $a$ and $b$ respectively. In the game, if the players use the classical strategies, the optimal success probability $w(textCHSH)=0.75$. Popescu and Rohrlich noted that the perfect success probability $1$ can also be achieved in a more general theory without violating the no-signaling assumption.
  arXiv  Detail & Related papers  (2022-01-25T09:06:53Z)
• 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)
• 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)
• 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)
• 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.