3 Preliminaries

3.1 Polynomials and measurements

For complex numbers $\alpha ,\beta \in \mathbb {C}$, write $\alpha \approx _\varepsilon \beta $ when $|\alpha -\beta |\le \varepsilon $. In particular,

\begin{equation} \label{eq:triangle-inequality-for-numbers} \text{if $\alpha \approx _{\varepsilon } \beta $ and $\beta \approx _{\delta } \gamma $, then $\alpha \approx _{\varepsilon +\delta }\gamma $.} \end{equation}

Fix a prime power $q=p^t$. Write $\omega =e^{2\pi i/p}$, and let $\operatorname {tr}:\mathbb {F}_q\to \mathbb {F}_p$ denote the finite-field trace.

Definition 3.1 Finite field trace

✓

The finite-field trace is the map $\operatorname {tr}:\mathbb {F}_q\to \mathbb {F}_p$ defined by

\[ \operatorname {tr}[x] = \sum _{\ell =0}^{t-1} x^{p^\ell }. \]

Lemma 3.2

✓

Let $a \in \mathbb {F}_q$. Then

\begin{equation*} \mathbb {E}_{{\boldsymbol {x}}\sim \mathbb {F}_q} \omega ^{\operatorname {tr}[{\boldsymbol {x}}\cdot a]} = \left\{ \begin{array}{rl} 1 & \text{if $a = 0$}, \\ 0 & \text{otherwise}. \end{array}\right. \end{equation*}

Proof ▶

If $a=0$, then $\operatorname {tr}[{\boldsymbol {x}}\cdot a]=0$ for every ${\boldsymbol {x}}$, so the average is $1$. If $a\neq 0$, choose $y \in \mathbb {F}_q$ such that $\operatorname {tr}[a\cdot y]\neq 0$, and set

\[ C=\mathbb {E}_{{\boldsymbol {x}}\sim \mathbb {F}_q} \omega ^{\operatorname {tr}[{\boldsymbol {x}}\cdot a]}. \]

Translation invariance of the uniform distribution gives

\[ C=\mathbb {E}_{{\boldsymbol {x}}\sim \mathbb {F}_q} \omega ^{\operatorname {tr}[({\boldsymbol {x}}+y)\cdot a]} = C \cdot \omega ^{\operatorname {tr}[y\cdot a]}. \]

Since $\omega ^{\operatorname {tr}[y\cdot a]}\neq 1$, it follows that $C=0$.

Lemma 3.3

✓

Let $v \in \mathbb {F}_q^m$. Then

\begin{equation*} \mathbb {E}_{\boldsymbol {u}\sim \mathbb {F}_q^m} \omega ^{\operatorname {tr}[\boldsymbol {u}\cdot v]} = \left\{ \begin{array}{rl} 1 & \text{if $v = 0$}, \\ 0 & \text{otherwise}. \end{array}\right. \end{equation*}

Proof ▶

By linearity of the trace and independence of the coordinates,

\[ \mathbb {E}_{\boldsymbol {u}\sim \mathbb {F}_q^m} \omega ^{\operatorname {tr}[\boldsymbol {u}\cdot v]} = \prod _{i=1}^m \mathbb {E}_{\boldsymbol {u}_i \sim \mathbb {F}_q} \omega ^{\operatorname {tr}[\boldsymbol {u}_i \cdot v_i]}. \]

Proposition 3.2 shows that the $i$-th factor is $1$ when $v_i=0$ and $0$ otherwise, so the product is $1$ exactly when $v=0$.

Definition 3.4 Low individual degree polynomials

✓

Let $\mathcal{P}(m,q,d)$ be the set of polynomials $g \in \mathbb {F}_q[x_1,\dots ,x_m]$ whose degree in each variable is at most $d$, viewed as functions $\mathbb {F}_q^m \to \mathbb {F}_q$ via evaluation. (Over finite fields, distinct low-degree polynomials can induce the same function; we identify elements of $\mathcal{P}(m,q,d)$ with their polynomial representatives, not their functional equivalence classes.)

Remark 3.5 Individual-degree convention

Here, “individual degree $d$” means degree at most $d$ in each coordinate. In particular,

\[ \mathcal{P}(m,q,d) \subseteq \mathcal{P}(m,q,d+1). \]

Lemma 3.6 Schwartz–Zippel lemma [ Sch80 , Zip79 ]

✓

Let $g, h:\mathbb {F}_q^m \rightarrow \mathbb {F}_q$ be two distinct polynomials of total degree $d$. Then

\begin{equation*} \mathbb {P}_{{\boldsymbol {x}}\sim \mathbb {F}_q^m}[g({\boldsymbol {x}}) = h({\boldsymbol {x}})] \leq \frac{d}{q}. \end{equation*}

Proof ▶

Apply the Schwartz–Zippel lemma to the nonzero polynomial $g-h$, which has total degree at most $d$.

Lemma 3.7 Schwartz–Zippel for individual degree

✓

If $g,h \in \mathcal{P}(m,q,d)$ are distinct, then

\[ \mathbb {P}_{u \sim \mathbb {F}_q^m}[g(u)=h(u)] \le \frac{md}{q}. \]

Proof ▶

The difference $g-h$ is a nonzero polynomial of total degree at most $md$. Apply Lemma 3.6.

Lemma 3.8 Polynomial agreement bound on coded points

✓

Let $g, g' : \mathrm{Polynomial}\, \mathrm{params}$ be two distinct full polynomial outcomes with individual degrees at most $d$. Then

\[ \mathbb {E}_{u \sim \mathrm{Point}\, \mathrm{params}}\bigl[\mathbf{1}[g(u) = g'(u)]\bigr] \le \frac{md}{q}. \]

This packages the $md/q$ loss term used in the mainFormal self-consistency cascade (inductive_step.tex, lines 119–133) and in comMain (commutativity-G.tex).

Proof ▶

Transport along the equivalence between coded $\mathbb {F}_q$ points and the underlying scalar function space, then apply Lemma 3.7.

Lemma 3.9 Axis-line polynomial agreement bound

✓

Let $f,h : \mathrm{AxisLinePolynomial}\, \mathrm{params}$ be two line-polynomial outcomes with distinct underlying polynomials. Then

\[ \mathbb {E}_{t \sim \mathbb {F}_q}\bigl[\mathbf{1}[f(t)=h(t)]\bigr] \le \frac{md}{q}. \]

The native univariate root-counting bound is $d/q$; the statement deliberately pads this to the paper’s ambient $md/q$ loss for Lemma 6.1.

Proof ▶

Reindex coded line parameters to the scalar field, count the roots of the nonzero univariate polynomial $f-h$, and use $m\ge 1$ to pad $d/q$ to $md/q$.

Definition 3.10 Measurements and submeasurements

✓

Let $\mathcal H$ be a Hilbert space and let $\mathcal A$ be a set of outcomes. A submeasurement on $\mathcal A$ is a family $A=\{ A_a\} _{a \in \mathcal A}$ of Hermitian positive semidefinite operators on $\mathcal H$ such that $\sum _a A_a \le I$. It is a measurement when $\sum _a A_a = I$, and it is projective when each $A_a$ is an idempotent projection. (In the Lean formalization, outcome sets are assumed finite throughout.)

Definition 3.11 Low-degree polynomial measurements

✓

We write $\mathrm{PolySub}(m,q,d)$ for the submeasurements indexed by $\mathcal{P}(m,q,d)$, and $\mathrm{PolyMeas}(m,q,d)$ for the corresponding measurements.

Definition 3.12 Post-processing

✓

Let $A=\{ A_a\} _{a \in \mathcal A}$ be a family of operators and let $f\colon \mathcal A \to \mathcal B$. The post-processed family $A_{[f(a)=b]}$ is defined by

\[ A_{[f(a)=b]} = \sum _{a\, :\, f(a)=b} A_a. \]

Proposition 3.13 Post-processing preserves measurements

✓

Let $A=\{ A_a\} _{a \in \mathcal A}$ be a family of operators and let $f\colon \mathcal A \to \mathcal B$. Then

\[ \sum _a A_a = \sum _b A_{[f(a)=b]}. \]

Consequently, if $\{ A_a\} $ is a submeasurement, respectively a measurement, then $\{ A_{[f(a)=b]}\} $ is again a submeasurement, respectively a measurement.

Proof ▶

Each $a \in \mathcal A$ contributes exactly once to the right-hand side, namely in the summand indexed by $b=f(a)$.

Remark 3.14 Post-processing notation

In the notation $A_{[f(a)=b]}$, the measurement outcome is the variable to which the function is applied. For example, if $G=\{ G_g\} \in \mathrm{PolySub}(m,q,d)$ and $u \in \mathbb {F}_q^m$, then

\[ G_{[g(u)=a]} = \sum _{g\, :\, g(u)=a} G_g. \]

Here $g$ is the measurement outcome, and $u$ is the evaluation point.

Definition 3.15 Completion of a submeasurement

✓

Let $A=\{ A_a^x\} _{a \in \mathcal A}$ be a submeasurement. Its completion is the measurement $\widehat A$ with outcome set $\widehat{\mathcal A}=\mathcal A \cup \{ \bot \} $ given by $\widehat A_a^x=A_a^x$ for $a \in \mathcal A$ and $\widehat A_\bot ^x = I-\sum _a A_a^x$.

3.2 Consistency and state-dependent distance

Definition 3.16 Consistency

✓

Let $\lvert \psi \rangle \in \mathcal H_{\mathrm A} \otimes \mathcal H_{\mathrm B}$. Let $A=\{ A_a^x\} $ and $B=\{ B_a^x\} $ be submeasurements with the same answer set, and let $\mathcal D$ be a distribution on the question set. We write

\[ A_a^x \otimes I \simeq _\delta I \otimes B_a^x \]

when

\begin{equation} \label{eq:no-big-Oh} \mathbb {E}_{x \sim \mathcal D} \sum _{a \ne b} \langle \psi \rvert A_a^x \otimes B_b^x \lvert \psi \rangle \le \delta . \end{equation}

Lemma 3.17 Characterization of a good symmetric strategy

✓

A symmetric projective strategy $(\psi ,A,B,L)$ is $(\varepsilon ,\delta ,\gamma )$-good if and only if the following hold on the relevant test distributions:

\[ A_a^u \otimes I \simeq _\varepsilon I \otimes B^{\ell }_{[f(u)=a]}, \qquad A_a^u \otimes I \simeq _\delta I \otimes A_a^u, \qquad A_a^u \otimes I \simeq _\gamma I \otimes L^{\ell }_{[f(u)=a]}. \]

Proof ▶

Each subtest accepts exactly when the two measurement outcomes agree. Because the relevant families are measurements, Lemma 3.18 rewrites those acceptance probabilities as consistency bounds.

Lemma 3.18 Consistency for measurements

✓

If $A=\{ A_a^x\} $ and $B=\{ B_a^x\} $ are measurements, then

\[ A_a^x \otimes I \simeq _\delta I \otimes B_a^x \qquad \text{if and only if}\qquad \mathbb {E}_x \sum _a \langle \psi \rvert A_a^x \otimes B_a^x \lvert \psi \rangle \ge 1-\delta . \]

Proof ▶

Expand the off-diagonal sum by writing $\sum _{a \ne b} A_a^x \otimes B_b^x = \sum _b (I-A_b^x) \otimes B_b^x$.

Definition 3.19 State-dependent distance

✓

Let $\lvert \psi \rangle \in \mathcal H$, let $A=\{ A_a^x\} $ and $B=\{ B_a^x\} $ be families of operators on $\mathcal H$, and let $\mathcal D$ be a distribution on the question set. We write

\[ A_a^x \approx _\delta B_a^x \]

when

\[ \mathbb {E}_{x \sim \mathcal D} \sum _a \lVert (A_a^x-B_a^x)\lvert \psi \rangle \rVert ^2 \le \delta . \]

In particular, if $A^x_a \otimes I \simeq _{\varepsilon } I \otimes C^x_a$, the question is what hypothesis on $A$ and $B$ allows one to conclude that

\begin{equation} \label{eq:can-we-use-approx-delta-to-derive-this} B^x_a \otimes I \simeq _{\varepsilon } I \otimes C^x_a. \end{equation}

Lemma 3.20 Transferring consistency through state-dependent distance

✓

Let $A=\{ A_a^x\} $ and $B=\{ B_a^x\} $ be measurements and let $C=\{ C_a^x\} $ be a submeasurement. If $A_a^x \otimes I \simeq _\delta I \otimes C_a^x$ and $A_a^x \otimes I \approx _\varepsilon B_a^x \otimes I$, then

\[ B_a^x \otimes I \simeq _{\delta +\sqrt\varepsilon } I \otimes C_a^x. \]

Proof ▶

Rewrite the inconsistency with $C$ as total mass minus diagonal overlap. The total mass is unchanged because $A$ and $B$ are measurements, and the diagonal overlap changes by at most $\sqrt\varepsilon $ by Cauchy–Schwarz.

Lemma 3.21 Consistency implies state-dependent distance for measurements

✓

If $A$ and $B$ are measurements and $A_a^x \otimes I \simeq _\delta I \otimes B_a^x$, then

\[ A_a^x \otimes I \approx _{2\delta } I \otimes B_a^x. \]

If both measurements are projective, the converse also holds: if $A_a^x \otimes I \approx _{2\delta } I \otimes B_a^x$ then $A_a^x \otimes I \simeq _\delta I \otimes B_a^x$.

Proof ▶

Expand the squared norm of $(A_a^x \otimes I - I \otimes B_a^x)\lvert \psi \rangle $ and use the diagonal-overlap formula from Lemma 3.18; projectivity turns the diagonal inequality into an equality, giving the converse.

Remark 3.22

The implication above does not extend to submeasurements. For example, if $A_a^x=0$ for all $a$, then $A_a^x \otimes I \simeq _0 I \otimes B_a^x$, but

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _a \lVert (A^{{\boldsymbol {x}}}_a \otimes I - I \otimes B^{{\boldsymbol {x}}}_a)\lvert \psi \rangle \rVert ^2 = \mathbb {E}_{{\boldsymbol {x}}} \sum _a \lVert (I \otimes B^{{\boldsymbol {x}}}_a)\lvert \psi \rangle \rVert ^2, \]

which is nonzero unless $(I \otimes B_a^x)\lvert \psi \rangle =0$ for all $x$ and $a$.

3.3 Consistency from state-dependent distance

Theorem 3.23 Closeness of inner products

✓

Let $\{ A^x_a\} $, $\{ B^x_a\} $, and $\{ C^x_{a,b}\} $ be matrices. Suppose that $A^x_a \approx _\gamma B^x_a$ and that for all $x$,

\[ \sum _a \Big(\sum _b C^x_{a,b}\Big) \Big(\sum _b C^x_{a,b}\Big)^\dagger \le I. \]

Then

\begin{equation} \mathbb {E}_{{\boldsymbol {x}}} \sum _{a,b} \langle \psi \rvert C^{{\boldsymbol {x}}}_{a,b} A^{{\boldsymbol {x}}}_a \lvert \psi \rangle \approx _{\sqrt{\gamma }} \mathbb {E}_{{\boldsymbol {x}}} \sum _{a,b} \langle \psi \rvert C^{{\boldsymbol {x}}}_{a,b} B^{{\boldsymbol {x}}}_a \lvert \psi \rangle . \label{eq:closeness3} \end{equation}

Similarly, suppose that $(A^x_a)^\dagger \approx _\gamma (B^x_a)^\dagger $ and that for all $x$,

\[ \sum _a \Big(\sum _b C^x_{a,b}\Big)^\dagger \Big(\sum _b C^x_{a,b}\Big) \le I. \]

Then

\begin{equation} \mathbb {E}_{{\boldsymbol {x}}} \sum _{a,b} \langle \psi \rvert A^{{\boldsymbol {x}}}_a C^{{\boldsymbol {x}}}_{a,b} \lvert \psi \rangle \approx _{\sqrt{\gamma }} \mathbb {E}_{{\boldsymbol {x}}} \sum _{a,b} \langle \psi \rvert B^{{\boldsymbol {x}}}_a C^{{\boldsymbol {x}}}_{a,b} \lvert \psi \rangle . \label{eq:closeness4} \end{equation}

Proof ▶

To prove 4, write the difference as

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert \Big(\sum _b C^{\boldsymbol {x}}_{a,b}\Big) (A^{\boldsymbol {x}}_a-B^{\boldsymbol {x}}_a) \lvert \psi \rangle . \]

Cauchy–Schwarz bounds its magnitude by

\[ \Big( \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert \Big(\sum _b C^{{\boldsymbol {x}}}_{a,b}\Big)\Big(\sum _b C^{{\boldsymbol {x}}}_{a,b}\Big)^\dagger \lvert \psi \rangle \Big)^{1/2} \Big( \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a)^\dagger (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a) \lvert \psi \rangle \Big)^{1/2}, \]

and the two hypotheses bound these factors by $1$ and $\sqrt{\gamma }$ respectively. For 5, rewrite the difference as

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _{a,b} \langle \psi \rvert (C^{{\boldsymbol {x}}}_{a,b})^\dagger \big((A^{{\boldsymbol {x}}}_a)^\dagger -(B^{{\boldsymbol {x}}}_a)^\dagger \big) \lvert \psi \rangle , \]

and apply 4 to the adjoint families.

Theorem 3.24

✓

Let $A = \{ A^x_a\} $, $B = \{ B^x_a\} $, and $C = \{ C^x_a\} $ be submeasurements such that $A^x_a \approx _{\delta } B^x_a$. Then

\begin{equation*} \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{{\boldsymbol {x}}}_a C^{{\boldsymbol {x}}}_a \lvert \psi \rangle \approx _{\sqrt{\delta }} \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert B^{{\boldsymbol {x}}}_a C^{{\boldsymbol {x}}}_a \lvert \psi \rangle . \end{equation*}

Proof ▶

The difference has magnitude

\[ \Big| \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a) C^{{\boldsymbol {x}}}_a \lvert \psi \rangle \Big|. \]

By Cauchy–Schwarz this is at most

\[ \Big(\mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a)^2 \lvert \psi \rangle \Big)^{1/2} \Big(\mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (C^{{\boldsymbol {x}}}_a)^2 \lvert \psi \rangle \Big)^{1/2}. \]

The first factor is at most $\sqrt{\delta }$ by hypothesis, and the second is at most $1$ because $C$ is a submeasurement.

Theorem 3.25

✓

Let $\{ A^x_a\} $, $\{ B^x_a\} $, and $\{ C^x_{a,b}\} $ be matrices. Suppose that $A^{x}_a \approx _\delta B^{x}_a$ and that for all $x$ and $a$,

\[ \sum _b (C^{x}_{a,b})^\dagger (C^{x}_{a,b}) \leq I. \]

Then

\[ C^{x}_{a,b} A^x_{a} \approx _{\delta } C^{x}_{a,b} B^{x}_a. \]

Proof ▶

The error term is

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _{a,b} \langle \psi \rvert (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a)^\dagger (C^{{\boldsymbol {x}}}_{a,b})^\dagger C^{{\boldsymbol {x}}}_{a,b} (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a) \lvert \psi \rangle . \]

Using $\sum _b (C^{x}_{a,b})^\dagger (C^{x}_{a,b}) \le I$, this is bounded by

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a)^\dagger (A^{{\boldsymbol {x}}}_a - B^{{\boldsymbol {x}}}_a) \lvert \psi \rangle \le \delta . \]

Lemma 3.26 Triangle inequality for vectors squared

✓

For vectors $\lvert \psi _1 \rangle ,\dots ,\lvert \psi _k \rangle $,

\[ \bigl\lVert \lvert \psi _1 \rangle +\cdots +\lvert \psi _k \rangle \bigr\rVert ^2 \le k(\lVert \lvert \psi _1 \rangle \rVert ^2+\cdots +\lVert \lvert \psi _k \rangle \rVert ^2). \]

Proof ▶

First,

\begin{equation} \label{eq:prop-for-real-numbers} (x_1+\cdots +x_k)^2 \le k(x_1^2+\cdots +x_k^2) \end{equation}

for all real numbers $x_1,\dots ,x_k$. Apply 6 to $x_i=\lVert \lvert \psi _i \rangle \rVert $ and combine it with the triangle inequality.

Lemma 3.27 Triangle inequality for $\approx _\delta $

✓

Suppose $(A_i)_a^x \approx _{\delta _i} (A_{i+1})_a^x$ for $i=1,\dots ,k$. Then

\[ (A_1)_a^x \approx _{k(\delta _1+\cdots +\delta _k)} (A_{k+1})_a^x. \]

Proof ▶

Expand $(A_1-A_{k+1})\lvert \psi \rangle $ as a telescoping sum and apply Lemma 3.26.

Remark 3.28 Lean finite-step triangle helpers

The general operator-family theorem above is complemented in Lean by reusable binary and three-step helper lemmas for operator expectations, ‘qSDD‘, and ‘SDDRel‘. The three-step ‘SDDRel‘ helper is the specialization used in the Step 6 projectivization chain in Theorem 2.14; this remark is only a cross-reference and makes no separate proof-level completeness claim.

Lemma 3.29 Triangle inequality for $\simeq _\delta $

✓

Suppose $A_a^x \otimes I \simeq _\varepsilon I \otimes B_a^x$, $C_a^x \otimes I \simeq _\delta I \otimes B_a^x$, and $C_a^x \otimes I \simeq _\gamma I \otimes D_a^x$, where all four families are measurements. Then

\[ A_a^x \otimes I \simeq _{\varepsilon + 2\sqrt{\delta +\gamma }} I \otimes D_a^x. \]

Proof ▶

Convert the two consistencies involving $C$ to state-dependent distance, compose them by the triangle inequality, and transfer the result back to consistency by Lemma 3.20.

Lemma 3.30 Data processing for consistency

✓

If $A=\{ A_a^x\} $ and $B=\{ B_a^x\} $ are measurements such that $A_a^x \otimes I \simeq _\delta I \otimes B_a^x$, and $f$ is a map on the answer set, then

\[ A_{[f(a)=b]}^x \otimes I \simeq _\delta I \otimes B_{[f(a)=b]}^x. \]

Proof ▶

Merging outcome classes can only decrease the off-diagonal mass.

Lemma 3.31 Consistency controls a submeasurement

✓

Let $A=\{ A_a^x\} $ be a submeasurement and $B=\{ B_a^x\} $ a measurement such that $A_a^x \otimes I \simeq _\gamma I \otimes B_a^x$. Then

\begin{equation} A_a^x \otimes I \approx _\gamma A_a^x \otimes B_a^x \approx _\gamma A^x \otimes B_a^x, \label{eq:closeness5} \end{equation}

where $A^x=\sum _a A_a^x$. In particular,

\[ A_a^x \otimes I \approx _{4\gamma } A^x \otimes B_a^x. \]

Proof ▶

For the first approximation in 7, bound

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert \bigl(A^{{\boldsymbol {x}}}_a \otimes (I-B^{{\boldsymbol {x}}}_a)\bigr)^2 \lvert \psi \rangle \]

by the inconsistency between $A$ and $B$. The second approximation is identical, applied to

\[ \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert \bigl((A^{\boldsymbol {x}}-A^{\boldsymbol {x}}_a)\otimes B^{\boldsymbol {x}}_a\bigr)^2 \lvert \psi \rangle . \]

Then compose the two bounds with Lemma 3.27.

Lemma 3.32 Switch-sandwich

✓

Suppose $A=\{ A_a^x\} $ is a projective submeasurement satisfying

\begin{equation} A_a^x \otimes I \approx _\delta I \otimes A_a^x. \label{eq:Aapproxd} \end{equation}

Then for every operator $B$ with $0 \le B \le I$,

\begin{equation} \mathbb {E}_x \sum _a \langle \psi \rvert A_a^x B A_a^x \otimes I \lvert \psi \rangle \approx _{2\sqrt\delta } \mathbb {E}_x \sum _a \langle \psi \rvert B \otimes A_a^x \lvert \psi \rangle \approx _{\sqrt\delta } \mathbb {E}_x \sum _a \langle \psi \rvert BA_a^x \otimes I \lvert \psi \rangle . \label{eq:switch-sandwich} \end{equation}

Proof ▶

We prove the first approximation in 9 in two steps. First,

\begin{equation} \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{{\boldsymbol {x}}}_a B A^{{\boldsymbol {x}}}_a \otimes I \lvert \psi \rangle \approx _{\sqrt{\delta }} \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{{\boldsymbol {x}}}_a B \otimes A^{{\boldsymbol {x}}}_a \lvert \psi \rangle . \label{eq:shift-right-A} \end{equation}

This is obtained by applying Cauchy–Schwarz to the difference and using $B^2 \le B \le I$ together with 8. For the second step, move the remaining left copy of $A^{\boldsymbol {x}}_a$ across the bipartition in the same way; projectivity then collapses the sandwich and yields the first approximation in 9. The second approximation in 9 is the same argument with the rightmost factor $A_a^{\boldsymbol {x}}$ omitted.

3.4 Strong self-consistency

Lemma 3.33 Completeness transfer to a projective approximation

✓

Let $A=\{ A_a^x\} $ be a submeasurement and $P=\{ P_a^x\} $ a projective submeasurement such that $A_a^x \otimes I \approx _\varepsilon P_a^x \otimes I$. Then

\[ \langle \psi \rvert A \otimes I \lvert \psi \rangle \ge \langle \psi \rvert P \otimes I \lvert \psi \rangle - 2\sqrt\varepsilon . \]

Proof ▶

Since $P$ is projective,

\[ \langle \psi \rvert P \otimes I \lvert \psi \rangle = \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (P^{{\boldsymbol {x}}}_a)^2 \otimes I \lvert \psi \rangle . \]

Apply Proposition 3.24 twice to replace $(P^{\boldsymbol {x}}_a)^2$ first by $A^{\boldsymbol {x}}_aP^{\boldsymbol {x}}_a$ and then by $(A^{\boldsymbol {x}}_a)^2$, and conclude with $(A_a^{\boldsymbol {x}})^2 \le A_a^{\boldsymbol {x}}$.

Definition 3.34 Strong self-consistency

✓

Let $\lvert \psi \rangle $ be permutation-invariant and let $A=\{ A_a^x\} $ be a submeasurement. We say that $A$ is $\delta $-strongly self-consistent when

\[ \mathbb {E}_x \sum _a \langle \psi \rvert A_a^x \otimes A_a^x \lvert \psi \rangle \ge \langle \psi \rvert A \otimes I \lvert \psi \rangle - \delta . \]

Lemma 3.35 Strong self-consistency implies ordinary self-consistency

✓

If $A$ is $\delta $-strongly self-consistent, then $A_a^x \otimes I \simeq _\delta I \otimes A_a^x$. If $A$ is a measurement, the converse also holds.

Proof ▶

Rewrite the off-diagonal mass as the difference between the total mass of $A$ and the diagonal overlap in the strong self-consistency inequality. When $A$ is a full measurement, the total mass is the identity, so this inequality becomes an equality; hence the ordinary self-consistency defect and the strong self-consistency defect coincide, giving the converse.

Lemma 3.36 Strong self-consistency and state-dependent distance

✓

If $A$ is $\delta $-strongly self-consistent, then

\[ A_a^x \otimes I \approx _{2\delta } I \otimes A_a^x. \]

If $A$ is projective, the converse also holds.

Proof ▶

Expanding the squared norm gives

\begin{align} & \mathbb {E}_{{\boldsymbol {x}}} \sum _a \lVert (A^{{\boldsymbol {x}}}_a \otimes I - I \otimes A^{{\boldsymbol {x}}}_a)\lvert \psi \rangle \rVert ^2 \nonumber \\ =~ & 2\cdot \Big( \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert (A^{{\boldsymbol {x}}}_a)^2 \otimes I \lvert \psi \rangle - \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{{\boldsymbol {x}}}_a \otimes A^{{\boldsymbol {x}}}_a \lvert \psi \rangle \Big) \nonumber \\ \leq ~ & 2\cdot \Big( \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{{\boldsymbol {x}}}_a \otimes I \lvert \psi \rangle - \mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{{\boldsymbol {x}}}_a \otimes A^{{\boldsymbol {x}}}_a \lvert \psi \rangle \Big). \label{eq:here's-where-projectivity-would-help} \end{align}

The strong self-consistency bound controls the last line by $2\delta $. If $A$ is projective, then 11 is an equality, which gives the converse.

Lemma 3.37 Post-processing preserves strong self-consistency

✓

If $A$ is $\delta $-strongly self-consistent and $f$ is a function on its answer set, then

\[ A_{[f(a)=b]}^x \otimes I \approx _{2\delta } I \otimes A_{[f(a)=b]}^x. \]

Proof ▶

The same computation as in Lemma 3.36 gives

\begin{align} & \mathbb {E}_{{\boldsymbol {x}}} \sum _b \lVert (A^{{\boldsymbol {x}}}_{[f(a)=b]} \otimes I - I \otimes A^{{\boldsymbol {x}}}_{[f(a)=b]}) \lvert \psi \rangle \rVert ^2 \nonumber \\ \leq ~ & 2\cdot \Big( \langle \psi \rvert A \otimes I \lvert \psi \rangle - \mathbb {E}_{{\boldsymbol {x}}} \sum _b \langle \psi \rvert A^{{\boldsymbol {x}}}_{[f(a)=b]} \otimes A^{{\boldsymbol {x}}}_{[f(a)=b]} \lvert \psi \rangle \Big). \label{eq:finishing-this-up} \end{align}

The post-processed diagonal term dominates $\mathbb {E}_{{\boldsymbol {x}}} \sum _a \langle \psi \rvert A^{\boldsymbol {x}}_a \otimes A^{\boldsymbol {x}}_a \lvert \psi \rangle $, so strong self-consistency bounds 12 by $2\delta $.

Lemma 3.38 Completeness transfer for a strongly self-consistent approximation

✓

Let $A$ be a $\delta $-strongly self-consistent submeasurement and let $B$ be a submeasurement such that $A_a^x \otimes I \approx _\varepsilon B_a^x \otimes I$. Then

\[ \langle \psi \rvert B \otimes I \lvert \psi \rangle \ge \langle \psi \rvert A \otimes I \lvert \psi \rangle - \delta - 2\sqrt\varepsilon . \]

Proof ▶

Bound $\langle \psi \rvert B \otimes I \lvert \psi \rangle $ from below by $\mathbb {E}_{{\boldsymbol {x}}}\sum _a \langle \psi \rvert B^{\boldsymbol {x}}_a \otimes B^{\boldsymbol {x}}_a \lvert \psi \rangle $. Then apply Proposition 3.24 twice to replace this by $\mathbb {E}_{{\boldsymbol {x}}}\sum _a \langle \psi \rvert A^{\boldsymbol {x}}_a \otimes A^{\boldsymbol {x}}_a \lvert \psi \rangle $, and finish with strong self-consistency of $A$.

Lemma 3.39 Self-consistency implies data-processing closeness

✓

Let $A$ be a $\delta $-strongly self-consistent submeasurement and let $P$ be a projective submeasurement such that $P_a^x \otimes I \approx _\varepsilon A_a^x \otimes I$. Then for every function $f$,

\[ P_{[f(a)=b]}^x \otimes I \approx _{8\delta + 8\sqrt\varepsilon } A_{[f(a)=b]}^x \otimes I. \]

Proof ▶

First prove

\begin{equation} P^x_{[f(a)=b]} \otimes I \approx _{2\delta + 4\sqrt{\varepsilon }} I \otimes A_{[f(a)=b]}^x. \label{eq:what-we-want-to-prove-but-on-wrong-side} \end{equation}

Expanding the squared norm and using projectivity gives

\begin{align} & \mathbb {E}_{{\boldsymbol {x}}} \sum _b \lVert (P^{{\boldsymbol {x}}}_{[f(a)=b]} \otimes I - I \otimes A_{[f(a)=b]}^{{\boldsymbol {x}}}) \lvert \psi \rangle \rVert ^2 \nonumber \\ \leq ~ & \langle \psi \rvert P \otimes I \lvert \psi \rangle + \langle \psi \rvert I \otimes A \lvert \psi \rangle - 2\cdot \mathbb {E}_{{\boldsymbol {x}}} \sum _b \langle \psi \rvert P^{{\boldsymbol {x}}}_{[f(a)=b]} \otimes A^{{\boldsymbol {x}}}_{[f(a)=b]} \lvert \psi \rangle . \label{eq:gonna-handle-third-term} \end{align}

Proposition 3.33 bounds the first term by $\langle \psi \rvert A \otimes I \lvert \psi \rangle +2\sqrt{\varepsilon }$, and Proposition 3.24 together with strong self-consistency bounds the third term below by $\langle \psi \rvert A \otimes I \lvert \psi \rangle -\delta -\sqrt{\varepsilon }$. Substituting into 14 yields 13. Now combine 13 with

\[ A^x_{[f(a)=b]} \otimes I \approx _{2\delta } I \otimes A^x_{[f(a)=b]} \]

from Lemma 3.37, and conclude by Lemma 3.27.

Lemma 3.40 Self-consistency moves one copy to the same side

✓

Let $A=\{ A_a\} $ be a $\zeta $-strongly self-consistent submeasurement. Then

\[ \sum _a \langle \psi \rvert A_a^2 \otimes I \lvert \psi \rangle \ge \sum _a \langle \psi \rvert A_a \otimes I \lvert \psi \rangle - \zeta . \]

Proof ▶

Apply Cauchy–Schwarz to the two-sided overlap $\sum _a \langle \psi \rvert A_a \otimes A_a \lvert \psi \rangle $ and compare it with the strong self-consistency lower bound.

Lemma 3.41 Bounding the missing mass of a close submeasurement

✓

Let $A=\{ A_a\} $ be a measurement that is $\zeta $-strongly self-consistent, and let $B=\{ B_a\} $ be a submeasurement such that $A_a \otimes I \approx _\delta B_a \otimes I$. Writing $B=\sum _a B_a$, one has

\[ \lVert (I-B) \otimes I\lvert \psi \rangle \rVert ^2 \le 2\sqrt\delta + \zeta . \]

Proof ▶

Since $0 \le I-B \le I$, the left-hand side is at most $1-\langle \psi \rvert B \otimes I \lvert \psi \rangle $. Compare $\sum _a \langle \psi \rvert B_a^2 \otimes I \lvert \psi \rangle $ with $\sum _a \langle \psi \rvert A_a B_a \otimes I \lvert \psi \rangle $ and then with $\sum _a \langle \psi \rvert A_a^2 \otimes I \lvert \psi \rangle $ using the $\approx _\delta $ hypothesis, and finish with Lemma 3.40.

Lemma 3.42 Completing a close submeasurement to a full measurement

✓

Let $A=\{ A_a\} $ be a measurement that is $\zeta $-strongly self-consistent, let $B=\{ B_a\} $ be a submeasurement such that $A_a \otimes I \approx _\delta B_a \otimes I$, and let $C$ be the measurement obtained by adding the missing mass $I-B$ to one distinguished answer $a^*$. Then

\[ A_a \otimes I \approx _{2\delta + 4\sqrt\delta + 2\zeta } C_a \otimes I. \]

Proof of 3.42 ▶

By Lemma 3.26,

\[ \sum _a \lVert (A_a-C_a)\otimes I \lvert \psi \rangle \rVert ^2 \leq 2\delta + 2 \cdot \lVert (I-B)\otimes I \lvert \psi \rangle \rVert ^2. \]

It remains to bound the residual term. Since $0 \le I-B \le I$,

\begin{align} \lVert (I-B) \otimes I \lvert \psi \rangle \rVert ^2 & \leq 1 -\sum _a \langle \psi \rvert B_a^2 \otimes I \lvert \psi \rangle . \label{eq:to-return-later-whatevs} \end{align}

By Proposition 3.24,

\[ \sum _a \langle \psi \rvert B_a^2 \otimes I \lvert \psi \rangle \approx _{\sqrt{\delta }} \sum _a \langle \psi \rvert (A_a B_a)\otimes I \lvert \psi \rangle \approx _{\sqrt{\delta }} \sum _a \langle \psi \rvert A_a^2\otimes I \lvert \psi \rangle . \]

Proposition 3.43 gives

\[ \sum _a \langle \psi \rvert A_a^2\otimes I \lvert \psi \rangle \geq \langle \psi \rvert A \otimes I \lvert \psi \rangle - \zeta = 1-\zeta . \]

Hence 15 implies

\[ \lVert (I-B) \otimes I \lvert \psi \rangle \rVert ^2 \le 2\sqrt\delta + \zeta . \]

Substituting this into the first bound proves the claim.

Theorem 3.43

✓

This is the same statement as Lemma 3.40: for a $\zeta $-strongly self-consistent submeasurement $A$,

\[ \sum _a \langle \psi \rvert (A_a)^2 \otimes I \lvert \psi \rangle \geq \sum _a \langle \psi \rvert A_a \otimes I \lvert \psi \rangle -\zeta . \]

Proof ▶

Immediate from Lemma 3.40.