OctoInformBeta

OpenAI preprint, September 2026 · Section 2. From conditioning to a threshold bound

Lemma 2.1: Arbitrary finite-dimensional strategies for parallel repetition on a nonempty finite coordinate set

The value bounds the mean win fraction.

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 full local question vector and returns an answer vector. The quantity at issue is the expected fraction of coordinates accepted by the base game’s verifier.

A two-player nonlocal game GG has finite nonempty question alphabets X,YX,Y and answer alphabets A,BA,B, a question distribution qq on X×YX\times Y, and an acceptance predicate V:X×Y×A×B→{0,1}V:X\times Y\times A\times B\to\{0,1\}.✦

A finite probability law pp on a finite set Ω\Omega is a function assigning nonnegative weights of total mass one; the expectation 𝔼p[f]\mathbb E_p[f] of a function ff on Ω\Omega with values in a real vector space is the weighted sum in (1). p(ω)≥0,∑ω∈Ωp(ω)=1,𝔼p[f]:=∑ω∈Ωp(ω)f(ω).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).(1)

A local positive operator-valued measure (POVM) EE on a finite-dimensional Hilbert space ℋ\mathcal H, with finite outcome alphabet AA, is a family of effects obeying (2). Ea≽0(a∈A),∑a∈AEa=Iℋ.E^a\succeq 0\quad(a\in A),\qquad \sum_{a\in A}E^a=I_{\mathcal H}.(2)✦

For a coefficient matrix Ψ\Psi on nonzero finite-dimensional local Hilbert spaces ℋA,ℋB\mathcal H_A,\mathcal H_B with orthonormal bases indexed by r,sr,s, the associated state vector |Ψ⟩|\Psi\rangle is the vector in their tensor product given in (3), and its squared Hilbert-Schmidt norm ∥Ψ∥HS2\|\Psi\|_{\mathrm{HS}}^2 is the sum given there. |Ψ⟩:=∑r,sΨrs|r⟩⊗|s⟩,∥Ψ∥HS2:=∑r,s|Ψrs|2.|\Psi\rangle:=\sum_{r,s}\Psi_{rs}|r\rangle\otimes|s\rangle, \qquad \|\Psi\|_{\mathrm{HS}}^2:=\sum_{r,s}|\Psi_{rs}|^2.(3) For a coefficient matrix Ψ\Psi on ℋA,ℋB\mathcal H_A,\mathcal H_B and local operators EE on ℋA\mathcal H_A and FF on ℋB\mathcal H_B, the bipartite operator expectation eΨ(E,F)e_\Psi(E,F) is the complex scalar in (4), and the Born probability bΨ(E,F)b_\Psi(E,F) is its real part. eΨ(E,F):=⟨Ψ|E⊗F|Ψ⟩,bΨ(E,F):=Re⁡eΨ(E,F).e_\Psi(E,F):=\langle\Psi|E\otimes F|\Psi\rangle, \qquad b_\Psi(E,F):=\operatorname{Re}e_\Psi(E,F).(4) For ∥Ψ∥HS2=1\|\Psi\|_{\mathrm{HS}}^2=1 and local POVMs P,QP,Q, the joint measurement distribution mΨ,P,Qm_{\Psi,P,Q} is the probability law on outcome pairs with weight mΨ,P,Q(a,b)=bΨ(Pa,Qb)m_{\Psi,P,Q}(a,b)=b_\Psi(P^a,Q^b).✦

A single-round entangled strategy SS for the game GG is a normalized state |Ψ⟩|\Psi\rangle on a pair of nonzero finite-dimensional local Hilbert spaces together with local POVMs Ex,FyE_x,F_y for each x∈X,y∈Yx\in X,y\in Y. The Born probability σS(a,b∣x,y)\sigma_S(a,b\mid x,y) of answers a,ba,b given questions x,yx,y for a single-round entangled strategy SS is the number given by σS(a,b∣x,y):=bΨ(Exa,Fyb)\sigma_S(a,b\mid x,y):=b_\Psi(E_x^a,F_y^b).✦ The winning probability sG(S)s_G(S) of a single-round entangled strategy SS for GG is its probability of acceptance, and the finite-dimensional entangled value vv of GG is the supremum of these winning probabilities over all finite-dimensional single-round entangled strategies, as given in (5). sG(S):=∑x,yq(x,y)∑a,bV(x,y,a,b)σS(a,b∣x,y),v:=supSsG(S).s_G(S):=\sum_{x,y}q(x,y) \sum_{a,b}V(x,y,a,b)\sigma_S(a,b\mid x,y), \qquad v:=\sup_S s_G(S).(5)

The Repeated Experiment

Let II be a nonempty finite coordinate set and k=|I|k=|I|. The uniform law uIu_I on II and the product law ⨂j∈Jpj\bigotimes_{j\in J}p_j of laws pjp_j on Ω\Omega indexed by a finite set JJ have the weights in (6), where f∈ΩJf\in\Omega^J. uI(i):=1k,(⨂j∈Jpj)(f):=∏j∈Jpj(fj).u_I(i):=\frac1k,\qquad \left(\bigotimes_{j\in J}p_j\right)(f):=\prod_{j\in J}p_j(f_j).(6)

A repeated quantum experiment MM for the game GG on the coordinate set II is a collection consisting of the question law qq and verifier VV, a normalized coefficient matrix Ψ\Psi, and local POVMs P𝒙P_{\mathbf x} on AIA^I and Q𝒚Q_{\mathbf y} on BIB^I for every 𝒙∈XI\mathbf x\in X^I and 𝒚∈YI\mathbf y\in Y^I.✦

A question profile z:I→X×Yz:I\to X\times Y for a repeated experiment on II is a function assigning a question pair zi=(xi,yi)z_i=(x_i,y_i) to each coordinate, with local vectors 𝒙=(xi)i∈I\mathbf x=(x_i)_{i\in I} and 𝒚=(yi)i∈I\mathbf y=(y_i)_{i\in I}.✦ A question and answer transcript t=(z,𝒂,𝒃)t=(z,\mathbf a,\mathbf b) for MM is a tuple consisting of a question profile zz and answer vectors with 𝒂∈AI,𝒃∈BI\mathbf a\in A^I,\mathbf b\in B^I.✦ The conditional answer distribution aM(⋅∣z)a_M(\cdot\mid z) of MM and its joint transcript distribution ℙM\mathbb P_M are the probability laws in (7). aM(𝒂,𝒃∣z):=mΨ,P𝒙,Q𝒚(𝒂,𝒃),ℙM(z,𝒂,𝒃):=(∏i∈Iq(xi,yi))aM(𝒂,𝒃∣z).\begin{aligned} a_M(\mathbf a,\mathbf b\mid z) &:=m_{\Psi,P_{\mathbf x},Q_{\mathbf y}}(\mathbf a,\mathbf b),\\ \mathbb P_M(z,\mathbf a,\mathbf b) &:=\left(\prod_{i\in I}q(x_i,y_i)\right) a_M(\mathbf a,\mathbf b\mid z). \end{aligned}(7)

For a coordinate i∈Ii\in I and transcript t=(z,𝒂,𝒃)t=(z,\mathbf a,\mathbf b), the coordinate winning predicate is acceptance of (xi,yi,ai,bi)(x_i,y_i,a_i,b_i) by VV; the coordinate winning indicator IiI_i is the function on transcripts given by Ii(t):=V(xi,yi,ai,bi)I_i(t):=V(x_i,y_i,a_i,b_i).✦ The winning fraction r(t)r(t) of a transcript is the uniform mean of these indicators, as in (8). r(t):=𝔼i∼uI[Ii(t)]=1k∑i∈IIi(t).r(t):=\mathbb E_{i\sim u_I}[I_i(t)] =\frac1k\sum_{i\in I}I_i(t).(8)✦ For a tested set C⊆IC\subseteq I, the event ECE_C that every tested coordinate wins, its subset winning indicator JCJ_C, and its joint winning probability pCp_C are defined by (9). EC:={t:Ii(t)=1 for every i∈C},JC(t):=𝟏EC(t),pC:=𝔼ℙM[JC].E_C:=\{t:I_i(t)=1\text{ for every }i\in C\},\qquad J_C(t):=\mathbf 1_{E_C}(t),\qquad p_C:=\mathbb E_{\mathbb P_M}[J_C].(9)

The Claim

Theorem 1. Let GG be a finite two-player game, II a nonempty finite coordinate set of size kk, and MM a repeated quantum experiment for GG on II. The mean rate obeys (10), with the singleton expression (11). 𝔼ℙM[r]≤v.\mathbb E_{\mathbb P_M}[r]\leq v.(10)✦ 𝔼ℙM[r]=𝔼i∼uI[p{i}].\mathbb E_{\mathbb P_M}[r] =\mathbb E_{i\sim u_I}[p_{\{i\}}].(11)✦

In the paper, the result reads: for any finite-dimensional strategy for the kk-fold repetition of a finite two-prover game of entangled value vv, 𝔼[Ii]≤v\mathbb E[I_i]\leq v for every 1≤i≤k1\leq i\leq k and 𝔼[∑i=1kIi]≤kv\mathbb E[\sum_{i=1}^k I_i]\leq kv; in particular, if v=0v=0, every coordinate is lost almost surely.

What Is Checked

The claims (10) and (11) concern repeated quantum experiments for GG on nonempty finite II, with expectations taken under the joint transcript law (7).