Math Conjectures

Quantum Parallel Repetition Conjecture

OPENMajorConjectureProposed 2004 · Standard version

Canonical statement

For every finite two-player one-round game GG whose entangled value satisfies ω∗(G)<1\omega^*(G)<1, there is a constant cG>0c_G>0 such that the entangled value of the nn-fold parallel repetition obeys
ω∗(G⊗n)≤e−cGn(n≥1). \omega^*(G^{\otimes n})\le e^{-c_G n}\qquad(n\ge1).
View source LaTeX
For every finite two-player one-round game \(G\) whose entangled value satisfies \(\omega^*(G)<1\), there is a constant \(c_G>0\) such that the entangled value of the \(n\)-fold parallel repetition obeys
\[
  \omega^*(G^{\otimes n})\le e^{-c_G n}\qquad(n\ge1).
\]
TCS-029:[CleveEtAl2004NonlocalGames][Yuen2016ParallelRepetition][BavarianVidickYuen2017Anchored][OpenAI2026TenAdvances]
Theoretical computer scienceInformation theoryMathematical physics

Notes

Classical parallel repetition underpins hardness amplification, but entanglement breaks many classical proof methods. Cleve, Høyer, Toner, and Watrous formulated the general nonlocal-game setting [CleveEtAl2004NonlocalGames]; Yuen obtained general polynomial decay [Yuen2016ParallelRepetition], and anchored games admit exponential decay [BavarianVidickYuen2017Anchored]. The announced all-game exponential theorem [OpenAI2026TenAdvances] awaits independent proof and certificate reproduction.

Proof-claim watch (1)

General quantum parallel repetition

Grade C

Full-scope theorem claim awaiting independent verification.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.