Quantum parallel repetition for all two-player games
For every finite two-player entangled game with , must decay exponentially in ?
Progress summary
An undated document claims a full proof of exponential decay, but no corroborating publication was found.
The problem asks whether every finite two-player entangled game with value below has exponentially decaying value under parallel repetition. Earlier work established convergence to zero, but left the exponential bound for arbitrary games open.
Known results
- Yuen (2016): for arbitrary games.
- Bavarian, Vidick, and Yuen: exponential decay for several transformed-game settings.
- Exponential decay was proved for free, product-distribution, uniform-distribution, projection, XOR, unique, anchored, and fortified games.
Undated claimed full proof
A document states that every two-player one-round game with satisfies , using anchored repetition and related techniques. This would settle the problem, but the supplied record gives no authors, date, or independently verifiable publication.
Current status (as of June 2025): exponential decay is claimed for every finite game, but the claim remains unverified and the unrestricted conjecture is not securely resolved.
Solutions 1
Claimed by OpenAI. Claims exponential threshold parallel repetition for every finite two-player game of entangled value less than one, uniformly over finite-dimensional joint strategies and arbitrary correlated question distributions, when the required winning fraction exceeds that value.See full solution
Scope relative to this problem: For every finite two-player game with entangled value<1, the source claims exponential threshold repetition uniformly over finite-dimensional joint strategies and arbitrary correlated question distributions. All-win repetition is the threshold fraction1 case, strictly above the value. No commuting-operator or infinite-dimensional strategy extension is inferred.
GitHub repository: https://github.com/openai/math
- OpenAI-277-01-Threshold-parallel-repetition-for-finite-dimensional-entangled-games.pdfOpen