5 Parallel repetition
This chapter states the parallel repetition theorem used for gap amplification in the compression procedure (Section 6.5): direct (unanchored) parallel repetition in value form, for entangled and for commuting-operator strategies, together with Lin’s tracial density theorem. Both theorems are imported from external Lean developments vendored into this repository, and the chapter records their statements in the vocabulary of Section 2 together with the bridges connecting the two; both are formalized end to end, the entangled one through Lemma 5.7.
The anchored, entanglement-preserving theorem of Bavarian, Vidick and Yuen [ 10 ] , which [ 1 ] uses for this step, is not stated here. Anchoring is what the entanglement form forces: [ 11 ] ’s recursive compression lemma needs a measure \(f\) with \(f(\textsc{Compr}(\hat x, n)) \geq \max \{ f(x), n\} \), so every transformation has to preserve \(\mathrm{Ent}\), and only the anchored theorem does. The compressibility criterion of [ 13 ] used here (Lemma 4.11) carries no measure at all, so value decay suffices and the repeated game may be the game as it is. Remark 5.11 records the comparison, and Remark 6.207 what the entanglement clauses of [ 1 ] would buy.
5.1 Direct parallel repetition
The \(n\)-fold direct repetition of a game asks \(n\) independent question pairs at once and accepts if all \(n\) answer pairs are accepted. Two recent Lean developments prove that the value of the repeated game decays exponentially in \(n\), for every game, with no anchoring and at a rate depending only on the gap \(1 - \mathrm{val}(\mathfrak {G})\) and on the size of the answer alphabets: one for tensor-product (entangled) strategies, by OpenAI [ 31 ] , and one for commuting-operator strategies [ 32 ] , the latter building on the former and on Lin’s tracial density theorem [ 12 ] . Both are vendored into this repository (MIPRE/Background/Repetition/, with provenance recorded in the README.md of each directory) and connected to the definitions of Section 2 by explicit bridges; the statements below are the bridged forms. The commuting-operator theorem is recorded now, although only the entangled one enters \(\mathrm{MIP}^*= \mathrm{RE}\), because it is the form needed for the commuting-operator counterpart \(\mathrm{MIP}^{\mathrm{co}}= \mathrm{coRE}\) [ 13 ] (Remark 8.145).
Let \(\mathfrak {G}= (\mathcal{X}, \mathcal{Y}, \mathcal{A}, \mathcal{B}, \mu , D)\) be a game and \(n \geq 0\) an integer. The \(n\)-fold direct repetition of \(\mathfrak {G}\) is the game \(\mathfrak {G}^{n}\) with question alphabets \(\mathcal{X}^n\), \(\mathcal{Y}^n\) and answer alphabets \(\mathcal{A}^n\), \(\mathcal{B}^n\), question distribution \(\mu ^{n}(\bar{x}, \bar{y}) = \prod _{i=1}^{n} \mu (x_i, y_i)\), and decision predicate \(D^{n}(\bar{x}, \bar{y}, \bar{a}, \bar{b}) = \bigwedge _{i=1}^{n} D(x_i, y_i, a_i, b_i)\). The direct repetition of a synchronous game is synchronous, with the same data.
The entangled theorem is stated for the quantum value of Definition 2.9, whose strategies are bipartite. The commuting-operator theorem needs the bipartite counterpart of the commuting value, which Section 2 defines in synchronous (tracial) form only (Definition 2.11); the two are related by Lemma 5.4.
[\(\uparrow \) QuantumLib] A commuting-operator strategy for \(\mathfrak {G}\) consists of a Hilbert space \(\mathcal{H}\) (a complete inner product space over \(\mathbb {C}\), of any dimension), a unit vector \(|\psi \rangle \in \mathcal{H}\), and POVMs \(\{ E^x_a\} _{a \in \mathcal{A}}\) and \(\{ F^y_b\} _{b \in \mathcal{B}}\) on \(\mathcal{H}\), one for each \(x\) (resp. \(y\)) — each \(E^x_a\) and \(F^y_b\) is a positive bounded operator, \(\sum _a E^x_a = I\) and \(\sum _b F^y_b = I\) — such that \(E^x_a F^y_b = F^y_b E^x_a\) for all \(x, y, a, b\). The players answer \((a, b)\) to questions \((x, y)\) with probability \(\langle \psi | E^x_a F^y_b |\psi \rangle \).
[\(\uparrow \) QuantumLib] The value of a commuting-operator strategy \(\mathscr {S}= (\mathcal{H}, \psi , E, F)\) in \(\mathfrak {G}\) is
and the commuting-operator value \(\omega ^{\mathrm{co}}(\mathfrak {G})\) of \(\mathfrak {G}\) is the supremum of \(\omega ^{\mathrm{co}}(\mathfrak {G}, \mathscr {S})\) over all commuting-operator strategies.
Comments.
As in Definition 2.9, the formalization takes the real part of the (real, nonnegative) probability. The Hilbert space of a strategy lives in the lowest universe, as in the vendored development; this is no restriction for the suprema, which are bounded by \(1\). The notation \(\omega ^{\mathrm{co}}\) follows [ 32 ] and keeps the bipartite value apart from the tracial value \(\mathrm{val}^{\mathrm{co}}\) of Definition 2.11.
[\(\bullet \bullet \) medium] [\(\uparrow \) QuantumLib]
[\(\uparrow \) QuantumLib] For every synchronous game \(\mathfrak {G}\), \(\mathrm{val}^{\mathrm{co}}(\mathfrak {G}) \leq \omega ^{\mathrm{co}}(\mathfrak {G})\). The Lean proof of the main theorem does not use this lemma; it serves the downstream \(\mathrm{MIP}^{\mathrm{co}}= \mathrm{coRE}\) chapter only.
Let \((\mathscr {A}, \tau , M)\) be a commuting strategy (Definition 2.5) and let \(\mathcal{H}\) be the completion of \(\mathscr {A}\) for the semi-inner product \(\langle a, b \rangle = \tau (a^* b)\), with the class of \(1\) as the unit vector \(\xi \). A tracial state is Hermitian, \(\tau (a^*) = \overline{\tau (a)}\), by polarization of its positivity at \(1 + a\) and \(1 + ia\). Left multiplication \(\pi (p) : b \mapsto pb\) and right multiplication \(\rho (p) : b \mapsto bp\) by a projection \(p\) are contractions for the semi-norm, hence extend to \(\mathcal{H}\). For \(\rho \) this uses the trace: \(\tau ((bp)^*(bp)) = \tau (b^* b p)\) and \(\tau (b^* b) - \tau (b^* b p) = \tau ((b(1-p))^*(b(1-p))) \geq 0\). Both are symmetric and positive for the form; for \(\rho \), \(\tau ((bp)^* c) = \tau (b^* c p)\) and \(\tau (b^* b p) = \tau ((bp)^*(bp))\). Left and right multiplications commute, by associativity, and each family sums to the identity. Setting \(E^x_a = \pi (M^x_a)\) and \(F^y_b = \rho (M^y_b)\) gives a commuting-operator strategy with \(\langle \xi | E^x_a F^y_b |\xi \rangle = \tau (1^* M^x_a M^y_b) = \tau (M^x_a M^y_b)\), hence with the same value as \((\mathscr {A}, \tau , M)\). Taking suprema yields the claim. No norm on \(\mathscr {A}\) is used.
Comments.
This is the direction needed to apply Theorem 5.5 to the tracial value used in the pipeline: a bound on \(\omega ^{\mathrm{co}}(\mathfrak {G}^n)\) is a bound on \(\mathrm{val}^{\mathrm{co}}(\mathfrak {G}^n)\). The reverse comparison (from \(\omega ^{\mathrm{co}}\) to \(\mathrm{val}^{\mathrm{co}}\), false in general and true up to error for synchronous games that carry proportional weight on the diagonal, as in Remark 3.4) is the commuting-operator analogue of Theorem 3.3, proved by Lin [ 12 ] ; it is part of the transport discussed in Section 1.3 and not of this section. The Lean statement of this lemma and its GNS construction are a sub-project of their own.
[\(\bullet \bullet \bullet \) hard] [\(\uparrow \) QuantumLib]
[\(\uparrow \) QuantumLib] There is a universal constant \(c {\gt} 0\) such that for every game \(\mathfrak {G}\) with nonempty alphabets and every integer \(n \geq 1\), writing \(\varepsilon = 1 - \omega ^{\mathrm{co}}(\mathfrak {G})\),
This is the main theorem of [ 32 ] (Theorem 7.1 there), whose Lean proof is vendored at MIPRE/Background/Repetition/CommutingRepetition/. The bridge identifies a game of Definition 2.1 with the game of the vendored development having the \(\{ 0, 1\} \)-valued payoff \(D\), a commuting-operator strategy of Definition 5.2 with a strategy of the vendored development (field by field, so that the two suprema defining the value range over the same set of numbers), and the two direct repetitions with each other. When \(\varepsilon = 0\) and \(\left\vert {\mathcal{A}} \right\vert = \left\vert {\mathcal{B}} \right\vert = 1\) the formalization reads the quotient as \(0\) and the bound is trivial.
[\(\uparrow \) QuantumLib] There is a universal constant \(c {\gt} 0\) such that for every game \(\mathfrak {G}\) with nonempty answer alphabets and \(\mathrm{val}^*(\mathfrak {G}) {\lt} 1\), and every integer \(n \geq 1\), writing \(\varepsilon = 1 - \mathrm{val}^*(\mathfrak {G})\),
This is the main theorem of Chapter 6 of [ 31 ] , whose Lean proof is vendored at MIPRE/Background/Repetition/TenProofs/. Its entangled value is defined with a density matrix on the product of two finite sets and POVMs; Lemma 5.7 identifies it with \(\mathrm{val}^*\) (Definition 2.9), after which the two direct repetitions are literally the same construction.
[\(\bullet \bullet \) medium] [\(\uparrow \) QuantumLib]
[\(\uparrow \) QuantumLib] Let \(\mathrm{val}^*_{\mathrm{POVM}}(\mathfrak {G})\) be the supremum of the winning probabilities \(\sum _{x,y,a,b} \mu (x,y)\, D(x,y,a,b)\, \operatorname{tr}\bigl( (A^x_a \otimes B^y_b)\, \rho \bigr)\) over all finite sets \(S_\textsc{A}\), \(S_\textsc{B}\), density matrices \(\rho \) on \(\mathbb {C}^{S_\textsc{A}} \otimes \mathbb {C}^{S_\textsc{B}}\) and POVMs \(\{ A^x_a\} \) on \(\mathbb {C}^{S_\textsc{A}}\), \(\{ B^y_b\} \) on \(\mathbb {C}^{S_\textsc{B}}\). Then \(\mathrm{val}^*_{\mathrm{POVM}}(\mathfrak {G}) = \mathrm{val}^*(\mathfrak {G})\).
A tensor-product strategy (Definition 2.3) is a strategy of the second kind, with \(S_\textsc{A}= \{ 1, \ldots , d_\textsc{A}\} \), \(S_\textsc{B}= \{ 1, \ldots , d_\textsc{B}\} \), \(\rho = |\psi \rangle \langle \psi |\) and projective measurements, which gives \(\mathrm{val}^*\leq \mathrm{val}^*_{\mathrm{POVM}}\).
Conversely, given a strategy of the second kind, purify \(\rho \) on a reference system placed on Bob’s side, where Bob’s effects act as \(B^y_b \otimes I\), so that the bipartite structure survives; then dilate the two POVM families to projective measurements on one extra register each, and reindex the two finite sets by initial segments of \(\mathbb {N}\). Neither step changes an outcome probability, so the result is a tensor-product strategy of the same value.
The dilation is the only delicate point, and the reason is that the shared state may not depend on the questions while the dilating isometry does. Writing \(A^x_a = (K^x_a)^\dagger K^x_a\), the isometry \(V_x : v \mapsto \sum _a (K^x_a v) \otimes |a\rangle \) satisfies \(V_x^\dagger (I\otimes |a\rangle \langle a|) V_x = A^x_a\); extending each \(V_x\) to a unitary \(U_x\) of \(\mathbb {C}^{S_\textsc{A}} \otimes \mathbb {C}^{\mathcal{A}}\) and setting \(P^x_a := U_x^\dagger (I\otimes |a\rangle \langle a|) U_x\) gives projective measurements all of which are compressed back to the POVMs by the same, question-independent isometry \(v \mapsto v \otimes |a_0\rangle \), so that the single state \(|\psi \rangle \otimes |a_0\rangle \otimes |b_0\rangle \) works for every question. In Lean the extension is Mathlib’s completion of an orthonormal family to an orthonormal basis, and only the factorization \(A^x_a = (K^x_a)^\dagger K^x_a\) is used, not a matrix square root, which Mathlib does not have. The nonemptiness of \(\mathcal{A}\) and \(\mathcal{B}\) needed to choose \(a_0\) and \(b_0\) is derived, not assumed: \(\mu \) is a probability distribution, so some question is asked, and a POVM on a space carrying a state has a nonempty outcome set.
Comments.
The lemma is a general fact of independent interest, and the substantive part of the entangled bridge; Naimark dilation is not in Mathlib. The vendored definition of the entangled value has the strategy’s two finite sets as arbitrary types in the lowest universe, and the bridge reindexes them.
[\(\bullet \bullet \bullet \) hard] [\(\uparrow \) QuantumLib]
Let \(\mathfrak {G}\) be a synchronous game and \(\mathscr {S}= (d, M)\) a synchronous strategy for it. The \(k\)-fold tensor power \(\mathscr {S}^{\otimes k} = (d^k, M^{\otimes k})\), with \(M^{\bar{x}}_{\bar{a}} = \bigotimes _{i=1}^{k} M^{x_i}_{a_i}\), is a synchronous strategy for the direct repetition \(\mathfrak {G}^{k}\) whose value is the \(k\)-th power of the value of \(\mathscr {S}\), and it is PCC if \(\mathscr {S}\) is. In particular a value-\(1\) PCC strategy for the doubled game of a game \(\mathfrak {G}\) gives one for the doubled game of \(\mathfrak {G}^{k}\), for every \(k\), the tag being read on every coordinate.
The normalized trace on \(\mathbb {C}^{d^k}\) of a tensor product is the product of the normalized traces on \(\mathbb {C}^d\) (the trace of a product of two projections being real), and the distribution and predicate of \(\mathfrak {G}^{k}\) are products, so each summand of the value of \(\mathscr {S}^{\otimes k}\) is the product over the coordinates of the corresponding summands of the value of \(\mathscr {S}\), and the sum over \(k\)-tuples of questions and answers is the \(k\)-th power of the sum. Commutation is coordinatewise, on the support of the product distribution, which is the product of the supports. For the doubled reading, the strategy on the doubled repetition is the tensor power relabeled along \((t, \bar{x}) \mapsto ((t, x_i))_i\), which is injective and covers the support of the doubled repeated distribution.
There is a universal constant \(c' {\gt} 0\) such that for every game \(\mathfrak {G}\) whose answer alphabets are the strings of length at most \(B\), every \(\varepsilon {\gt} 0\) with \(\mathrm{val}^*(\mathfrak {G}) \leq 1 - \varepsilon \) and every \(k \geq 1\),
Theorem 5.6 at \(\varepsilon ' = 1 - \mathrm{val}^*(\mathfrak {G}) \geq \varepsilon \): there are at most \(3^{B+1}\) strings of length at most \(B\), so \(\log (\left\vert {\mathcal{A}} \right\vert \left\vert {\mathcal{B}} \right\vert ) \leq 2(B + 1) \log 3\), and \(\varepsilon ' \leq 1 \leq B + 1\), so the denominator is at most \((B + 1)(1 + 2 \log 3)\); the exponent is monotone in the gap, so the bound at \(\varepsilon '\) implies the one at \(\varepsilon \). Take \(c' = c / (1 + 2 \log 3)\). This is the form in which the soundness clause of Theorem 6.196 consumes the theorem.
[\(\uparrow \) QuantumLib] Let \(\mathcal{X}\) and \(\mathcal{A}\) be finite nonempty sets. Call a correlation \(q(a, b \mid x, y)\) on question alphabets \(\mathcal{X}, \mathcal{X}\) and answer alphabets \(\mathcal{A}, \mathcal{A}\) tracially embeddable if there are: a unital \(*\)-algebra \(\mathscr {A}\) over \(\mathbb {C}\) with a tracial state \(\tau \) (\(\tau (1) = 1\), \(\tau (ab) = \tau (ba)\), \(\tau (a^*) = \overline{\tau (a)}\)); a Hilbert space \(\mathcal{H}\) with a linear map \(\iota : \mathscr {A}\to \mathcal{H}\) of dense range satisfying \(\langle \iota a, \iota b \rangle = \tau (a^* b)\), on which \(\mathscr {A}\) acts on the left by bounded operators \(L(a)\) with \(L(a)\, \iota b = \iota (ab)\); a positive element \(\sigma \in \mathscr {A}\) with \(\tau (\sigma ^* \sigma ) = 1\); POVMs \(\{ E^x_a\} _{a} \subseteq \mathscr {A}\) of positive elements summing to \(1\); and POVMs \(\{ G^y_b\} _{b}\) of positive bounded operators on \(\mathcal{H}\) summing to \(I\) and commuting with \(L(\mathscr {A})\), such that
Then every commuting-operator correlation \(p(a, b \mid x, y) = \langle \psi | E^x_a F^y_b |\psi \rangle \) on these alphabets (Definition 5.2) is an \(\ell ^1\)-limit of tracially embeddable correlations: for every \(\delta {\gt} 0\) there is a tracially embeddable \(q\) with \(\sum _{x, y, a, b} \left\vert {p(a, b \mid x, y) - q(a, b \mid x, y)} \right\vert {\lt} \delta \).
This is Theorem 3.2 of [ 12 ] , as formalized in [ 32 ] (the density programme of the vendored development, Tracial/Density/Main.lean). The statement above is that of the vendored development, in its own vocabulary — its tracially embeddable correlations have the shape of Lin’s Definition 3.1, with Bob’s measurement taken in the commutant of the left action; restating it through the definitions of Section 2 is pending.
Source.
Direct parallel repetition for entangled strategies is Chapter 6 of OpenAI’s Ten advances [ 31 ] , with the Lean proof in the accompanying repository; for commuting-operator strategies it is [ 32 ] , whose proof reduces to the tracially embeddable case by Theorem 5.10 and then rounds by adapting the argument of [ 31 ] . Earlier value-form theorems cover restricted classes of games or give polynomial rates; the anchored theorem of [ 10 ] is the one used in [ 1 ] . The rates \(\varepsilon ^{13}\) and \(\varepsilon ^{7}\) are those of the sources; any polynomial rate suffices for the pipeline.
Comments.
Both vendored developments are sorry-free and use only the standard axioms; the file MIPRE/Background/Repetition/Axioms.lean guards the axioms of Theorem 5.10 and of both bridged repetition theorems. Vendoring is done by scripts/vendor-repetition.py, never by hand; the copies are read-only and the only local changes are recorded in each directory’s README.md. Nothing outside MIPRE/Background/Repetition/ refers to the vendored namespaces.
Theorems 5.6 and 5.5 are statements about values, while the anchored theorem of [ 10 ] is a statement about entanglement requirements: the anchored proof extracts from a good strategy for the repeated game a strategy for the original game of no larger dimension, whereas the proofs of the direct theorems round through auxiliary resources (an embezzling state in [ 31 ] , a tracial approximation in [ 32 ] ) and give no control of the dimension. Lin’s proof of \(\mathrm{MIP}^{\mathrm{co}}= \mathrm{coRE}\) [ 13 ] shows that the entanglement clauses of [ 1 ] are dispensable: with completeness and soundness of compression stated in value form (perfect strategies are preserved, and \(\mathrm{val}^*\) at most \(\frac12\) is preserved, a \(\mathrm{val}^{s}\) hypothesis side being converted by the free comparison Lemma 2.14), the halting reduction follows from the \(\mathrm{val}^*\) half of the enumeration of Lemma 3.112 and Kleene’s recursion theorem alone (Lemma 4.11), and gap amplification then needs only a value statement — exactly the theorems of this section, applied to the game as it is, without anchoring. The pipeline of Section 6 is stated in that form (Section 1.3): Theorem 6.196 rests on Theorem 5.6, and the anchored theorem with its toolkit — the entropy inequalities, Uhlmann’s theorem, the quantum Raz lemma and Holenstein conditioning that its proof needs — is not on the path to the main theorem and is no longer stated in this blueprint; the entanglement clauses are recorded in Remark 6.207. The active pipeline carries bipartite soundness throughout (Remark 6.8); its completeness witnesses use the separately specified synchronous PCC interface.