OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Theorem 1.1: A uniform bound for every finite-dimensional joint strategy and the supremum over such strategies

Upper tails in entangled repetition decay exponentially.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

In parallel repetition, each player receives a string of questions and returns a string of answers. The upper tail measures the chance of winning a fraction of coordinates above the single-round entangled value.

A finite probability law pp on a finite set Ω\Omega is a nonnegative weight function of total mass one.✦ For a function ff on Ω\Omega with values in a real vector space, the expectation under pp is given by (1); for a finite index set II, the same equation gives the product law of finite probability laws pip_i on the common finite set Ω\Omega, with Ωi=Ω\Omega_i=\Omega and zi∈Ωz_i\in\Omega for every i∈Ii\in I. p(ω)≥0,∑ω∈Ωp(ω)=1,𝔼p[f]=∑ω∈Ωp(ω)f(ω),(⨂i∈Ipi)(z)=∏i∈Ipi(zi).p(\omega)\geq 0,\qquad \sum_{\omega\in\Omega}p(\omega)=1,\qquad \mathbb E_p[f]=\sum_{\omega\in\Omega}p(\omega)f(\omega),\qquad \Bigl(\bigotimes_{i\in I}p_i\Bigr)(z)=\prod_{i\in I}p_i(z_i).(1)

A finite two-player one-round game GG has finite nonempty question alphabets X,YX,Y and answer alphabets A,BA,B, a question law μ\mu on X×YX\times Y, and a Boolean acceptance predicate V:X×Y×A×B→{0,1}V:X\times Y\times A\times B\to\{0,1\}.✦ Write d=|A||B|d=|A||B|; all logarithms are natural.

A positive operator-valued measure (POVM) (Pa)a∈A(P_a)_{a\in A} on a finite-dimensional Hilbert space ℋ\mathcal H with outcome alphabet AA is a family of operators satisfying (2): Pa≽0(a∈A),∑a∈APa=Iℋ.P_a\succeq 0\quad(a\in A),\qquad \sum_{a\in A}P_a=I_{\mathcal H}.(2) An entangled strategy SS consists of local Hilbert spaces ℋA,ℋB\mathcal H_A,\mathcal H_B of positive finite dimensions, a unit vector |ψ⟩∈ℋA⊗ℋB|\psi\rangle\in\mathcal H_A\otimes\mathcal H_B, and local POVMs (Pax)a(P_a^x)_a and (Qby)b(Q_b^y)_b for each local question. In fixed orthonormal bases, the state coefficient matrix CC of an entangled strategy SS and the corresponding state vector |C⟩|C\rangle are given by (3), where ∥C∥HS2\|C\|_{\mathrm{HS}}^2 is the squared Hilbert-Schmidt norm: Cij=⟨i,j|ψ⟩,|C⟩=∑i,jCij|i⟩⊗|j⟩,∥C∥HS2=∑i,j|Cij|2=1.C_{ij}=\langle i,j|\psi\rangle,\qquad |C\rangle=\sum_{i,j}C_{ij}|i\rangle\otimes|j\rangle,\qquad \|C\|_{\mathrm{HS}}^2=\sum_{i,j}|C_{ij}|^2=1.(3)

For local operators E,FE,F, the bipartite operator expectation ℰC(E,F)\mathcal E_C(E,F) and its real part qC(E,F)q_C(E,F) are defined in (4). The same equation defines the Born probabilities pS(a,b∣x,y)p_S(a,b\mid x,y), the joint measurement distribution for the local POVMs: ℰC(E,F)=⟨C|E⊗F|C⟩,qC(E,F)=Re⁡ℰC(E,F),pS(a,b∣x,y)=qC(Pax,Qby).\begin{aligned} \mathcal E_C(E,F)&=\langle C|E\otimes F|C\rangle, &q_C(E,F)&=\operatorname{Re}\mathcal E_C(E,F),\\ p_S(a,b\mid x,y)&=q_C(P_a^x,Q_b^y). \end{aligned}(4) A single-round strategy SS for the game GG is an entangled strategy with question alphabets X,YX,Y and answer alphabets A,BA,B. The winning probability wG(S)w_G(S) of a single-round strategy SS for GG and the finite-dimensional entangled value vv of GG are defined by (5), with the supremum over all finite-dimensional single-round strategies for GG: wG(S)=∑x,yμ(x,y)∑a,bV(x,y,a,b)pS(a,b∣x,y),v=supSwG(S).w_G(S)=\sum_{x,y}\mu(x,y)\sum_{a,b}V(x,y,a,b)p_S(a,b\mid x,y), \qquad v=\sup_S w_G(S).(5)

Repeated Experiments

For an integer k≥0k\geq0, a repeated strategy SS for kk coordinates of the game GG is an entangled strategy with question alphabets Xk,YkX^k,Y^k and answer alphabets Ak,BkA^k,B^k.

A repeated quantum experiment MM on a finite nonempty coordinate set II consists of a question law μ\mu on X×YX\times Y, a normalized state coefficient matrix CC, string POVMs (P𝜶𝒙)(P^{\mathbf x}_{\boldsymbol\alpha}) and (Q𝜷𝒚)(Q^{\mathbf y}_{\boldsymbol\beta}), and a Boolean predicate VV on the single-coordinate questions and answers.✦ A question profile z:I→X×Yz:I\to X\times Y of a repeated quantum experiment MM is a function assigning a question pair to each coordinate; write zX,zYz_X,z_Y for its two local strings.✦ A transcript t=(z,𝜶,𝜷)t=(z,\boldsymbol\alpha,\boldsymbol\beta) of a repeated quantum experiment MM is a tuple consisting of a question profile zz and answer strings 𝜶∈AI\boldsymbol\alpha\in A^I and 𝜷∈BI\boldsymbol\beta\in B^I.✦ The conditional answer law aMa_M, the joint transcript law ρM\rho_M, and the coordinate winning predicate wiw_i are defined in (6): aM(𝜶,𝜷∣z)=qC(P𝜶zX,Q𝜷zY),ρM(z,𝜶,𝜷)=μ⊗I(z)aM(𝜶,𝜷∣z),wi(t)=V(zX(i),zY(i),αi,βi).\begin{aligned} a_M(\boldsymbol\alpha,\boldsymbol\beta\mid z) &=q_C(P^{z_X}_{\boldsymbol\alpha},Q^{z_Y}_{\boldsymbol\beta}),\\ \rho_M(z,\boldsymbol\alpha,\boldsymbol\beta) &=\mu^{\otimes I}(z)\, a_M(\boldsymbol\alpha,\boldsymbol\beta\mid z),\\ w_i(t)&=V(z_X(i),z_Y(i),\alpha_i,\beta_i). \end{aligned}(6) The repetition model MSM_S associated to a repeated strategy SS for GG takes I={1,…,k}I=\{1,\ldots,k\} and uses GG’s question law and predicate together with SS’s coefficient matrix and local string POVMs.✦

The uniform law uIu_I on II assigns weight 1/|I|1/|I| to each coordinate.✦ For a finite probability law ρ\rho on outcomes Ω\Omega and Boolean winning predicates wiw_i on Ω\Omega, the number of wins WIW_I, the winning fraction rIr_I, and the event probability Tρ,w(s)T_{\rho,w}(s) at a real threshold ss are defined by (7); here 𝟏\mathbf 1 denotes an indicator: WI(t)=∑i∈Iwi(t),rI(t)=𝔼uI[i↦wi(t)]=WI(t)|I|,Tρ,w(s)=𝔼ρ[𝟏{rI≥s}].W_I(t)=\sum_{i\in I}w_i(t),\qquad r_I(t)=\mathbb E_{u_I}[i\mapsto w_i(t)]=\frac{W_I(t)}{|I|},\qquad T_{\rho,w}(s)=\mathbb E_\rho[\mathbf 1_{\{r_I\geq s\}}].(7) For I={1,…,k}I=\{1,\ldots,k\}, write Wk=WIW_k=W_I. For a real excess δ\delta, the repeated threshold probability Pk(G,δ;S)P_k(G,\delta;S) is the probability of the event in (8) when question pairs are sampled independently from μ\mu and answers follow SS.✦ The entangled threshold value Vk(G,δ)V_k(G,\delta) of the game GG is the supremum of Pk(G,δ;S)P_k(G,\delta;S) over all finite-dimensional repeated strategies SS for kk coordinates: Pk(G,δ;S)=ℙS[Wk≥⌈(v+δ)k⌉],Vk(G,δ)=supSPk(G,δ;S).P_k(G,\delta;S) =\mathbb P_S\!\left[W_k\geq\lceil(v+\delta)k\rceil\right], \qquad V_k(G,\delta)=\sup_S P_k(G,\delta;S).(8)

The Claim

Theorem 1. There is a universal constant κ0>0\kappa_0>0, with admissible choice κ0=2−101\kappa_0=2^{-101}, such that the following holds. Let GG be a finite game as above with v<1v<1, let 0<δ<1−v0<\delta<1-v, and let k≥1k\geq1 be an integer. The bounds for every finite-dimensional repeated strategy SS and for the threshold value are (9): ℙS[Wk≥⌈(v+δ)k⌉]≤exp⁡(−κ0δ13k1+log⁡d),Vk(G,δ)≤exp⁡(−κ0δ13k1+log⁡d).\begin{aligned} \mathbb P_S\!\left[W_k\geq\lceil(v+\delta)k\rceil\right] &\leq\exp\!\left(-\frac{\kappa_0\delta^{13}k}{1+\log d}\right),\\ V_k(G,\delta) &\leq\exp\!\left(-\frac{\kappa_0\delta^{13}k}{1+\log d}\right). \end{aligned}(9)✦ For a repeated quantum experiment MM of GG on II, let k=|I|k=|I|. Under the hypotheses 0<δ0<\delta and v+δ≤1v+\delta\leq1, its real win-fraction threshold satisfies (10): TρM,w(v+δ)≤exp⁡(−δ13k2101(1+log⁡d)).T_{\rho_M,w}(v+\delta) \leq\exp\!\left(-\frac{\delta^{13}k}{2^{101}(1+\log d)}\right).(10)✦ Let SS be a repeated strategy of positive integer length kk, and let δ∈ℝ\delta\in\mathbb R. Its associated repetition model satisfies (11): Pk(G,δ;S)=TρMS,w(v+δ).P_k(G,\delta;S)=T_{\rho_{M_S},w}(v+\delta).(11)✦

In the paper, the result reads: there is a universal κp>0\kappa_{\mathrm p}>0 such that, for every finite two-player one-round game with Boolean acceptance predicate and entangled value v<1v<1, every 0<δ<1−v0<\delta<1-v, every integer k≥1k\geq1 and every finite-dimensional joint strategy SS for kk repetitions, ℙS[Wk≥⌈(v+δ)k⌉]≤exp⁡(−κpδ5k/(1+log⁡d))\mathbb P_S[W_k\geq\lceil(v+\delta)k\rceil] \leq\exp(-\kappa_{\mathrm p}\delta^5 k/(1+\log d)), with the same inequality for the supremum over those strategies; the question law may be correlated, have zero entries and have disconnected support.

What Is Checked

The claims (9), (10) and (11) are stated over finite games with nonempty alphabets and finite-dimensional normalized bipartite states, with local POVMs on complete question and answer strings and product question laws across coordinates.