← All problems

Quantum parallel repetition for all two-player games

13 years old · traced to

For every finite two-player entangled game GG with ω∗(G)<1\omega^*(G)<1, must ω∗(G⊗n)\omega^*(G^{\otimes n}) decay exponentially in nn?

References

Progress summary

Refreshed
Open · solution reported

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 11 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): val∗(G⊗n)≤cGn−1/4log⁡n\mathrm{val}^*(G^{\otimes n})\leq c_G n^{-1/4}\log n 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 val⁡∗(G)<1\operatorname{val}^*(G)<1 satisfies val⁡∗(G⊗n)≤Ce−cn\operatorname{val}^*(G^{\otimes n})\leq Ce^{-cn}, 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.

Sources

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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Threshold-parallel-repetition-for-finite-dimensional-entangled-games-September-25-2026/paper.pdf

  • OpenAI-277-01-Threshold-parallel-repetition-for-finite-dimensional-entangled-games.pdf426,968 bytesOpen