Posted

Andrea Coladangelo, Qipeng Liu, Ziyi Xie (Sep 03 2025).
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 ABC\mathsf{ABC}; register A\mathsf{A}, consisting of nn qubits, is sent to a Referee, while B\mathsf{B} and C\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 nn-bit outcome string xx. Tomamichel et al. show that the optimal winning probability is cos2n(π8)\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 xx. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in nn. 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 cos2(π8)0.85\cos^2{(\frac{\pi}{8})} \approx 0.85 for any nn. - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random nn-bit string rr that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of rxr\cdot x. We show that the optimal advantage over random guessing decays exponentially in nn for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and Ç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.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!