Quantum method improves bounds on repeated two-player game wins
Parallel Repetition for Entangled Games via Conditional Relative Entropy
Computational ComplexityInformation Theory
Summary
The paper studies games where two players share quantum entanglement and answers to questions are repeated many times. It shows how the chance to win all or most of these repeated games decreases quickly, based on a new way to measure information using quantum relative entropy. The authors provide precise math bounds that explain how the winning probability drops with the number of repetitions and size of answers. Their results help understand the limits of quantum strategies in repeated interactions.
What this means in practice
- •For quantum cryptographers: Improve security analyses of quantum protocols by quantifying how repetition reduces adversary success probabilities in entangled settings.
- •For quantum algorithm designers: Guide design of multi-round quantum interactive protocols by understanding how repeated games constrain winning chances under entanglement.
A theory result. No direct application yet.
Authors
Rahul Jain
Abstract
We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value $1-\varepsilon<1$ and answer alphabets $\mathcal A,\mathcal B$, its $n$-fold repeated value is at most \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, \] for every $n\ge1$. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least $1-\varepsilon+δ$ is at most $\exp[-Ω(δ^5n/(\varepsilon^2L))]$ for $0<δ\le\varepsilon$. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.