Why repeating an entangled game eventually works
Must perfect success become exponentially unlikely when a quantum game is repeated?
Repetition is the oldest error-reduction trick in the book: run the test many times and demand a perfect score. For entangled players, however, the referee’s independent questions do not make the players’ answers independent. The claimed advance is a universal proof that their all-win probability still falls exponentially. 1manuscript
Why repetition is not multiplication
A referee separates Alice and Bob, gives them related questions, and prevents communication after the questions arrive. If their optimal strategy wins 80% of the time, repetition should make perfect success less likely: run many fresh instances and accept only when every answer is correct.
If the attempts were independent, eight wins would have chance 0.88 ≈ 16.8%. But Alice and Bob can answer all eight instances using one coordinated strategy. In the quantum version, they may also share entanglement and make measurements that treat the entire question list jointly. Multiplying 0.8 eight times therefore assumes precisely the independence the theorem must establish.
Can correlation keep “win everything” surprisingly likely forever? The theorem says no: for every finite two-player entangled game whose one-shot value is below 1, the all-win probability has an exponential ceiling as repetitions grow. 1manuscript
Why multiplication alone fails
The referee samples each coordinate independently. But Alice sees her whole question tuple and may make one joint measurement; Bob can do the same. A repeated strategy therefore need not factor into a product of one-game strategies. Playing independently proves only a lower bound, ω*(G⊗n) ≥ ω*(G)n—the wrong direction for soundness. 1manuscript
Even knowing that the strategy expects many losses does not control the chance of zero losses. At the correlation extreme, all outcomes could move together: either every instance wins or every instance loses. The proof has to rule out this concentration without assuming independence. 6walkthrough
Under independence, the all-win chance is 0.88.
Suppose one finite repeated-game strategy beats the claimed exponential ceiling. The proof will turn it into an impossible one-game strategy.
What came before
Raz proved the classical parallel-repetition theorem for arbitrary finite two-player games: if a one-game strategy cannot win perfectly, the repeated all-win value falls exponentially. 2Raz Quantum results later covered important structured families, including XOR, unique, projection, and free games. But those structures do not include every predicate and correlated question distribution. 1manuscript
Yuen’s 2016 theorem applied to every finite entangled game without changing it, but guaranteed polynomial decay rather than exponential decay. 3Yuen Bavarian, Vidick, and Yuen achieved exponential amplification through anchoring: modifying the game by inserting special anchor questions. That is powerful for hardness amplification, but it is not a theorem about standard repetition of the unchanged original game. 4Bavarian
Technical layer · games and entangled value
A finite game G = (X, Y, A, B, μ, V) has finite question sets X, Y; finite answer sets A, B; question distribution μ; and win predicate V. Its entangled value ω*(G) is the supremum win probability over all finite-dimensional shared states and local measurements.
In G⊗n, the referee draws n independent question pairs and accepts only if V = 1 in every coordinate. The players still return classical answers, but each player’s measurement may depend on their entire n-question tuple. 1manuscript
The bottleneck: conditioning creates two debts
The proof begins in the style of Yuen: suppose a repeated strategy wins too often, select a small “core” of coordinates, and condition on winning that core. A random coordinate outside the core must then win with high conditional probability. This is useful—but the successful branch may be exponentially rare. Dividing every estimate by that tiny probability would destroy an exponential bound. 6walkthrough
Quantum conditioning adds a second debt. A measurement effect fixes the probability of a branch, but not a unique vector representation of the postselected state. Neighboring local descriptions can choose incompatible purification frames—a kind of quantum phase mismatch, or holonomy. Matching ordinary classical marginals does not automatically give Alice and Bob one legal shared state they can prepare locally. 6walkthrough
Normalizing too early turns a small error into error ÷ p.
Alice and Bob can describe nearby states in incompatible frames.
Astra’s move: preserve the Born weight
The exploratory insight was to change the purification gauge without changing observable probability. For a positive measurement effect F, the proof constructs a cross operator Γ(F) satisfying Γ(F)†Γ(F) = F. Therefore the squared length of the unnormalized branch remains exactly its Born-rule probability. 7manuscript
The final construction is a resolvent purification. Instead of taking one matrix square root √F, it spreads F across scales using F(F + uI)−1. For any fixed finite strategy the required auxiliary span is still finite-dimensional. Crucially, the comparison cost is controlled by an operator-entropy drop without paying for the smallest eigenvalue. 7manuscript
Technical layer · the resolvent identity
For a scalar σ ≥ 0, the identity ∫0∞(σ/(σ + u))² du = σ is the engine behind Γ(F)†Γ(F) = F. Spectral calculus applies that scalar identity to every eigenvalue of F. 7manuscript
The derivative of √F contains denominators √λi + √λj. Tiny eigenvalues can make direct comparison expensive. The resolvent identity reorganizes the difference so its squared movement is bounded by an entropy gap H(F̄) − E H(F), even when F is singular. 6walkthrough
The live coordinate makes the rare branch pay for itself
One coordinate stays “live”: neither question there is revealed. Other questions are exposed in a size-biased random orientation and random order. In one direction, Alice’s successive conditional effects form a martingale while Bob’s effect stays fixed; reversing the orientation swaps their roles. The live coordinate becomes a uniformly random martingale increment. 8manuscript
The resolvent entropy bound telescopes along that reveal sequence. More importantly, it remains weighted by the branch’s actual Born probability. When normalized-state distance introduces a dangerous denominator, the same branch weight cancels it before averaging. The cost becomes log(1/p), not 1/p. This is what survives exponentially rare postselection. 8manuscript
Classical correlated sampling synchronizes the locally generated histories. Quantum correlated sampling then helps prepare nearby shared states on matching histories, using a finite embezzlement catalyst. The proof uses Dinur, Steurer, and Vidick’s quantum correlated-sampling lemma at this rounding step. 5Dinur
- 01Branch effect Fan unnormalized winning branch
- 02Resolvent Γ(F)Æà = F preserves its squared length
- 03Born weight pprobability remains attached to the error
- 04Live coordinateentropy telescopes while views align
- 05One-game strategycorrelated sampling completes the round
The contradiction, in five moves
- Assume one finite strategy for G⊗n beats the proposed exponential ceiling.
- Condition on winning a small core, making a random remaining coordinate almost surely win.
- Preserve the conditioned branch’s exact Born weight with resolvent purification.
- Reveal around one live coordinate so entropy telescopes and local views become close.
- Round those views into a legal one-game strategy that wins more often than ω*(G)—a contradiction. 1manuscript
Exact result and scope
Let ε = 1 − ω*(G) > 0 and ℓ = log(|A||B|). The manuscript claims a universal constant cqs > 0 such that, for every integer n ≥ 1,
ω*(G⊗n) ≤ exp(−cqs · ε13/(ε + ℓ) · n). 1manuscript
This applies to every finite two-player, one-round entangled game with nonempty finite answer alphabets. It does not require full support of μ, a bound on question-alphabet size, connected support, or a uniform bound on strategy dimension. The prefactor is 1, so the statement covers every positive n, not only sufficiently large repetitions. 1manuscript
The power 13 is explicitly not claimed optimal; it comes from quantitative losses in correlated sampling. The theorem says exponential decay exists universally, not that this is the best exponent for a given game. 1manuscript
Is the claim overhyped?
If the manuscript and formalization withstand independent scrutiny, this closes the standard qualitative quantum parallel-repetition question for finite two-player one-round games. The scope is broad, but not every quantum protocol and not an optimal rate.
“Standard repetition works exponentially for every finite two-player entangled game below value one.”
That is exactly the qualitative content of Theorem 1.1: the original game is repeated unchanged and the all-win value has an e−cGn ceiling. 1manuscript
“The proof removes the rare-postselection denominator.”
More precisely, Born-weighted resolvent estimates make the branch probability cancel before normalization is averaged, leaving logarithmic information cost rather than an inverse branch-probability loss. 6walkthrough
“Entanglement can no longer help in repeated games.”
False. Entanglement may still change one-shot and repeated values, and joint strategies remain correlated. The result supplies an exponential upper bound when ω*(G) < 1; it does not force ω*(G⊗n) = ω*(G)n. 1manuscript
“The theorem is formally verified and independently settled.”
The public Lean file states both the explicit distribution-uniform bound and the qualitative standard-repetition theorem. 9formal artifact The repository labels its review status “agent-reviewed,” so independent expert validation should remain a separate claim. 10formal artifact
Full bibliography
10 fully annotated sources
- 01 · primary manuscript
OpenAI. Exponential Parallel Repetition for All Two-Player Entangled Games — Chapter 6, pp. 153–154, Theorem 1.1 and §1.2 (PDF pp. 155–156). States the distribution-uniform exponential bound, its scope, quantitative exponent, and previous-work comparison. ↩
- 02 · peer-reviewed predecessor
Ran Raz. A Parallel Repetition Theorem — SIAM Journal on Computing 27 (1998), main theorem, pp. 763–803. The classical theorem establishing exponential decay for arbitrary finite two-player games. ↩
- 03 · peer-reviewed predecessor
Henry Yuen. A Parallel Repetition Theorem for All Entangled Games — ICALP 2016, Theorem 1. The prior theorem for arbitrary entangled games, with polynomial rather than exponential decay. ↩
- 04 · peer-reviewed predecessor
Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Hardness Amplification for Entangled Games via Anchoring — STOC 2017, Theorem 1 and pp. 303–316. Obtains exponential amplification after transforming a game by adding anchors. ↩
- 05 · peer-reviewed predecessor
Irit Dinur, David Steurer, and Thomas Vidick. A Parallel Repetition Theorem for Entangled Projection Games — Computational Complexity 24(2), 201–254 (2015); correlated-sampling lemma in the full version. Supplies the quantum correlated-sampling result used by the new rounding argument. ↩
- 06 · reasoning walkthrough
OpenAI. Quantum Parallel Repetition: From Holonomy to Resolvent Purification — Chapter 7, §§7.1–7.6, PDF pp. 33–36. Explains the failed reductions, probability and phase losses, Born-weight principle, resolvent construction, and live-coordinate martingale. ↩
- 07 · primary manuscript
OpenAI. Exponential Parallel Repetition for All Two-Player Entangled Games — Chapter 6, §3.2, equations (4)–(5), and §4.2, Definition 4.2 and equation (24) (PDF pp. 161 and 171). Defines the probability-preserving cross operator and finite resolvent purification. ↩
- 08 · primary manuscript
OpenAI. Exponential Parallel Repetition for All Two-Player Entangled Games — Chapter 6, Lemma 4.1 and Lemmas 4.3–4.4, equations (21)–(28) (PDF pp. 170–173). Builds the random live-coordinate martingales and proves the telescoping entropy control. ↩
- 09 · formal certificate
OpenAI. QuantumParallelRepetition.lean — theorems distributionUniformExponential and standardQuantumParallelRepetition. Formal statements include the explicit ε¹³ rate and qualitative exponential repetition conclusion. ↩
- 10 · formal certificate
OpenAI. Formalization metadata — review.status and project.status.main_results, entry “Quantum parallel repetition”. The repository describes its review status as “agent-reviewed.” ↩