Abstract

In a two-player entangled game G, a referee sends a question to each of two noncommunicating players, receives their answers, and decides whether they win. The players may share an arbitrary entangled quantum state, and the supremum of their winning probabilities is the entangled value ω*(G). In the repeated game G^{⊗n}, the referee plays n independent copies and accepts only if the players win every copy. Raz’s celebrated classical parallel repetition theorem (STOC 1995) shows that, for classical players, the repeated value decreases exponentially whenever the original value is less than one. Whether the same holds for arbitrary entangled games has been a longstanding open problem. We resolve this quantum analogue affirmatively: for every finite two-player, one-round game G with ω*(G) = 1 - ε < 1 and answer alphabets A, B, ω*(G^{⊗n}) ≤ exp(-c_qs [ε^13 / (ε + log(|A||B|))] n), n ≥ 1, for a universal constant c_qs > 0. Previously, Yuen (ICALP 2016) proved polynomial decay for arbitrary entangled games, and Bavarian, Vidick, and Yuen (STOC 2017) proved exponential decay for anchored games obtained by modifying the original game. Our proof builds on Yuen’s conditioning and dependency-breaking framework. Its main new ingredient is a postselection-stable quantum sampleability estimate that avoids an inverse dependence on the probability of the conditioning event.

Personal information

Srijita Kundu completed her PhD at the Centre for Quantum Technologies in the National University of Singapore in 2021, under the supervision of Prof. Rahul Jain. From 2022 to 2025, she was a postdoctoral researcher at the Institute for Quantum Computing in the University of Waterloo, Canada. She is interested in quantum computational complexity, quantum information theory, and quantum cryptography.

Reference

https://cdn.openai.com/pdf/ten-proofs-oai.pdf