the finite-dimensional case, in [JNV+20b] with an improved error dependence
and was extended to the infinite-dimensional case in [dlS21]. The proof uses
the polar decomposition.

######  Lemma 5.1 (Orthogonalization).

Let $\mathscr{A}$ be a von Neumann algebra with a normal state $\tau$.999Even
though in our application $\tau$ will be tracial, this is not required for the
lemma. Let $A=\\{A_{a}\\}_{a\in\mathcal{A}}\subset\mathscr{A}$ denote a
submeasurement. Suppose that

$\sum_{a}\tau(A_{a}(\mathbf{1}-A_{a}))\leq\zeta.$

Then there exists a projective submeasurement $\\{P_{a}\\}\subset\mathscr{A}$
such that

$A_{a}\approx_{\sqrt{18\zeta}}P_{a}\;.$

###### Proof.

We indicate how the lemma follows from [dlS21, Theorem 1.2]. Let
$n=|\mathcal{A}|+1$ and identify $\mathcal{A}$ with the set
$\\{1,\ldots,n-1\\}$. Let $A_{n}=\mathbf{1}-\sum_{a}A_{a}$ so
$\\{A_{a}\\}_{a\in\\{1,\ldots,n\\}}$ is a measurement. Applying [dlS21,
Theorem 1.2], we get orthogonal projections $P_{a}$ satisfying

$A_{a}\approx_{\sqrt{9\delta}}P_{a}\;,$ (43)

where

$\displaystyle\delta$
$\displaystyle=1-\sum_{a=1}^{n}\tau\big{(}A_{a}^{2}\big{)}$
$\displaystyle=\sum_{a=1}^{n-1}\tau(A_{a}(\mathbf{1}-A_{a}))+\tau\big{(}A_{n}-A_{n}^{2}\big{)}\;,$
(44)

where for the second line we used that $\\{A_{a}\\}_{a\in\\{1,\ldots,n\\}}$ is
a measurement. The first term is at most $\zeta$ by assumption. For the second
term we write

$\displaystyle\tau\big{(}A_{n}^{2}\big{)}$
$\displaystyle=\tau\Bigg{(}A_{n}\bigg{(}\mathbf{1}-\sum_{a=1}^{n-1}A_{a}\bigg{)}\Bigg{)}$
$\displaystyle=\tau\big{(}A_{n})-\sum_{a=1}^{n-1}\tau\big{(}A_{n}A_{a}\big{)}$
$\displaystyle\geq\tau\big{(}A_{n})-\sum_{a=1}^{n-1}\tau\big{(}\big{(}\mathbf{1}-A_{a}\big{)}A_{a}\big{)}$
$\displaystyle\geq\tau\big{(}A_{n}\big{)}-\zeta\;,$

where the inequality on the third line uses that

$A_{n}\,=\,\mathbf{1}-\sum_{a=1}^{n-1}A_{a}\,\leq\,\mathbf{1}-A_{a}$

for all $a\in\\{1,\ldots,n-1\\}$, and $A_{a}\geq 0$ for all $a$. Thus (44) is
at most $2\zeta$, which together with (43) proves the lemma. ∎

##### Complementary slackness.

The second ingredient is a duality result about positive linear maps which
appears in [dlS21]. The proof is based on an application of the Hahn-Banach
theorem.

######  Lemma 5.2 (Proposition 7.1 in [dlS21]).

Let $\mathscr{A}$ be a von Neumann algebra and let
$\varphi_{1},\ldots,\varphi_{k}:\mathscr{A}\to\mathbb{C}$ be normal positive
linear maps. Then there is a unique normal linear map
$\psi:\mathscr{A}\to\mathbb{C}$ of minimal norm such that
$\psi\geq\varphi_{i}$ for all $i$. Moreover there exists a measurement
$\\{T_{i}\\}_{i\in[k]}$ such that for all $X\in\mathscr{A}$,

$\psi(X)=\sum_{i}\varphi_{i}(T_{i}X)$ (45)

In finite dimensions this lemma corresponds to the complementary slackness
condition of a particular semidefinite program satisfying strong duality (see
[NV18b, Lemma 10] for the finite-dimensional version of this statement). In
the proof of Lemma 4.2, we use Lemma 5.2 to define the “maximum” $\psi$ of a
collection of linear forms $\varphi_{i}$. This step can be thought of as a
replacement for “majority decoding” in analyses of low-degree testing in the
commutative (i.e. classical) case [GLR+91, RS92].

##### Local-to-global variance bound.

The third ingredient is the following lemma. Recall that $\mathcal{C}$ is a
$[n,k,d]_{\Sigma}$ code. Define $\gamma=1-\frac{d}{n}$.

######  Lemma 5.3.

Let $(\tau,A,B,P)$ be an $(\varepsilon,\delta)$-good strategy for the tensor
code test with $\mathcal{C}^{\otimes m}$. Let $\\{T_{g}\\}$ be a measurement
with outcomes in $\mathcal{C}^{\otimes m}$. Then on average over uniform
$x,y\in[n]^{m}$,

$A^{x}_{g(x)}T^{1/2}_{g}\approx_{\zeta_{var}}A^{y}_{g(y)}T^{1/2}_{g}$

where
$\zeta_{var}=\sqrt{m}\,\Big{(}2\sqrt{2\varepsilon}+2\sqrt{\gamma}\Big{)}$.

Before proving Lemma 5.3 we first prove a “local” version of Lemma 5.3, where
the closeness of $A^{x}_{g(x)}T^{1/2}_{g}$ and $A^{y}_{g(y)}T^{1/2}_{g}$ hold
when $x,y$ are random points from a random axis-parallel line (rather than
being random points from the entire domain $[n]^{m}$).

######  Lemma 5.4.

Let $(\tau,A,B,P)$ be an $(\varepsilon,\delta)$-good strategy for the tensor
code test with $\mathcal{C}^{\otimes m}$. Then on overage over axis-parallel
lines $\ell$, and $x,y\in\ell$,

$A^{x}_{g(x)}T^{1/2}_{g}\approx_{\zeta_{local}}A^{y}_{g(y)}T^{1/2}_{g}$

where $\zeta_{local}=2\sqrt{2\varepsilon}+2\sqrt{\gamma}$.

###### Proof.

By definition of $(\varepsilon,\delta)$-good strategy we have
$A^{x}_{a}\simeq_{\varepsilon}B^{\ell}_{[f\mapsto f(x)\mid a]}$, and thus by
Proposition 2.5 we have
$A^{x}_{a}\approx_{\sqrt{2\varepsilon}}B^{\ell}_{[f\mapsto f(x)\mid a]}$. This
implies that

$A^{x}_{g(x)}T_{g}^{1/2}\approx_{\sqrt{2\varepsilon}}B^{\ell}_{[f:f(x)=g(x)]}\cdot
T_{g}^{1/2}$ (46)

on average over a uniformly random axis-parallel line $\ell$ and a uniformly
random point $x\in\ell$. This holds because

$\displaystyle\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{g\in\mathcal{C}^{\otimes
m}}\left\|\Big{(}A^{x}_{g(x)}-B^{\ell}_{[f:f(x)=g(x)]}\Big{)}T_{g}^{1/2}\right\|^{2}_{\tau}=\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{a\in\Sigma}\sum_{g:g(x)=a}\left\|\Big{(}A^{x}_{g(x)}-B^{\ell}_{[f\mapsto
f(x)\mid a]}\Big{)}T_{g}^{1/2}\right\|^{2}_{\tau}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{a\in\Sigma}\sum_{g:g(x)=a}\tau\left(\Big{(}A^{x}_{a}-B^{\ell}_{[f\mapsto
f(x)\mid
a]}\Big{)}^{2}T_{g}\right)\leq\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{a\in\Sigma}\tau\Big{(}\Big{(}A^{x}_{a}-B^{\ell}_{[f\mapsto
f(x)\mid a]}\Big{)}^{2}\Big{)}\leq 2\varepsilon$

where the first inequality follows from the fact that $\\{T_{g}\\}$ is a
measurement. Next, we have that

$B^{\ell}_{[f:f(x)=g(x)]}\cdot
T_{g}^{1/2}\approx_{\sqrt{\gamma}}B^{\ell}_{g|_{\ell}}\cdot T_{g}^{1/2}~{}.$
(47)

This holds because

$\displaystyle\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{g\in\mathcal{C}^{\otimes
m}}\left\|\Big{(}B^{\ell}_{[f:f(x)=g(x)]}-B^{\ell}_{g|_{\ell}}\Big{)}T_{g}^{1/2}\right\|^{2}_{\tau}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{h\in\mathcal{C}}\tau\left(\Big{(}B^{\ell}_{[f:f(x)=h(x)]}-B^{\ell}_{h}\Big{)}^{2}T_{[g:g|_{\ell}=h]}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\ell,x\in\ell}\sum_{h\in\mathcal{C}}\tau\left(B^{\ell}_{[f:f(x)=h(x),f\neq
h]}\cdot T_{[g:g|_{\ell}=h]}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\ell}\sum_{h,f\in\mathcal{C}}\Big{(}\operatorname*{\mathbb{E}}_{x\in\ell}\mathbb{I}[f(x)=h(x),f\neq
h]\Big{)}\cdot\tau\left(B^{\ell}_{f}\cdot T_{[g:g|_{\ell}=h]}\right)$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\ell}\sum_{h,f\in\mathcal{C}}\gamma\cdot\tau\left(B^{\ell}_{f}\cdot
T_{[g:g|_{\ell}=h]}\right)$ $\displaystyle=\gamma$

where the third line follows from the fact that the $\\{B^{\ell}_{h}\\}$
measurements are projective, in the fourth line we used
$\mathbb{I}[f(x)=h(x),f\neq h]$ to denote the characteristic function of the
indicated set, the fifth line follows from the fact that two distinct
codewords $f\neq h$ can only agree on at most $\gamma$ fraction of
coordinates, and the last line follows from the fact that $\\{B^{\ell}_{f}\\}$
and $\\{T_{g}\\}$ are measurements. Thus putting together (46) and (47) we get

$\displaystyle
A^{x}_{g(x)}T_{g}^{1/2}\approx_{\sqrt{2\varepsilon}}B^{\ell}_{[f:f(x)=g(x)]}\cdot
T_{g}^{1/2}\approx_{\sqrt{\gamma}}B^{\ell}_{g|_{\ell}}\cdot T_{g}^{1/2}$
$\displaystyle\approx_{\sqrt{\gamma}}B^{\ell}_{[f:f(y)=g(y)]}\cdot
T_{g}^{1/2}\approx_{\sqrt{2\varepsilon}}A^{y}_{g(y)}\cdot T_{g}^{1/2}.$

on average over a random axis-parallel line $\ell$ and independent random
points $x,y\in\ell$. ∎

The proof of Lemma 5.3 now follows by using the expansion of the hypercube to
transfer the “local variance” bound of Lemma 5.4 to a “global variance” bound.

###### Proof of Lemma 5.3.

Define the graph $G$ to have vertex set $[n]^{m}$, and vertices
$x,y\in[n]^{m}$ are connected if and only if they differ in at most one
coordinate. Define $N=n^{m}$. The Laplacian $L$ associated with this graph $G$
has a zero eigenvector

${|\varphi_{0}\rangle}=\frac{1}{\sqrt{N}}\sum_{x\in[n]^{m}}{|x\rangle}.$

Furthermore the second largest eigenvalue $\lambda_{2}$ is equal to
$\frac{1}{mN}$.

For all $g\in\mathcal{C}^{\otimes m}$, define the positive linear functional
$\psi_{g}(X)=\tau\big{(}T_{g}^{1/2}\cdot X\cdot T_{g}^{1/2}\big{)}$. By Lemma
A.2, we have that

$\displaystyle\operatorname*{\mathbb{E}}_{x,y\sim{[n]}^{m}}\sum_{g\in\mathcal{C}^{\otimes
m}}\left\|\bigl{(}A^{x}_{g(x)}-A^{y}_{g(y)}\bigr{)}T_{g}^{1/2}\right\|_{\tau}^{2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y\sim[n]^{m}}\sum_{g\in\mathcal{C}^{\otimes
m}}\psi_{g}\left(\Big{(}A^{x}_{g(x)}-A^{y}_{g(y)}\Big{)}^{2}\right)$
$\displaystyle\leq
m\operatorname*{\mathbb{E}}_{\ell,x,y\in\ell}\sum_{g\in\mathcal{C}^{\otimes
m}}\psi_{g}\left(\Big{(}A^{x}_{g(x)}-A^{y}_{g(y)}\Big{)}^{2}\right)$
$\displaystyle=m\,\operatorname*{\mathbb{E}}_{(x,y)\sim
G}\sum_{g\in\mathcal{C}^{\otimes
m}}\left\|\bigl{(}A^{x}_{g(x)}-A^{y}_{g(y)}\bigr{)}T_{g}^{1/2}\right\|_{\tau}^{2}$
$\displaystyle\leq m\,\zeta_{local}^{2},$

which completes the proof by definition. ∎

We now proceed to prove Lemma 4.2.

###  5.1 Proof of Lemma 4.2, Step 1: Construction of (non-projective) $H$

Let $A=\\{A^{x}\\}_{x\in[n]^{m}}$ and $\\{G_{g}\\}$ be as in the statement of
Lemma 4.2. Let $\mathscr{A}$ and $\tau$ be the underlying von Neumann algebra
and normal trace. For all $g\in\mathcal{C}^{\otimes m}$ define

$A_{g}=\operatorname*{\mathbb{E}}_{x}A^{x}_{g(x)}\;,$

where the expectation is uniform over all $x\in[n]^{m}$. For all
$g\in\mathcal{C}^{\otimes m}$ define $\varphi_{g}:\mathscr{A}\to\mathbb{C}$ by

$\forall X\in\mathscr{A}\;,\qquad\varphi_{g}(X)=\tau(X\cdot A_{g})\;.$

Notice that $\varphi_{g}$ is a normal positive linear map. It is positive
because $\tau(XA_{g})=\tau(A_{g}^{1/2}XA_{g}^{1/2})\geq 0$ for positive
$X\in\mathscr{A}$. It is normal because $\tau$ is normal, which by definition
(see Section 2) implies that there is a positive trace class operator $M$ such
that $\tau(XA_{g})=\tau(A_{g}^{1/2}XA_{g}^{1/2})=\mbox{\rm
tr}(A_{g}^{1/2}XA_{g}^{1/2}M)$. Since $XA_{g}^{1/2}M$ is a trace class
operator and $A_{g}^{1/2}$ is bounded, we have that $\mbox{\rm
tr}(A_{g}^{1/2}XA_{g}^{1/2}M)=\mbox{\rm tr}(XA_{g}^{1/2}MA_{g}^{1/2})$; this
implies that $\varphi_{g}(X)=\mbox{\rm tr}(XA_{g}^{1/2}MA_{g}^{1/2})$ is
normal because $A_{g}^{1/2}MA_{g}^{1/2}$ is a positive trace class operator.

By Lemma 5.2 there exists a unique normal linear map $\psi$ of minimal norm
satisfying $\psi\geq\varphi_{g}$ for all $g\in\mathcal{C}^{\otimes m}$.
Moreover there exists a measurement $\\{T_{g}\\}$ such that

$\forall X\in\mathscr{A}\;,\qquad\psi(X)=\sum_{g}\varphi_{g}(T_{g}X)\;.$ (48)

We refer to Equation 48 as the _complementary slackness_ condition.

For all $x\in[n]^{m}$ and $g\in\mathcal{C}^{\otimes m}$ let

$H^{x}_{g}=A^{x}_{g(x)}\cdot T_{g}\cdot A^{x}_{g(x)}\;.$

We verify that for all $x\in[n]^{m}$, $\\{H^{x}_{g}\\}$ forms a
submeasurement:

$\displaystyle\sum_{g}H^{x}_{g}=\sum_{g}A^{x}_{g(x)}\cdot T_{g}\cdot
A^{x}_{g(x)}=\sum_{a}A^{x}_{a}\Big{(}\sum_{g:g(x)=a}T_{g}\Big{)}A^{x}_{a}\leq\sum_{a}(A^{x}_{a})^{2}=\sum_{a}A^{x}_{a}=\mathbf{1}.$
(49)

Finally, for $g\in\mathcal{C}^{\otimes m}$ define

$H_{g}=\operatorname*{\mathbb{E}}_{x\sim[n]^{m}}H^{x}_{g}\;.$

We proceed to argue that, except for the projectivity condition, the
submeasurement $\\{H_{g}\\}$ satisfies the conclusions of Lemma 4.2. We first
show a technical lemma.

######  Lemma 5.5.

Let $\zeta_{var}=\sqrt{m}(2\sqrt{2\varepsilon}+2\sqrt{\gamma})$ as in Lemma
5.3. Then

$\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\big{(}\big{|}H_{g}-A^{x}_{g(x)}T_{g}A^{x}_{g(x)}\big{|}\big{)}\leq{2\,\zeta_{var}}\;.$

###### Proof.

We have

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\big{(}\big{|}H_{g}-A^{x}_{g(x)}T_{g}A^{x}_{g(x)}\big{|}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\Big{(}\Big{|}\operatorname*{\mathbb{E}}_{y}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}T_{g}A^{y}_{g(y)}+\operatorname*{\mathbb{E}}_{y}A^{x}_{g(x)}T_{g}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}\Big{|}\Big{)}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\tau\big{(}\big{|}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}T_{g}A^{y}_{g(y)}\big{|}\big{)}+\tau\big{(}\big{|}A^{x}_{g(x)}T_{g}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}\big{|}\big{)}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\Big{(}\big{\|}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}T_{g}^{1/2}\big{\|}_{\tau}\cdot\big{\|}T_{g}^{1/2}A^{y}_{g(y)}\big{\|}_{\tau}$
$\displaystyle\hskip
85.35826pt+\big{\|}A^{x}_{g(x)}T_{g}^{1/2}\big{\|}_{\tau}\cdot\big{\|}T_{g}^{1/2}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}\big{\|}_{\tau}\Big{)}$
$\displaystyle\leq
2\Big{(}\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\big{\|}\big{(}A^{y}_{g(y)}-A^{x}_{g(x)}\big{)}T_{g}^{1/2}\big{\|}_{\tau}^{2}\Big{)}^{1/2}\Big{(}\operatorname*{\mathbb{E}}_{x}\sum_{g}\big{\|}T_{g}^{1/2}A^{x}_{g(x)}\big{\|}_{\tau}^{2}\Big{)}^{1/2}\;,$

where the second line uses the triangle inequality for the $1$-norm (Item 4 of
Proposition 2.1), the third the Hölder inequality (Item 2 of Proposition 2.1),
and the fourth the Cauchy-Schwarz inequality. The lemma then follows from
Lemma 5.3 together with the fact that $\|A^{x}_{a}\|\leq 1$ for every $x,a$
and $\sum_{g}T_{g}\leq\mathbf{1}$. ∎

####  5.1.1 Bounding the completeness of $H$

######  Lemma 5.6.

$\sum_{g}\tau(H_{g})\geq 1-\nu$.

###### Proof.

We compute

$\displaystyle\sum_{g}\tau(H_{g})$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\left(A^{x}_{g(x)}\cdot
T_{g}\cdot A^{x}_{g(x)}\right)$ (50)
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\left(T_{g}\cdot
A^{x}_{g(x)}\right)$ Cyclicity of trace, projectivity of $A^{x}_{a}$
$\displaystyle=\sum_{g}\tau\left(T_{g}\cdot A_{g}\right)$
$\displaystyle=\sum_{g}\varphi_{g}(T_{g})$ Definition of $\varphi_{g}$
$\displaystyle=\psi(\mathbf{1})$ Complementary slackness (51)
$\displaystyle=\sum_{g}\psi(G_{g})$ $\\{G_{g}\\}$ is a measurement
$\displaystyle\geq\sum_{g}\varphi_{g}(G_{g})$ $\psi\geq\varphi_{g}$ for all
$g$ $\displaystyle=\sum_{g}\tau(G_{g}\cdot A_{g})$ Definition of $\varphi_{g}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(G_{[g(x)=a]}\cdot
A^{x}_{a})$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(G_{[g(x)=a]})-\operatorname*{\mathbb{E}}_{x}\sum_{b\neq
a}\tau(G_{[g(x)=a]}\cdot A^{x}_{b})$ $\displaystyle\geq 1-\nu\;,$

by the assumption that $\\{G_{g}\\}$ is $\nu$-inconsistent with $A$. ∎

####  5.1.2 Bounding the consistency of $H$ with $A$

Let $\zeta_{var}$ be as in Lemma 5.5.

######  Lemma 5.7.

On average over $x\sim[n]^{m}$, $H_{[g\mapsto g(x)\mid
a]}\simeq_{2\,{\zeta_{var}}}A^{x}_{a}$.

###### Proof.

By expanding the definition of $H$ we get

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\left(A^{x}_{b}\cdot H_{[g\mapsto g(x)\mid a]}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g,b:g(x)\neq
b}\tau\left(A^{x}_{b}H_{g}\right)$ (52)
$\displaystyle\approx_{2\,{\zeta_{var}}}\operatorname*{\mathbb{E}}_{x}\sum_{g,b:g(x)\neq
b}\tau\left(A^{x}_{b}\cdot A^{x}_{g(x)}\cdot T_{g}\cdot A^{x}_{g(x)}\right)$
(53) $\displaystyle=0$ Projectivity of $A^{x}_{b}$ (54)

Here the application of Lemma 5.5 is justified by forming the difference
between (53) and (52) and bounding it as

$\displaystyle\big{|}\eqref{eq:si-cons-1b}-\eqref{eq:si-cons-1a}\big{|}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x}\Big{|}\sum_{g,b:g(x)\neq
b}\tau\big{(}A^{x}_{b}\cdot(H_{g}-A^{x}_{g(x)}\cdot T_{g}\cdot
A^{x}_{g(x)}\big{)}\big{)}\Big{|}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x}\sum_{g}\big{|}\tau\big{(}(\mathbf{1}-A^{x}_{g(x)})\cdot(H_{g}-A^{x}_{g(x)}\cdot
T_{g}\cdot A^{x}_{g(x)}\big{)}\big{)}\big{|}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\Big{(}\big{|}H_{g}-A^{x}_{g(x)}\cdot
T_{g}\cdot A^{x}_{g(x)}\big{|}\Big{)}$
$\displaystyle\leq{2\,{\zeta_{var}}}\;,$

where the third line follows from Hölder’s inequality (Item 3 of Proposition
2.1) and $\|\mathbf{1}-A^{x}_{g(x)}\|\leq 1$. ∎

####  5.1.3 Bounding the projectivity of $H$

######  Lemma 5.8.

Let $\gamma_{m}=1-(d/n)^{m}$. Then $\sum_{g}\tau(H_{g}-H_{g}^{2})\leq
5\,{\zeta_{var}}+\gamma_{m}$.

###### Proof.

Write

$\displaystyle\sum_{g}\tau(H_{g}^{2})$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\left(H^{x}_{g}\cdot
H_{g}\right)$
$\displaystyle\approx_{2\,{\zeta_{var}}}\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\left(A^{x}_{g(x)}\cdot
H^{x}_{g}\cdot A^{x}_{g(x)}\cdot T_{g}\right)\;,$ (55)

where the approximation on the second line follows from Lemma 5.5. Now we
write

RHS of Eq. 55
$\displaystyle\approx_{\gamma_{m}}\operatorname*{\mathbb{E}}_{x}\sum_{g,g^{\prime}}\tau\left(A^{x}_{g(x)}\cdot
H^{x}_{g^{\prime}}\cdot A^{x}_{g(x)}\cdot T_{g}\right)$ To be proved below
(56)
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g,g^{\prime}}\tau\left(H^{x}_{g^{\prime}}\cdot
A^{x}_{g(x)}\cdot T_{g}\right)$ $A^{x}_{g(x)}\cdot H^{x}_{g^{\prime}}\cdot
A^{x}_{g(x)}=H^{x}_{g^{\prime}}\cdot A^{x}_{g(x)}$ (57)
$\displaystyle\approx_{\,{\zeta_{var}}}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,g^{\prime}}\tau\left(H^{x}_{g^{\prime}}\cdot
A^{y}_{g(y)}\cdot T_{g}\right)$ To be proved below (58)
$\displaystyle=\sum_{g,g^{\prime}}\tau\left(H_{g^{\prime}}\cdot A_{g}\cdot
T_{g}\right)$ (59) $\displaystyle=\sum_{g,g^{\prime}}\varphi_{g}(T_{g}\cdot
H_{g^{\prime}})$ Definition of $\varphi_{g}$ (60)
$\displaystyle=\sum_{g^{\prime}}\psi(H_{g^{\prime}})$ Complementary slackness
(61) $\displaystyle\geq\sum_{g^{\prime}}\varphi_{g^{\prime}}(H_{g^{\prime}})$
$\psi\geq\varphi_{g^{\prime}}$ for all $g^{\prime}$ (62)
$\displaystyle=\sum_{g^{\prime}}\tau(H_{g^{\prime}}\cdot A_{g^{\prime}})$
Definition of $\varphi_{g^{\prime}}$ (63)
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(H_{[g\mapsto
g(x)\mid a]}\cdot A^{x}_{a}\right)$ (64)
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\Big{(}H_{[g\mapsto
g(x)\mid a]}\cdot\Big{(}\mathbf{1}-\sum_{b\neq a}A^{x}_{b}\Big{)}\Big{)}$ (65)
$\displaystyle=\tau(H)-\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\big{(}H_{[g\mapsto g(x)\mid a]}\cdot A^{x}_{b}\big{)}$ (66)
$\displaystyle\geq\tau(H)-2\,{\zeta_{var}}$ (67)

This completes the proof of the lemma, modulo Eq. (56) and Eq. (58), which we
now turn to.

##### Proof of approximation in Eq. 56.

We aim to show that

$\Big{|}\operatorname*{\mathbb{E}}_{x}\sum_{g^{\prime}\neq
g}\tau\left(A^{x}_{g(x)}\cdot H^{x}_{g^{\prime}}\cdot A^{x}_{g(x)}\cdot
T_{g}\right)\Big{|}\leq\gamma_{m}\;.$

To see this, we show

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{g^{\prime}\neq
g}\tau\left(A^{x}_{g(x)}\cdot H^{x}_{g^{\prime}}\cdot A^{x}_{g(x)}\cdot
T_{g}\right)$ $\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g\neq
g^{\prime}}\tau\left(A^{x}_{g(x)}\cdot A^{x}_{g^{\prime}(x)}\cdot
T_{g^{\prime}}\cdot A^{x}_{g^{\prime}(x)}\cdot A^{x}_{g(x)}\cdot T_{g}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g\neq
g^{\prime}}\tau\left(A^{x}_{g(x)}\cdot T_{g^{\prime}}\cdot A^{x}_{g(x)}\cdot
T_{g}\right)\cdot\mathbb{I}[g(x)=g^{\prime}(x)]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g\neq
g^{\prime}}\tau\left(T_{g^{\prime}}\cdot A^{x}_{g(x)}\cdot T_{g}\cdot
A^{x}_{g(x)}\right)\cdot\mathbb{I}[g(x)=g^{\prime}(x)]$ Cyclicity of trace
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{g\neq
g^{\prime}}\tau\left(T_{g^{\prime}}\cdot
H_{g}\right)\cdot\mathbb{I}[g(x)=g^{\prime}(x)]~{}.$ Definition of $H_{g}$
(68)

To conclude, note that since $\tau(T_{g^{\prime}}H_{g})\geq 0$ for all
$g,g^{\prime}$ and $\sum_{g\neq g^{\prime}}\tau(T_{g^{\prime}}H_{g})\leq 1$ it
follows that (68) is at most

$\max_{g\neq
g^{\prime}}\;\operatorname*{\mathbb{E}}_{x}\,\mathbb{I}[g(x)=g^{\prime}(x)]\,\leq\,1-\frac{d^{m}}{n^{m}}=\gamma_{m}\;,$

because two distinct codewords $g\neq g^{\prime}$ of $\mathcal{C}^{\otimes m}$
can only agree on at most $n^{m}-d^{m}$ coordinates.

##### Proof of approximation in Eq. 58.

We aim to show that

$\operatorname*{\mathbb{E}}_{x}\sum_{g,g^{\prime}}\tau\left(H^{x}_{g^{\prime}}\cdot
A^{x}_{g(x)}\cdot
T_{g}\right)\approx_{\,{\zeta_{var}}}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,g^{\prime}}\tau\left(H^{x}_{g^{\prime}}\cdot
A^{y}_{g(y)}\cdot T_{g}\right)\;.$ (69)

To do this, we bound the magnitude of the difference:

$\displaystyle\Big{|}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,g^{\prime}}\tau\left(H^{x}_{g^{\prime}}\cdot(A^{x}_{g(x)}-A^{y}_{g(y)})\cdot
T_{g}\right)\Big{|}$
$\displaystyle=\Big{|}\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\tau\Big{(}T_{g}^{1/2}\cdot\Big{(}\sum_{g^{\prime}}H^{x}_{g^{\prime}}\Big{)}\cdot(A^{x}_{g(x)}-A^{y}_{g(y)})\cdot
T_{g}^{1/2}\Big{)}\Big{|}$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\Big{(}T_{g}^{1/2}\cdot\Big{(}\sum_{g^{\prime}}H^{x}_{g^{\prime}}\Big{)}^{2}\cdot
T_{g}^{1/2}\Big{)}}\cdot\sqrt{\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\tau\Big{(}T_{g}^{1/2}\cdot\big{(}A^{x}_{g(x)}-A^{y}_{g(y)}\big{)}^{2}\cdot
T_{g}^{1/2}\Big{)}}$ $\displaystyle\leq\sqrt{1}\cdot\,{\zeta_{var}}$

where we used Cauchy-Schwarz, the fact that $\\{H^{x}_{g^{\prime}}\\}$ and
$\\{T_{g}\\}$ are (sub)measurements, and Lemma 5.3. This concludes the proof
of (67) and hence the lemma. ∎

###  5.2 Proof of Lemma 4.2, Step 2: Making $H$ projective

To conclude the proof of Lemma 4.2, we show how to modify the submeasurement
$\\{H_{g}\\}$ defined and analyzed in the previous section so that it is
projective. Recall that according to Lemma 5.8 $\\{H_{g}\\}$ satisfies

$\sum_{g}\tau(H_{g}-H_{g}^{2})\,\leq\,\eta\;,$

for $\eta=5\,{\zeta_{var}}+\gamma_{m}$. This condition allows us to apply the
Orthogonalization Lemma (Lemma 5.1). From the lemma it follows that there
exists a projective submeasurement $H^{\prime}=\\{H_{g}^{\prime}\\}$
satisfying

$H_{g}\approx_{\sqrt{18\eta}}H_{g}^{\prime}\;.$

####  5.2.1 Proof of Item 1 (Completeness)

The completeness of the projective submeasurement $\\{H_{g}^{\prime}\\}$ is
related to the completeness of $\\{H_{g}\\}$ in the following manner:

$\displaystyle\sum_{g}\tau(H_{g}^{\prime})$
$\displaystyle=\sum_{g}\tau(H_{g}^{\prime}\cdot H_{g}^{\prime})$
$\\{H_{g}^{\prime}\\}$ is projective
$\displaystyle\approx_{\sqrt{18\eta}}\sum_{g}\tau(H_{g}\cdot H_{g}^{\prime})$
$\displaystyle\approx_{\sqrt{18\eta}}\sum_{g}\tau(H_{g}\cdot H_{g})$
$\displaystyle\geq\sum_{g}\tau(H_{g})-\eta$ Lemma 5.8 (70)

####  5.2.2 Proof of Item 2 (Consistency with $A$)

Next we show consistency of $\\{H_{g}^{\prime}\\}$ with the measurements
$\\{A^{x}_{a}\\}$. Towards this we first prove that for all $x$,

$H_{[g\mapsto g(x)\mid a]}\approx_{\eta^{\prime}}H_{[g\mapsto g(x)\mid
a]}^{\prime}\;,$

where

$\eta^{\prime}=\sqrt{2\sqrt{18\eta}+\eta}.$

This is because

$\displaystyle\sum_{a}\tau\big{(}(H_{[g\mapsto g(x)\mid a]}-H_{[g\mapsto
g(x)\mid a]}^{\prime})^{2}\big{)}$ $\displaystyle=$
$\displaystyle\sum_{a}\tau(H_{[g\mapsto g(x)\mid
a]}^{2})+\sum_{a}\tau((H_{[g\mapsto g(x)\mid
a]}^{\prime})^{2})-2\sum_{a}\tau(H_{[g\mapsto g(x)\mid a]}\cdot H_{[g\mapsto
g(x)\mid a]}^{\prime})$ $\displaystyle\leq$
$\displaystyle\sum_{a}\tau(H_{[g\mapsto g(x)\mid
a]})+\sum_{a}\tau((H_{[g\mapsto g(x)\mid
a]}^{\prime}))-2\sum_{a}\tau(H_{[g\mapsto g(x)\mid a]}\cdot H_{[g\mapsto
g(x)\mid a]}^{\prime})$ $\displaystyle=$
$\displaystyle\sum_{g}\tau(H_{g})+\sum_{g}\tau(H_{g}^{\prime})-2\sum_{a}\tau(H_{[g\mapsto
g(x)\mid a]}\cdot H_{[g\mapsto g(x)\mid a]}^{\prime})$ $\displaystyle\leq$
$\displaystyle\sum_{g}\tau(H_{g})+\sum_{g}\tau(H_{g}^{\prime})-2\sum_{g}\tau(H_{g}\cdot
H_{g}^{\prime})$ $\displaystyle\leq$ $\displaystyle 2\sqrt{18\eta}+\eta.$

The third line follows from the fact that $\\{H_{[g(x)=a]}\\}$ and
$\\{H_{[g(x)=a]}^{\prime}\\}$ are submeasurements. The fifth line follows from
dropping terms $\tau(H_{g}\cdot H_{g^{\prime}}^{\prime})$ for $g\neq
g^{\prime}$, which are nonnegative. The sixth line follows from (each step of)
the derivation (70).

Using the fact that $\\{A^{x}_{a}\\}$ forms a complete measurement,

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\Big{(}H_{[g\mapsto g(x)\mid a]}^{\prime}\cdot A^{x}_{b}\Big{)}$
$\displaystyle=\tau(H^{\prime})-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\Big{(}H_{[g\mapsto
g(x)\mid a]}^{\prime}\cdot A^{x}_{a}\Big{)}$
$\displaystyle\approx_{\eta^{\prime}}\tau(H^{\prime})-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\Big{(}H_{[g\mapsto
g(x)\mid a]}\cdot A^{x}_{a}\Big{)}$
$\displaystyle\approx_{\eta^{\prime}}\tau(H)-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\Big{(}H_{[g\mapsto
g(x)\mid a]}\cdot A^{x}_{a}\Big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\Big{(}H_{[g\mapsto g(x)\mid a]}\cdot A^{x}_{b}\Big{)}$
$\displaystyle\leq 2\,{\zeta_{var}}$ (71)

where the second line follows from Proposition 2.7, the third line follows
from (70), and the last line follows from Lemma 5.7.

####  5.2.3 Proof of Item 3 (Agreement is well-explained)

The map $\psi$ constructed at the start of Section 5.1 satisfies
$\psi(X)\geq\varphi_{g}(X)=\tau(X\cdot A_{g})$ for all
$g\in\mathcal{C}^{\otimes m}$ and positive $X\in\mathrm{B}(\mathcal{H})$. We
compute

$\displaystyle\psi(\mathbf{1}-H^{\prime})$
$\displaystyle=\psi(\mathbf{1})-\psi(H^{\prime})$
$\displaystyle=\psi(\mathbf{1})-\sum_{g}\psi(H_{g}^{\prime})$
$\displaystyle\leq\psi(\mathbf{1})-\sum_{g}\tau(H_{g}^{\prime}\cdot A_{g})$
$\displaystyle=\psi(\mathbf{1})-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(H_{[g\mapsto
g(x)\mid a]}^{\prime}\cdot A^{x}_{a})$
$\displaystyle=\tau(H)-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(H_{[g\mapsto
g(x)\mid a]}^{\prime}\cdot A^{x}_{a})$
$\displaystyle\approx_{\eta^{\prime}}\tau(H^{\prime})-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(H_{[g\mapsto
g(x)\mid a]}^{\prime}\cdot A^{x}_{a})$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a\neq b}\tau(H_{[g\mapsto
g(x)\mid a]}^{\prime}\cdot A^{x}_{b})$ $\displaystyle\leq
2\eta^{\prime}+2\,{\zeta_{var}}$

where the equality $\psi(\mathbf{1})=\tau(H)$ follows from the equality
between (50) and (51), the sixth line follows from (70), and the last line
follows from (71). This implies

$\psi(\mathbf{1}-H^{\prime})\leq 3\eta^{\prime}+2\,\zeta_{var}.$

####  5.2.4 Putting everything together

To conclude the proof of Lemma 4.2, we set

$\zeta=3\eta^{\prime}+2\,{\zeta_{var}}\;.$

First we note that, since $t=n-d+1$, we can express
$\gamma=1-\frac{d}{n}\leq\frac{t}{n}$ and

$\gamma_{m}=1-\frac{d^{m}}{n^{m}}=1-\Big{(}1-\frac{t-1}{n}\Big{)}^{m}\leq
1-\Big{(}1-\frac{mt}{n}\Big{)}=\frac{mt}{n}.$

By the definitions of $\eta^{\prime}$ and $\zeta_{var}$, we have

$\displaystyle\zeta_{var}$
$\displaystyle=\sqrt{m}(2\sqrt{2\varepsilon}+2\sqrt{\gamma})=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\frac{1}{n}\right)~{},$
$\displaystyle\eta$
$\displaystyle=5\zeta_{var}+\gamma_{m}=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\frac{1}{n}\right),$
$\displaystyle\eta^{\prime}$
$\displaystyle=\sqrt{2\sqrt{18\eta}+\eta}=\mathrm{poly}(\eta)=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\frac{1}{n}\right),$
$\displaystyle\zeta$
$\displaystyle=3\eta^{\prime}+2\zeta_{var}=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\frac{1}{n}\right).$

##  6 Pasting

We now prove Lemma 4.3. For convenience we restate the lemma here:

See 4.3

###  6.1 Commutativity of the $A$’s

We first derive a consequence of passing the subcube commutation test with
high probability.

######  Lemma 6.1.

Let $\mathscr{S}=(\tau,A,B,P)$ be strategy for the tensor code test with code
$\mathcal{C}^{\otimes(m+1)}$ that passes the subcube commutation test with
probability $1-\delta$. Let $A=\\{A^{u,x}\\}_{u\in[n]^{m},x\in[n]}$ denote the
points measurements. On average over uniform and independently random
$(u,x),(v,y)\sim[n]^{m}\times[n]$,

$A^{u,x}_{a}A^{v,y}_{b}\approx_{\sqrt{32(m+1)\delta}}A^{v,y}_{b}A^{u,x}_{a}.$

###### Proof.

Suppose the strategy $\mathscr{S}$ passes the subcube commutation test with
probability $1-\delta$. Since the index $j=1$ in the test (see Figure 1) with
probability $(m+1)^{-1}$, the strategy passes the test conditioned on $j=1$
with probability at least $1-\delta(m+1)$. When $j=1$, the “subcube” is
actually the entire space $[n]^{m+1}$. This means that

$A^{u,x}_{a}\simeq_{(m+1)\delta}P^{u,x,v,y}_{[(a,b)\mapsto a]},$

on average over $(u,x),(v,y)\in[n]^{m+1}$ which implies

$A^{u,x}_{a}\approx_{\sqrt{2(m+1)\delta}}P^{u,x,v,y}_{[(a,b)\mapsto a]},$ (72)

by Proposition 2.5.

By multiple applications of Proposition 2.8, we have

$\displaystyle A^{u,x}_{a}A^{v,y}_{b}$
$\displaystyle\approx_{\sqrt{2(m+1)\delta}}A^{u,x}_{a}P^{u,x,v,y}_{[(a,b)\mapsto
b]}$ $\displaystyle\approx_{\sqrt{2(m+1)\delta}}P^{u,x,v,y}_{[(a,b)\mapsto
a]}P^{u,x,v,y}_{[(a,b)\mapsto b]}$ $\displaystyle=P^{u,x,v,y}_{[(a,b)\mapsto
b]}P^{u,x,v,y}_{[(a,b)\mapsto a]}$
$\displaystyle\approx_{\sqrt{2(m+1)\delta}}A^{v,y}_{b}P^{u,x,v,y}_{[(a,b)\mapsto
a]}$ $\displaystyle\approx_{\sqrt{2(m+1)\delta}}A^{v,y}_{b}A^{u,x}_{a}.$

The theorem now follows from the triangle inequality. ∎

###  6.2 Commutativity of the $G$’s

Having deduced that the points measurements approximately commute on average,
we now aim to deduce that the “subspace measurements” $\\{G^{x}\\}$
corresponding to the parallel $m$-dimensional subspaces
$S_{x}=\\{(u,x):u\in[n]^{m}\\}$ approximately commute. We first prove a
slightly weaker statement, which is that the subspace measurements
$\\{G^{x}\\}$ give rise to points measurements
$\\{G^{u,x}_{a}\\}_{a\in\Sigma}$ that approximately commute.

######  Lemma 6.2.

Let $\nu_{1}=8(\sqrt{\zeta}+\sqrt{(m+1)\delta})$. Let $\\{G^{x}_{g}\\}$ be
projective submeasurements satisfying the conditions in Lemma 4.3. Define
$G^{u,x}_{a}=G^{x}_{[g\mapsto g(u)\mid a]}$ for all
$(u,x)\in{[n]}^{m}\times[n]$. Then on average over uniform and independently
uniform $(u,x)$, $(v,y)\sim{[n]}^{m}\times[n]$,

$G^{u,x}_{a}G^{v,y}_{b}\approx_{\nu_{1}}G^{v,y}_{b}G^{u,x}_{a}~{}.$

###### Proof.

We compute

$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(\Bigl{(}G^{u,x}_{a}G^{v,y}_{b}-G^{v,y}_{b}G^{u,x}_{a}\Bigr{)}^{*}\Bigl{(}G^{u,x}_{a}G^{v,y}_{b}-G^{v,y}_{b}G^{u,x}_{a}\Bigr{)}\right)$
$\displaystyle=2$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{u,x}_{a}G^{v,y}_{b}-G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}\right)$

where in the second line we used the cyclicity of the trace $\tau$ and the
fact that $\\{G^{u,x}_{a}\\}$ is projective. By the consistency assumption
(Assumption 2 of Lemma 4.3), we have $G^{u,x}_{a}\simeq_{\zeta}A^{u,x}_{a}$
and therefore by Proposition 2.10 we have, on average over
$(u,x)\sim{[n]}^{m+1}$,

$\displaystyle G^{u,x}_{a}$
$\displaystyle\approx_{\sqrt{\zeta}}G^{u,x}_{a}A^{u,x}_{a}$ (73)
$\displaystyle G^{u,x}_{a}$
$\displaystyle\approx_{2\sqrt{\zeta}}G^{x}A^{u,x}_{a}$ (74)

where $G^{x}=\sum_{a}G^{x}_{[g\mapsto g(u)\mid a]}$.

The rest of the proof is outlined in the following sequence of approximations.

$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}\right)$
$\displaystyle\approx_{2\sqrt{\zeta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}G^{x}A^{u,x}_{a}\right)$
To be proved below (75) $\displaystyle\approx_{\sqrt{\zeta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}A^{u,x}_{a}\right)$
To be proved below (76) $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}\right)$
Cyclicity of the trace $\displaystyle\approx_{2\sqrt{\zeta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}G^{y}A^{v,y}_{b}\right)$
To be proved below (77) $\displaystyle\approx_{\sqrt{\zeta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}A^{v,y}_{b}\right)$
To be proved below (78) $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}A^{v,y}_{b}A^{u,x}_{a}\right)$
Cyclicity of the trace $\displaystyle\approx_{\sqrt{32(m+1)\delta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}A^{u,x}_{a}A^{v,y}_{b}\right)$
Lemma 6.1, Prop. 2.7 $\displaystyle\approx_{\sqrt{\zeta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}A^{v,y}_{b}\right)$
To be proved below (79) $\displaystyle\approx_{\sqrt{\zeta}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}\right).$
To be proved below (80)

This shows that

$\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}\right)\approx_{8\sqrt{\zeta}+\sqrt{32(m+1)\delta}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}\right).$

##### Proof of approximation in Eqs. 75 and 77.

Define $G^{u,x,v,y}_{a}=\sum_{b}G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}$ and it is
easy to verify that $\\{G^{u,x,v,y}_{a}\\}$ forms a submeasurement. Hence, we
have

$\begin{split}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}\right)&=_{\phantom{2\sqrt{\zeta}}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a}\tau\left(G^{u,x,v,y}_{a}\cdot
G^{u,x}_{a}\right)\\\
&\approx_{2\sqrt{\zeta}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a}\tau\left(G^{u,x,v,y}_{a}\cdot
G^{x}A^{u,x}_{a}\right)\\\
&=_{\phantom{2\sqrt{\zeta}}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}G^{x}A^{u,x}_{a}\right),\end{split}$

where the approximation follows from Propositions 2.7 and 74. This gives Eq.
75.

Similarly, to prove the approximation in Eq. 77, we define
$H^{u,x,v,y}_{b}=\sum_{a}A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}$. Then

$\begin{split}\sum_{b}H^{u,x,v,y}_{b}{\bigl{(}H^{u,x,v,y}_{b}\bigr{)}}^{*}&=\sum_{b}\sum_{a,a^{\prime}}A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}G^{u,x}_{a^{\prime}}G^{v,y}_{b}A^{u,x}_{a^{\prime}}\\\
&=\sum_{b}\sum_{a}A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}A^{u,x}_{a}\\\
&\leq\sum_{a,b}A^{u,x}_{a}G^{v,y}_{b}A^{u,x}_{a}\\\
&\leq\mathbf{1},\end{split}$

where the second line uses the projectivity of
$\bigl{\\{}G^{u,x}_{a}\bigr{\\}}$ and the third line uses
$G^{u,x}_{a}\leq\mathbf{1}$. By Propositions 2.7 and 74, we have

$\begin{split}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}\right)&=_{\phantom{2\sqrt{\zeta}}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{b}\tau\left(H^{u,x,v,y}_{b}G^{v,y}_{b}\right)\\\
&\approx_{2\sqrt{\zeta}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{b}\tau\left(H^{u,x,v,y}_{b}G^{y}A^{v,y}_{b}\right)\\\
&=_{\phantom{2\sqrt{\zeta}}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{u,x}_{a}G^{v,y}_{b}G^{u,x}_{a}G^{y}A^{v,y}_{b}\right).\end{split}$

##### Proof of approximations in Eqs. 76 and 78.

Let
$R^{x}_{g}=\operatorname*{\mathbb{E}}_{v,y}\sum_{b}G^{v,y}_{b}G^{x}_{g}G^{v,y}_{b}$.
It can be verified that $\\{R^{x}_{g}\\}$ forms a submeasurement:

$\sum_{g}R^{x}_{g}\leq\operatorname*{\mathbb{E}}_{v,y}\sum_{b}{(G^{v,y}_{b})}^{2}\leq\mathbf{1}.$

To show the approximation in Eq. 76, we bound the magnitude of the difference:

$\displaystyle\left|\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{{a,b}}\tau\left(G^{v,y}_{b}G^{u,x}_{a}G^{v,y}_{b}\cdot(\mathbf{1}-G^{x})\cdot
A^{u,x}_{a}\right)\right|$ $\displaystyle=$
$\displaystyle\left|\operatorname*{\mathbb{E}}_{u,x}\sum_{a}\tau\left(R^{x}_{[g\mapsto
g(u)\mid a]}\cdot(\mathbf{1}-G^{x})\cdot A^{u,x}_{a}\right)\right|$
$\displaystyle=$
$\displaystyle\left|\operatorname*{\mathbb{E}}_{u,x}\sum_{g}\tau\left(R^{x}_{g}\cdot(\mathbf{1}-G^{x})\cdot
A^{u,x}_{g(u)}\right)\right|$
$\displaystyle\leq_{\phantom{\sqrt{\varepsilon}}}$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\left(R^{x}_{g}\right)}\cdot\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{g}\tau\left(A^{u,x}_{g(u)}\cdot(\mathbf{1}-G^{x})\cdot
R^{x}_{g}\cdot(\mathbf{1}-G^{x})\cdot A^{u,x}_{g(u)}\right)}$ Cauchy-Schwarz
$\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{g}\tau\left(A^{u,x}_{g(u)}\cdot(\mathbf{1}-G^{x})\cdot
R^{x}_{g}\cdot(\mathbf{1}-G^{x})\cdot A^{u,x}_{g(u)}\right)}$
$\\{R^{x}_{g}\\}$ is a submeasurement $\displaystyle=$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{g}\tau\left((\mathbf{1}-G^{x})\cdot
R^{x}_{g}\cdot(\mathbf{1}-G^{x})\cdot\operatorname*{\mathbb{E}}_{u}A^{u,x}_{g(u)}\right)}$
$\\{A^{x}_{a}\\}$ is projective $\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{g}\psi^{x}\left((\mathbf{1}-G^{x})\cdot
R^{x}_{g}\cdot(\mathbf{1}-G^{x})\right)}$ Assumption 3 $\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\psi^{x}\left(\mathbf{1}-G^{x}\right)}$
$\\{R^{x}_{g}\\}$ is submeasurement, $\\{G^{x}\\}$ is projective
$\displaystyle\leq$ $\displaystyle\sqrt{\zeta}$
$\displaystyle\quad\text{Assumption~{}\ref{enu:pasting-boundedness}}.$

The proof of approximation in Eq. 78 follows in an identical manner.

##### Proof of approximations in Eqs. 79 and 80.

To show the approximation in Eq. 79, we define

$S^{v,y}=\sum_{b}A^{v,y}_{b}G^{v,y}_{b},$

and verify that

$S^{v,y}{(S^{v,y})}^{*}=\sum_{b,b^{\prime}}A^{v,y}_{b}G^{v,y}_{b}G^{v,y}_{b^{\prime}}A^{b,y}_{b^{\prime}}=\sum_{b}A^{v,y}_{b}G^{v,y}_{b}A^{b,y}_{b}\leq\mathbf{1},$

and

$\sum_{a}S^{v,y}G^{u,x}_{a}{(S^{v,y}G^{u,x}_{a})}^{*}\leq
S^{v,y}{(S^{v,y})}^{*}\leq\mathbf{1}.$

Applying Proposition 2.7 to Eq. 73, we have

$\begin{split}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{v,y}_{b}G^{v,y}_{b}G^{u,x}_{a}A^{u,x}_{a}\right)&=_{\phantom{\sqrt{\zeta}}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a}\tau\left(S^{v,y}G^{u,x}_{a}\cdot
G^{u,x}_{a}A^{u,x}_{a}\right)\\\
&\approx_{\sqrt{\zeta}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a}\tau\left(S^{v,y}G^{u,x}_{a}\cdot
G^{u,x}_{a}\right)\\\
&=_{\phantom{\sqrt{\zeta}}}\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(A^{v,y}_{b}G^{v,y}_{b}G^{u,x}_{a}\right),\end{split}$

which proves Eq. 79 by cyclicity of the trace.

The proof of approximation in Eq. 80 follows in an identical manner.

∎

We now show that the subspace measurements $\\{G^{x}\\}$ themselves
approximately commute.

######  Lemma 6.3.

Let $\gamma_{m}$ be as defined in Proposition 2.18 and
$\nu_{2}=4(\gamma_{m}+\nu_{1})$. Let $\\{G^{x}_{g}\\}$ be projective
submeasurements satisfying the conditions in Lemma 4.3.

Then on average over independently uniform $x,y\sim[n]$,

$G^{x}_{g}\,G^{y}_{h}\approx_{\nu_{2}}G^{y}_{h}\,G^{x}_{g}.$

###### Proof.

By definition, we need to bound

$\operatorname*{\mathbb{E}}_{x,y}\sum_{g,h}\tau\left({\Big{(}G^{x}_{g}\,G^{y}_{h}-G^{y}_{h}\,G^{x}_{g}\Big{)}}^{*}\Big{(}G^{x}_{g}\,G^{y}_{h}-G^{y}_{h}\,G^{x}_{g}\Big{)}\right)=2\operatorname*{\mathbb{E}}_{x,y}\sum_{g,h}\tau\left(G^{x}_{g}\,G^{y}_{h}-G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g}\right)$

where we used the cyclicity of the trace $\tau$ and the projectivity of
$\\{G^{x}_{g}\\}$.

For notational convenience we use the abbreviation
$G^{u,x}_{a}=G^{x}_{[g\mapsto g(u)\mid a]}$ for all
$(u,x)\in{[n]}^{m}\times[n]$. We have

$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{g,h}\tau\left(G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g}\right)$
$\displaystyle\approx_{\gamma_{m}\phantom{m}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),y}\sum_{a,h}\tau\left(G^{y}_{h}\,G^{u,x}_{a}\,G^{y}_{h}\,G^{u,x}_{a}\right)$
To be proved below (81) $\displaystyle\approx_{\gamma_{m}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}\,G^{u,x}_{a}\,G^{v,y}_{b}\,G^{u,x}_{a}\right)$
To be proved below (82) $\displaystyle\approx_{\nu_{1}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}\,G^{u,x}_{a}\,G^{u,x}_{a}\,G^{v,y}_{b}\right)$
Propositions 2.7 and 6.2 $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{a,b}\tau\left(G^{v,y}_{b}\,G^{u,x}_{a}\right)$
Projectivity of $G$’s $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{g,h}\tau\left(G^{x}_{g}\,G^{y}_{h}\right).$

##### Proof of approximation in Eq. 81.

To show the approximation in Eq. 81, we bound the magnitude of the difference:

$\displaystyle\left|\operatorname*{\mathbb{E}}_{(u,x),y}\sum_{\begin{subarray}{c}g,g^{\prime},h:\\\
g\neq
g^{\prime}\end{subarray}}\,\mathbb{I}[g(u)=g^{\prime}(u)]\,\tau\left(G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g^{\prime}}\right)\right|$
$\displaystyle=_{\phantom{\sqrt{\varepsilon}}}$
$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{\begin{subarray}{c}g,g^{\prime},h:\\\
g\neq
g^{\prime}\end{subarray}}\tau\left(G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g^{\prime}}\right)\,\operatorname*{\mathbb{E}}_{u}\mathbb{I}[g(u)=g^{\prime}(u)]$
$\tau(G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g^{\prime}})\geq 0$
$\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{\begin{subarray}{c}g,g^{\prime},h:\\\
g\neq
g^{\prime}\end{subarray}}\tau\left(G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g^{\prime}}\right)\,\Big{(}1-\frac{d^{m}}{n^{m}}\Big{)}$
Proposition 2.18 $\displaystyle\leq$ $\displaystyle\gamma_{m}$

where in the last inequality we used that summing
$\tau\left(G^{y}_{h}\,G^{x}_{g}\,G^{y}_{h}\,G^{x}_{g^{\prime}}\right)$ over
$g,g^{\prime},h$ is at most $1$.

##### Proof of approximation in Eq. 82.

To show the approximation in Eq. 82, we bound the magnitude of the difference:

$\displaystyle\left|\operatorname*{\mathbb{E}}_{(u,x),(v,y)}\sum_{\begin{subarray}{c}a,h,h^{\prime}:\\\
h\neq
h^{\prime}\end{subarray}}\,\mathbb{I}[h(v)=h^{\prime}(v)]\,\tau\left(G^{y}_{h}\,G^{u,x}_{a}\,G^{y}_{h^{\prime}}\,G^{u,x}_{a}\right)\right|$
$\displaystyle=_{\phantom{\sqrt{\varepsilon}}}$
$\displaystyle\operatorname*{\mathbb{E}}_{(u,x),y}\sum_{\begin{subarray}{c}a,h,h^{\prime}:\\\
h\neq
h^{\prime}\end{subarray}}\tau\left(G^{y}_{h}\,G^{u,x}_{a}\,G^{y}_{h^{\prime}}\,G^{u,x}_{a}\right)\,\operatorname*{\mathbb{E}}_{v}\mathbb{I}[h(v)=h^{\prime}(v)]$
$\displaystyle\leq$ $\displaystyle\gamma_{m}\;.$

∎

###  6.3 Pasting the $G$’s together: Method 1

Now that we have established the subspace submeasurements $\\{G^{x}\\}$
approximately commute, we “paste” them together into a single submeasurement
$H=\\{H_{h}\\}$ with outcomes in $\mathcal{C}^{\otimes(m+1)}$ that are
consistent with the $G$’s. We give two methods for achieving this. The first,
detailed in this section, is the simpler method, but it achieves a weaker
bound: instead of the value of $\mu$ claimed in Lemma 4.3 this method obtains

$\mu(\kappa,m,t,\varepsilon,\delta,\zeta,n^{-1})=\kappa+\mathrm{poly}(m,t)\cdot\left(\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)\right)^{1/t}\;,$
(83)

with a dependence on $1/t$ in the exponent. Intuitively, for this method we
define $H$ as a measurement that tries to “simultaneously” measure $t=n-d+1$
subspace submeasurements $G^{x_{1}},\ldots,G^{x_{t}}$ for a randomly chosen
tuple of distinct coordinates $(x_{1},\ldots,x_{t})\in[n]^{t}$, obtain
$m$-dimensional words $g_{1},\ldots,g_{t}\in\mathcal{C}^{\otimes m}$, and then
interpolate a “global” codeword $h\in\mathcal{C}^{\otimes m+1}$ such that
$h(u,x_{i})=g_{i}(u)$. Since the base code $\mathcal{C}$ is interpolable, by
Proposition 2.20, there is always a global codeword $h$ consistent with
$g_{1},\ldots,g_{t}$.

While the exponential dependence on $1/t$ in (83) remains acceptable for
applications where $t$ is thought of as constant, if the parameter grows even
e.g. logarithmically with $n$ the bound can become trivial. To address this
case in Section 6.4 we give a different method (explained in that section),
which obtains the bound claimed in Lemma 4.3.

We now formalize the first “interpolation” approach. We start by precisely
defining the pasted submeasurement $H$.

Let $x_{1},\ldots,x_{t}\in[n]$. Define an initial pasted submeasurement as
follows:

$H^{x_{1},\ldots,x_{t}}_{g_{1},\ldots,g_{t}}=G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{1}}_{g_{1}}.$

This forms a submeasurement because of each of the individual $G^{x}$’s are
submeasurements. Then, for all $h\in\mathcal{C}^{\otimes(m+1)}$, define the
following operators

$H^{x_{1},\ldots,x_{t}}_{h}=H^{x_{1},\ldots,x_{t}}_{h|_{x_{1}},\ldots,h|_{x_{t}}}$

where $h|_{x_{j}}$ denotes the codeword in $\mathcal{C}^{\otimes m}$ that
comes from setting the $(m+1)$-st coordinate of $h$ to $x_{j}$. This set
$H^{x_{1},\ldots,x_{t}}=\\{H^{x_{1},\ldots,x_{t}}_{h}\\}$ forms a
submeasurement. This is because the set

$S=\\{(g_{1},\ldots,g_{t})\in{\left(\mathcal{C}^{\otimes{m}}\right)}^{t}:\text{there
exists $h\in\mathcal{C}^{\otimes(m+1)}$ such that }h|_{x_{j}}=g_{j}\\}$

is a subset of ${\left(\mathcal{C}^{\otimes{m}}\right)}^{t}$, and furthermore
$S$ is in one-to-one correspondence with $\mathcal{C}^{\otimes(m+1)}$ as shown
in Proposition 2.19. Thus

$\sum_{h}H^{x_{1},\ldots,x_{t}}_{h}=\sum_{(g_{1},\ldots,g_{t})\in
S}H^{x_{1},\ldots,x_{t}}_{g_{1},\ldots,g_{t}}\leq\sum_{(g_{1},\ldots,g_{t})\in{\left(\mathcal{C}^{\otimes{m}}\right)}^{t}}H^{x_{1},\ldots,x_{t}}_{g_{1},\ldots,g_{t}}\leq\mathbf{1}.$

And finally, define the operators

$H_{h}=\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathsf{distinct}([n],t)}H^{x_{1},\ldots,x_{t}}_{h}$

where we define $\mathsf{distinct}([n],t)$ to denote the set of tuples
$(x_{1},\ldots,x_{t})\in{[n]}^{t}$ such that all of the coordinates are
distinct. It is easy to verify that $H=\\{H_{h}\\}$ forms a submeasurement. In
what follows, $H$ will interchangeably refer to both the set $\\{H_{h}\\}$ as
well as the sum $\sum_{h}H_{h}$; it should be clear from context which we are
referring to. We will repeatedly use the following simple claim.

######  Proposition 6.4.

Let $n,k\geq 1$ be integer. Let $x=(x_{1},\ldots,x_{k})\sim[n]^{k}$ be sampled
uniformly at random and let
$y=(y_{1},\ldots,y_{k})\sim\mathsf{distinct}([n],k)$. Then

$d_{\mathrm{TV}}(x,y)\leq\frac{k^{2}}{n}.$

###### Proof.

For any $z=(z_{1},\ldots,z_{k})\in[n]^{k}$,

$\displaystyle\Pr(x=z)$ $\displaystyle=\frac{1}{q^{k}},$
$\displaystyle\Pr(y=z)$
$\displaystyle=\left\\{\begin{array}[]{cl}\frac{1}{\binom{n}{k}k!}&\text{if
$z\in\mathsf{distinct}([n],k)$,}\\\ 0&\text{otherwise.}\end{array}\right.$

Because $\frac{1}{\binom{n}{k}k!}\geq\frac{1}{n^{k}}$, $\Pr(x=z)\geq\Pr(y=z)$
if and only if $z\notin\mathsf{distinct}([n],k)$. Hence,

$\displaystyle d_{\mathrm{TV}}(x,y)$
$\displaystyle=\max_{S\subseteq[n]^{k}}\\{\Pr(x\in S)-\Pr(y\in S)\\}$
$\displaystyle=\Pr(x\in\overline{\mathsf{distinct}([n],k)})-\Pr(y\in\overline{\mathsf{distinct}([n],k)})=\Pr(x\in\overline{\mathsf{distinct}([n],k)}]\;.$

We can upper-bound this probability as follows.

$\displaystyle\Pr(x\in\overline{\mathsf{distinct}([n],k)})$
$\displaystyle=\Pr(\exists i:x_{i}\in\\{x_{1},\ldots,x_{i-1}\\})$
$\displaystyle\leq\sum_{i=2}^{k}\Pr(x_{i}\in\\{x_{1},\ldots,x_{i-1}\\})\leq\sum_{i=2}^{k}\left(\frac{i-1}{n}\right)=\frac{k(k-1)}{2n}\;.$

∎

####  6.3.1 Bounding the consistency of $H$ with the $A$ measurements

First we bound the consistency of $H$ with line measurements $B^{\ell}$ where
$\ell$ are parallel to the $(m+1)$-st axis. In other words, we consider lines
$\ell$ consisting of points that only vary in the $(m+1)$-st coordinate. Since
we focus on such lines, we use the following abbreviation:

$B^{u}_{f}=B^{\ell}_{f}$

where $\ell=\ell(m+1,u)$ (see Definition 2.16 for the notation for axis-
parallel lines).

Since $(\tau,A,B,P)$ is an $(\varepsilon,\delta)$-good strategy for
$\mathcal{C}^{\otimes(m+1)}$, we have by definition that

$\operatorname*{\mathbb{E}}_{\ell,y\sim\ell}\sum_{f\in\mathcal{C}}\tau\left(B^{\ell}_{f}\,A^{y}_{f(y_{j})}\right)\geq
1-\varepsilon$

where the expectation is over all axis-parallel lines
$\ell=\ell(j,\alpha_{-j})$ (not necessarily the ones parallel to direction
$m+1$) and points $y\in\ell$. Since a line $\ell$ that is parallel to the
$(m+1)$-st direction is selected with probability $1/(m+1)$, this implies that

$\operatorname*{\mathbb{E}}_{(u,x)\in{[n]}^{m}\times[n]}\sum_{f\in\mathcal{C}}\tau\left(B^{u}_{f}\,A^{u,x}_{[a:a\neq
f(x)]}\right)\leq(m+1)\varepsilon\;.$ (84)

Define measurement $\\{B^{u,x}_{a}\\}$ as

$B^{u,x}_{a}=B^{u}_{[f\mapsto f(x)\mid a]}\;.$

Then Eq. 84 can be also written as

$\operatorname*{\mathbb{E}}_{(u,x)\in{[n]}^{m}\times[n]}\sum_{a,b:a\neq
b}\tau\left(B^{u,x}_{b}A^{u,x}_{a}\right)\leq(m+1)\varepsilon\;.$ (85)

By Proposition 2.5 this implies that on average over
$(u,x)\in{[n]}^{m}\times[n]$,

$B^{u,x}_{a}\approx_{\sqrt{2(m+1)\varepsilon}}A^{u,x}_{a}\;.$ (86)

We first show that the $\\{H_{h}\\}$ submeasurement and the $\\{B^{u}_{f}\\}$
measurements are consistent.

######  Lemma 6.5.

Let
$\nu_{3}=t\cdot\left(t\cdot\nu_{2}+\sqrt{\zeta+\sqrt{2(m+1)\varepsilon}}\right)$.
On average over $u$ sampled uniformly from ${[n]}^{m}$, we have

$H_{[h\mapsto h|_{u}\mid f]}\simeq_{\nu_{3}}B^{u}_{f}$

where the answer summation is over $f\in\mathcal{C}$.

###### Proof.

Let $\mathcal{D}$ be the uniform distribution on $\mathsf{distinct}([n],t)$
and $\mathcal{D}_{i}$ be the marginal distribution of $\mathcal{D}$ on $i$
coordinates.

$\displaystyle\operatorname*{\mathbb{E}}_{u}\sum_{f^{\prime}\neq
f}\tau\left(H_{[h\mapsto h|_{u}\mid f^{\prime}]}\,B^{u}_{f}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{\begin{subarray}{c}h\in\mathcal{C}^{\otimes(m+1)},f\in\mathcal{C}\\\
h|_{u}\neq f\end{subarray}}\tau\left(H_{h}\,B^{u}_{f}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathcal{D}}\sum_{\begin{subarray}{c}h\in\mathcal{C}^{\otimes(m+1)},f\in\mathcal{C}:\\\
h|_{u}\neq
f\end{subarray}}\tau\left(H_{h}^{x_{1},\ldots,x_{t}}\,B^{u}_{f}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathcal{D}}\sum_{\begin{subarray}{c}h,f:\\\
\exists\,i:h(u,x_{i})\neq
f(x_{i})\end{subarray}}\tau\left(H_{h}^{x_{1},\ldots,x_{t}}\,B^{u}_{f}\right)$
$\displaystyle\leq\sum_{i=1}^{t}\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathcal{D}}\sum_{\begin{subarray}{c}h,f:\\\
h(u,x_{i})\neq
f(x_{i})\end{subarray}}\tau\left(H_{h}^{x_{1},\ldots,x_{t}}\,B^{u}_{f}\right)$

For any fixed $i\in[t]$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathcal{D}}\sum_{\begin{subarray}{c}h,f:\\\
h(u,x_{i})\neq
f(x_{i})\end{subarray}}\tau\left(H_{h}^{x_{1},\ldots,x_{t}}\,B^{u}_{f}\right)$
$\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathcal{D}}\sum_{\begin{subarray}{c}h,f:\\\
h(u,x_{i})\neq
f(x_{i})\end{subarray}}\tau\left(G^{x_{1}}_{h|_{x_{1}}}\cdots\,G^{x_{t}}_{h|_{x_{t}}}\cdots\,G^{x_{1}}_{h|_{x_{1}}}\cdot
B^{u}_{f}\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathcal{D}}\sum_{\begin{subarray}{c}g_{1},\ldots,g_{t},f:\\\
g_{i}(u)\neq f(x_{i})\end{subarray}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{1}}_{g_{1}}\cdot B^{u}_{f}\right)$
$\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{i})\sim\mathcal{D}_{i}}\sum_{g_{1},\ldots,g_{i}}\tau\left(B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\cdot G^{x_{1}}_{g_{1}}\cdots
G^{x_{i}}_{g_{i}}\cdot\Bigl{(}G^{x_{i}}_{g_{i}}\cdot
G^{x_{i-1}}_{g_{i-1}}\cdots G^{x_{1}}_{g_{1}}\Bigr{)}\right)$
$\displaystyle\approx_{i\cdot\nu_{2}\;}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{i})\sim\mathcal{D}_{i}}\sum_{g_{1},\ldots,g_{i}}\tau\left(B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\cdot G^{x_{1}}_{g_{1}}\cdots
G^{x_{i}}_{g_{i}}\cdot\Bigl{(}G^{x_{i-1}}_{g_{i-1}}\cdots
G^{x_{1}}_{g_{1}}\cdot G^{x_{i}}_{g_{i}}\Bigr{)}\right)$ (87)

where the inequality comes from the fact that $G^{x_{i+1}},\ldots,G^{x_{t}}$
are submeasurements, and the last approximation follows from Propositions 2.7
and 2.11 and the approximate commutativity of the $G^{x}$ measurements (Lemma
6.3). Continuing on, we can use Cauchy-Schwarz to bound (87) by

(87)
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{i})\sim\mathcal{D}_{i}}\sum_{g_{1},\ldots,g_{i}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{i}}_{g_{i}}\cdots G^{x_{1}}_{g_{1}}\right)}$
$\displaystyle\qquad\qquad\cdot\sqrt{\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{i})\sim\mathcal{D}_{i}}\sum_{g_{1},\ldots,g_{i}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{i-1}}_{g_{i-1}}\cdots G^{x_{1}}_{g_{1}}\cdot
G^{x_{i}}_{g_{i}}\cdot{\bigl{(}B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\bigr{)}}^{2}\cdot G^{x_{i}}_{g_{i}}\right)}$
$\displaystyle\leq\sqrt{1}\cdot\sqrt{\operatorname*{\mathbb{E}}_{u,x_{i}}\sum_{g_{i}}\tau\left(G^{x_{i}}_{g_{i}}\,B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\right)}$

where in the last inequality we used the fact that the $G^{x}$ is projective
and ${\bigl{(}B^{u}_{[f:f(x_{i})\neq g_{i}(u)]}\bigr{)}}^{2}\leq
B^{u}_{[f:f(x_{i})\neq g_{i}(u)]}$ for all $u$. Notice that

$\displaystyle\operatorname*{\mathbb{E}}_{u,x_{i}}\sum_{g_{i}}\tau\left(G^{x_{i}}_{g_{i}}B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{u,x}\sum_{a,b:a\neq
b}\tau\left(G^{u,x}_{a}B^{u,x}_{b}\right)$
$\displaystyle\approx_{\sqrt{2(m+1)\varepsilon}}\operatorname*{\mathbb{E}}_{u,x}\sum_{a,b:a\neq
b}\tau\left(G^{u,x}_{a}A^{u,x}_{b}\right)$ $\displaystyle\leq\zeta\;.$

where the approximation in the second line follows from Proposition 2.7 and
Eq. 86. Putting everything together, this implies that

$\operatorname*{\mathbb{E}}_{u}\sum_{\begin{subarray}{c}h\in\mathcal{C}^{\otimes(m+1)},f\in\mathcal{C}\\\
h|_{u}\neq f\end{subarray}}\tau\left(H_{h}\,B^{u}_{f}\right)\leq\nu_{3},$

for $\nu_{3}$ given in the statement of the lemma. ∎

Next we argue that $H$ is consistent with the points measurements $A$.

######  Lemma 6.6.

Let $\nu_{4}=\nu_{3}+\sqrt{2(m+1)\varepsilon}$. On average over $(u,x)$
sampled uniformly from ${[n]}^{m}\times[n]$, we have

$H_{[h\mapsto h(u,x)\mid a]}\simeq_{\nu_{4}}A^{u,x}_{a}\;.$

where the answer summation is over $a\in\Sigma$.

###### Proof.

Define $H^{u,x}_{a}=H_{[h\mapsto h(u,x)|a]}$. We have

$\begin{split}\operatorname*{\mathbb{E}}_{u,x}\sum_{\begin{subarray}{c}a,b:\\\
a\neq
b\end{subarray}}\tau\left(H^{u,x}_{a}B^{u,x}_{b}\right)&=\operatorname*{\mathbb{E}}_{u,x}\sum_{\begin{subarray}{c}a,b:\\\
a\neq
b\end{subarray}}\tau\left(\biggl{(}\sum_{h:h(u,x)=a}H_{h}\biggr{)}\biggl{(}\sum_{f:f(x)=b}B^{u}_{f}\biggr{)}\right)\\\
&=\operatorname*{\mathbb{E}}_{u,x}\sum_{\begin{subarray}{c}h,f:\\\ h(u,x)\neq
f(x)\end{subarray}}\tau\left(H_{h}B^{u}_{f}\right)\\\
&\leq\operatorname*{\mathbb{E}}_{u,x}\sum_{\begin{subarray}{c}h,f\end{subarray}:h|_{u}\neq
f}\tau\left(H_{h}B^{u}_{f}\right),\end{split}$

which is at most $\nu_{3}$ by Lemma 6.5. That is

$H^{u,x}_{a}\simeq_{\nu_{3}}B^{u,x}_{a}.$

Applying Proposition 2.9 to the above and Eq. 86 proves that

$H^{u,x}_{a}\simeq_{\nu_{4}}A^{u,x}_{a},$

for $\nu_{4}=\nu_{3}+\sqrt{2(m+1)\varepsilon}$.

∎

####  6.3.2 Bounding the completeness of $H$

We now bound the completeness of $H$. Let
$G=\operatorname*{\mathbb{E}}_{x}G^{x}$ where $G^{x}=\sum_{g}G^{x}_{g}$.

######  Lemma 6.7.

Let $\nu_{5}=\sqrt{\nu_{4}}+\sqrt{\zeta}$. Then

$\tau(H)\approx_{\nu_{5}}\tau(HG)~{}.$

###### Proof.

We bound the difference

$\displaystyle\tau\left(H(\mathbf{1}-G)\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{h}\tau\left(H_{h}(\mathbf{1}-G^{x})\right)$
$\displaystyle\approx_{\sqrt{\nu_{4}}\;\;}\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left(H_{h}A^{u,x}_{h(u,x)}(\mathbf{1}-G^{x})\right).$
(88)

To see the approximation in the second line, it suffices to bound the
difference as

$\displaystyle\Big{|}\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left(H_{h}\bigl{(}\mathbf{1}-A^{u,x}_{h(u,x)}\bigr{)}(\mathbf{1}-G^{x})\right)\Big{|}$
$\displaystyle\leq\;\;$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left(H_{h}\bigl{(}\mathbf{1}-A^{u,x}_{h(u,x)}\bigr{)}^{2}\right)}\cdot\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left(H_{h}(\mathbf{1}-G^{x})^{2}\right)}$
Cauchy-Schwarz $\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{a}\tau\left(H_{[h:h(u,x)\neq
a]}A^{u,x}_{a}\right)}\cdot\sqrt{1}$ $\displaystyle\leq$
$\displaystyle\sqrt{\nu_{4}}$

where the third line follows from the projectivity of the points measurements,
$G^{x}\leq\mathbf{1}$, and $\\{H_{h}\\}$ is a submeasurement. Continuing the
proof, we bound the absolute value of Eq. 88 as

$\displaystyle\left|\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left(H_{h}A^{u,x}_{h(u,x)}(\mathbf{1}-G^{x})\right)\right|$
$\displaystyle\leq\;\;$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left(H_{h}\right)}\cdot\sqrt{\operatorname*{\mathbb{E}}_{u,x}\sum_{h}\tau\left((\mathbf{1}-G^{x}){\bigl{(}A^{u,x}_{h(u,x)}\bigr{)}}^{2}(\mathbf{1}-G^{x})H_{h}\right)}$
Cauchy-Schwarz $\displaystyle\leq$
$\displaystyle\sqrt{1}\cdot\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{h}\tau\left((\mathbf{1}-G^{x})H_{h}(\mathbf{1}-G^{x})\operatorname*{\mathbb{E}}_{u}A^{u,x}_{h(u,x)}\right)}$
$\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{h}\psi^{x}((\mathbf{1}-G^{x})\,H_{h}\,(\mathbf{1}-G^{x}))}$
Assumption 3 of Lemma 4.3 $\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\psi^{x}(\mathbf{1}-G^{x})}$
$\psi^{x}$ is positive $\displaystyle\leq$ $\displaystyle\sqrt{\zeta}$
$\displaystyle\text{Assumption~{}\ref{enu:pasting-boundedness} of
\lx@cref{creftype~refnum}{lem:pasting}}.$

∎

We now argue that $HG$ can be approximated by $G^{t+1}$.

######  Lemma 6.8.

Let $\nu_{6}=2t^{2}(\nu_{2}+n^{-1})$. Then

$\tau(H)\approx_{\nu_{6}}\tau(G^{t})\qquad\text{and}\qquad\tau(HG)\approx_{\nu_{6}}\tau(G^{t+1})~{}.$

###### Proof.

We prove the first approximation.

$\displaystyle\tau\left(H\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathsf{distinct}([n],t)}\sum_{h\in\mathcal{C}^{\otimes(m+1)}}\tau\left(G^{x_{1}}_{h|_{x_{1}}}\cdots
G^{x_{t}}_{h|_{x_{t}}}\cdots G^{x_{1}}_{h|_{x_{1}}}\right)$ (89)
$\displaystyle=\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim\mathsf{distinct}([n],t)}\sum_{g_{1},\ldots,g_{t}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{1}}_{g_{1}}\right)$ (90)
$\displaystyle\approx_{t^{2}/n}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim[n]^{t}}\sum_{g_{1},\ldots,g_{t}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{1}}_{g_{1}}\right),$ (91)

where in going from the first to the second line we used Proposition 2.20
(which uses the interpolability of $\mathcal{C}$) to rewrite the sum over $h$
to sums over $t$-tuples of polynomials $g_{1},\dots,g_{t}$; and in going from
the second to the third line, we used Proposition 6.4 and that the absolute
value of

$\sum_{g_{1},\ldots,g_{t}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{1}}_{g_{1}}\right)$

for all $x_{1},\ldots,x_{t}$ is at most $1$. Continuing, we have

(91) $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim[n]^{t}}\sum_{g_{1},\ldots,g_{t}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{2}}_{g_{2}}\right)$ Cyclicity of the trace
$\displaystyle\approx_{(2t-5)\nu_{2}\;}$
$\displaystyle\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim[n]^{t}}\sum_{g_{1},\ldots,g_{t}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\cdots G^{x_{3}}_{g_{3}}\right)$

In other words, the right-most $G^{x_{2}}_{g_{2}}$ has been commuted leftwards
to where the left occurence of $G^{x_{2}}_{g_{2}}$ is; this requires $2t-5$
(approximate) commutations. This follows from Proposition 2.11, the
approximate commutativity of the $G$’s, and the projectivity of the $G$’s. We
can then commute the right-hand $G^{x_{3}}_{g_{3}}$ to the left $2t-7$ places,
and so on. Adding up all the errors together, we get that

$\tau(H)\approx_{t^{2}(\nu_{2}+n^{-1})}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{t})\sim[n]^{t}}\sum_{g_{1},\ldots,g_{t}}\tau\left(G^{x_{1}}_{g_{1}}\cdots
G^{x_{t}}_{g_{t}}\right)=\tau\left(G^{t}\right)$

where we used that $\sum_{j=2}^{t-1}(2(t-j)-1)\leq t^{2}$.

The second approximation in the Lemma statement follows from a nearly
identical argument. ∎

######  Lemma 6.9.

Let $\nu_{7}=\nu_{6}+2(\nu_{5}+2\nu_{6})^{1/t}$. Then

$\tau(H)\geq\tau(G)-\nu_{7}~{}.$

###### Proof.

Since for all real numbers $0\leq\lambda\leq 1$ and integer $t\geq 2$, we have

$\lambda(1-\lambda^{t-1})\leq 2\Big{(}\lambda^{t}(1-\lambda)\Big{)}^{1/t}$

we have the operator inequality

$G-G^{t}\leq 2\Big{(}G^{t}(\mathbf{1}-G)\Big{)}^{1/t}\;.$

and thus applying $\tau\left(\cdot\right)$ on both sides, we have

$\tau(G-G^{t})\leq
2\tau\left(\Big{(}G^{t}(\mathbf{1}-G)\Big{)}^{1/t}\right)\leq
2{\Bigl{(}\tau\left(G^{t}-G^{t+1}\right)\Bigr{)}}^{1/t}$

where we used that $\tau\left(X^{1/t}\right)\leq\tau\left(X\right)^{1/t}$ for
all positive operators $X$ (this is a consequence of Hölder’s inequality, see
[PX03]). This implies that

$|\tau(H)-\tau(G)|\leq\tau(G-G^{t})+|\tau(H-G^{t})|\leq\tau(G-G^{t})+\nu_{6}$

and

$\tau(G-G^{t})\leq
2\Big{(}|\tau\left(G^{t}-H\right)|+|\tau\left(H-HG\right)|+\left|\tau\left(HG-G^{t+1}\right)\right|\Big{)}^{1/t}\leq
2(\nu_{6}+\nu_{5}+\nu_{6})^{1/t}$

where we used Lemmas 6.7 and 6.8. Put altogether we have

$|\tau(H)-\tau(G)|\leq\nu_{6}+2(\nu_{5}+2\nu_{6})^{1/t}.$

∎

####  6.3.3 Putting everything together

We now finish the proof of Lemma 4.3, with the error function $\mu$ specified
in (83) instead of (5). (The claimed bound (5) is shown in the next section.)
Let $H^{\prime}=\\{H^{\prime}_{h}\\}$ denote the completion of $H=\\{H_{h}\\}$
as follows: letting $h^{*}$ be the lexicographically first element of
$\mathcal{C}^{\otimes(m+1)}$, we set
$H^{\prime}_{h^{*}}=H_{h^{*}}+(\mathbf{1}-H)$. Then for all $h\neq h^{*}$,
define $H_{h}^{\prime}=H_{h}$. By construction $H^{\prime}$ is a perfectly
complete measurement. We now evaluate its consistency with $A$:

$\displaystyle\operatorname*{\mathbb{E}}_{u,x}\sum_{h,a:h(u,x)\neq
a}\tau\left(H^{\prime}_{h}\,A^{u,x}_{a}\right)$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{u,x}\sum_{h,a:h(u,x)\neq
a}\tau\left(H_{h}\,A^{u,x}_{a}\right)+\sum_{a}\tau\left((\mathbf{1}-H)A^{u,x}_{a}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{u,x}\sum_{h,a:h(u,x)\neq
a}\tau\left(H_{h}\,A^{u,x}_{a}\right)+\tau\left((\mathbf{1}-H)\right)$
$\displaystyle\leq\nu_{4}+(1-\tau\left(G\right))+\nu_{7}\;.$

Letting $\mu=\kappa+\nu_{4}+\nu_{7}$ where $\kappa=\tau(G)$, we get that
$H^{\prime}$ satisfies the conclusions stated in Lemma 4.3, once we verify
that $\mu$ has the correct asymptotic dependence on
$m,t,\varepsilon,\delta,\zeta,n,t$.

Without loss of generality, we assume $\varepsilon\leq 1/(m+1)$, $\delta\leq
1$, $\zeta\leq 1$ as otherwise the lemma is trivial. Recall also that by
Proposition 2.18, $\gamma_{m}\leq(mt)/n$. Under these conditions, we have

$\displaystyle\nu_{1}$
$\displaystyle=8(\sqrt{\zeta}+\sqrt{(m+1)\delta})=\mathrm{poly}(m)\cdot\mathrm{poly}(\delta,\zeta)$
$\displaystyle\nu_{2}$
$\displaystyle=4(\gamma_{m}+\nu_{1})=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\delta,\zeta,n^{-1}\right)$
$\displaystyle\nu_{3}$
$\displaystyle=t\left(t\nu_{2}+\sqrt{\zeta+\sqrt{2(m+1)\varepsilon}}\right)=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)$
$\displaystyle\nu_{4}$
$\displaystyle=\nu_{3}+\sqrt{2(m+1)\varepsilon}=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)$
$\displaystyle\nu_{5}$
$\displaystyle=\sqrt{\nu_{4}}+\sqrt{\zeta}=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)$
$\displaystyle\nu_{6}$
$\displaystyle=2t^{2}\left(v_{2}+n^{-1}\right)=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)$
$\displaystyle\nu_{7}$ $\displaystyle=\nu_{6}+2{(\nu_{5}+2\nu_{6})}^{1/t}$
$\displaystyle=\mathrm{poly}(m,t)\cdot\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)+\left(\mathrm{poly}(m,t)\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)\right)^{\frac{1}{t}}$
$\displaystyle=\mathrm{poly}(m,t)\cdot\left(\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)\right)^{\frac{1}{t}}.$

Therefore,
$\mu=\kappa+\mathrm{poly}(m,t)\cdot\left(\mathrm{poly}\left(\varepsilon,\delta,\zeta,n^{-1}\right)\right)^{1/t}$
as required.

###  6.4 Pasting the $G$’s together: Method 2

The second construction of $H=\\{H_{h}\\}$ is designed to circumvent the
problem of the first construction, which is that its soundness has a rather
poor dependence on the parameter $t$. Before describing the construction, we
need the following definitions.

######  Definition 6.10 ($G$’s incomplete part).

For each $x\in[n]$ we write $G^{x}=\sum_{g}G^{x}_{g}$ and
$G^{x}_{\bot}=\mathbf{1}-G^{x}$ for the “complete” and “incomplete” parts of
$G^{x}$ respectively. Let
$\widehat{G}=\\{\widehat{G}^{x}_{g}\\}_{g\in\mathcal{C}^{\otimes
m}\cup\\{\bot\\}}$ be the projective measurement defined as

$\widehat{G}^{x}_{g}=\left\\{\begin{array}[]{rl}G^{x}_{g}&\text{if
}g\in\mathcal{C}^{\otimes m},\\\ G^{x}_{\bot}&\text{if
}g=\bot.\end{array}\right.$

For succinctness we denote $\mathcal{C}^{+}=\mathcal{C}^{\otimes
m}\cup\\{\bot\\}$, leaving the parameter $m$ implicit.

######  Definition 6.11 (Types).

A type $\tau$ is an element of $\\{0,1\\}^{k}$ for some integer $k$. We write
$|\tau|=\tau_{1}+\cdots+\tau_{k}$ for the Hamming weight of $\tau$. We often
associate $\tau$ with the set $\\{i:\tau_{i}=1\\}$ and write $i\in\tau$ if
$\tau_{i}=1$.

Suppose that the measurement $\widehat{G}$ is performed some $k\geq 1$ times
in succession, generating the outcomes $g_{1},\ldots,g_{k}$. Let us write
$\tau\in\\{0,1\\}^{k}$ for the “type” of these outcomes, where

$\tau_{i}=\left\\{\begin{array}[]{rl}1&\text{if $g_{i}\in\mathcal{C}^{\otimes
m}$}\;,\\\ 0&\text{if $g_{i}=\bot$\;.}\end{array}\right.$

Whenever $\tau\geq t$, assuming that the $g_{i}$ are not inconsistent using
Proposition 2.19 we can interpolate them to produce an
$h\in\mathcal{C}^{\otimes(m+1)}$. Hence, we would like to understand the
probability that $|\tau|\geq t$ and ensure that it is as large as possible.
The probability that $\widehat{G}$ returns a $g\in\mathcal{C}^{\otimes m}$ is
equal to the completeness of $G$, which is $1-\kappa$. This tells us that the
probability that $\tau_{1}=1$ is $1-\kappa$. We might naively expect that the
same holds for the other $\tau_{i}$ as well. We might also naively expect that
the $\tau_{i}$ are independent. These two assumptions should not be expected
to hold in general, as they ignore correlations between the measurements.
However, if we make these assumptions, then we at least have a simple toy
model for the measurement outcomes: $\tau\sim\mathrm{Binomial}(k,1-\kappa)$.

In this toy model, we expect $|\tau|\approx k\cdot(1-\kappa)$ on average. This
was the limitation of the first construction: if $k=t$ and $\kappa$ is
reasonably large (say, on the order of $1/t$), then we don’t expect $|\tau|$
to be larger than $t$ with high probability, and so we can’t interpolate to
produce a global codeword. This suggests an alternative strategy: choose $k$
large enough so that $k\cdot(1-\kappa)\gg t$. In fact, as we are aiming for
$H$ to have completeness close to $1-\kappa$, we should choose $k$ so large
that $|\tau|\geq t$ with probability roughly $1-\kappa$. On the other hand, if
we set $k$ _too_ large, then we increase the risk that the $k$ outcomes
$g_{1},\ldots,g_{k}$ are inconsistent with each other, which is an additional
source of error.

This “naive analysis” motivates our second construction of $H$, which is
stated below. We will show that the naive analysis, in which we treat $\tau$
as a binomial random variable and bound $|\tau|$ using a Chernoff bound, can
be formalized.

######  Definition 6.12 (The pasted measurement).

Let $k\geq t$ be an integer.

  1. 1.

(Pasting): Let $x_{1},\ldots,x_{k}\in[n]$. Define initial “sandwiched”
measurement operators as follows:

$\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}\,=\,\widehat{G}^{x_{1}}_{g_{1}}\cdot\widehat{G}^{x_{2}}_{g_{2}}\cdots\widehat{G}^{x_{k}}_{g_{k}}\cdots\widehat{G}^{x_{2}}_{g_{2}}\cdot\widehat{G}^{x_{1}}_{g_{1}}\;.$

  2. 2.

(Interpolation): Let $(x_{1},\ldots,x_{k})\in\mathsf{distinct}([n],k)$. For
any $w\in\\{0,1\\}^{k}$ and $h\in\mathcal{C}^{\otimes(m+1)}$, define
$h_{w}=(g_{1},\ldots,g_{k})\in(\mathcal{C}^{+})^{k}$ as $g_{i}=\bot$ if
$w_{i}=0$ and $g_{i}=h|_{x_{i}}$ otherwise. Define the interpolated
measurement

$H^{x_{1},\ldots,x_{k}}_{h}\,=\,\sum_{w:|w|\geq
t}\widehat{H}^{x_{1},\ldots,x_{k}}_{h_{w}}\;.$

  3. 3.

(Averaging): Define

$H_{h}\,=\,\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{k})\sim\mathsf{distinct}([n],k)}H^{x_{1},\ldots,x_{k}}_{h}\;.$

To analyze this construction, we first need to show that $\widehat{G}$
commutes with itself. This is shown in Section 6.4.1, using that a similar
property holds for $G$. Using this in Section 6.4.2 we prove that
$\widehat{H}$ is consistent with $B$, which we use to prove that $H$ is
consistent with $A$. Finally, we analyze the completeness of $H$ in Section
6.4.3.

####  6.4.1 Commutativity of $\widehat{G}$

In this section we show that $\widehat{G}$ commutes with itself. As we already
know this holds for the sub-measurement $G$, our task essentially reduces to
showing that this holds for $G$’s incomplete part, i.e. $G_{\perp}$. As it is
more convenient to work with $G=\mathbf{1}-G_{\perp}$ rather than $G_{\perp}$,
we will first show that these properties hold for $G$; the fact that they also
hold for $G_{\perp}$ will then follow as an immediate corollary.

######  Lemma 6.13 (Commutativity with $G_{g}^{x}$ implies commutativity with
$G^{x}$).

For all $y\in[n]$ let $M^{y}=\\{M^{y}_{o}\\}$ be a projective sub-measurement
with outcomes in some set $\mathcal{O}$ and let $\chi>0$. Suppose that

$G^{x}_{g}M^{y}_{o}\,\approx_{\chi}\,M^{y}_{o}G^{x}_{g}\;,$ (92)

on average over independent and uniformly random $x,y\in[n]$. Then

$G^{x}M^{y}_{o}\,\approx_{\sqrt{3\chi}}\,M^{y}_{o}G^{x}\;.$

###### Proof.

We first show that

$\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\big{(}G^{x}_{g}M^{y}_{o}G^{x}M^{y}_{o}\big{)}\,\approx_{{\chi}}\,\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\big{(}G^{x}_{g}M^{y}_{o}G^{x}_{g}M^{y}_{o}\big{)}$
(93)

(note that on the left hand side, the third factor is $G^{x}$ instead of
$G^{x}_{g}$). To show this, we take the difference to obtain

$\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\Big{(}G^{x}_{g}M^{y}_{o}\big{(}G^{x}-G^{x}_{g}\big{)}M^{y}_{o}\Big{)}=\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\Big{(}G^{x}_{g}G^{x}_{g}M^{y}_{o}\big{(}G^{x}-G^{x}_{g}\big{)}M^{y}_{o}\Big{)}$
(94)

where we used the fact that $\\{G^{x}_{g}\\}$ is projective. Notice that

$\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\big{(}G^{x}_{g}M^{y}_{o}G^{x}_{g}(G^{x}-G^{x}_{g})M^{y}_{o}\big{)}\,=\,0$
(95)

using again the fact that $\\{G^{x}_{g}\\}$ is projective. Thus to prove (93)
it suffices to show that the quantity in (94) is $\chi$-close to the quantity
in (95). Taking the difference, we get

$\displaystyle\Big{|}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}$
$\displaystyle\tau\big{(}G^{x}_{g}(G^{x}_{g}M^{y}_{o}-M^{y}_{o}G^{x}_{g})(G^{x}-G^{x}_{g})M^{y}_{o}\big{)}\Big{|}$
$\displaystyle=\Big{|}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\big{(}(G^{x}-G^{x}_{g})M^{y}_{o}G^{x}_{g}(G^{x}_{g}M^{y}_{o}-M^{y}_{o}G^{x}_{g})\big{)}\Big{|}$
$\displaystyle\leq\Big{(}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\big{(}(G^{x}-G^{x}_{g})M^{y}_{o}G^{x}_{g}M^{y}_{o}(G^{x}-G^{x}_{g})\big{)}\Big{)}^{1/2}\Big{(}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\big{(}(G^{x}_{g}M^{y}_{o}-M^{y}_{o}G^{x}_{g})^{2}\big{)}\Big{)}^{1/2}$
$\displaystyle\leq{\chi}\;,$ (96)

where the second line follows from the cyclicity of the trace, the third line
uses Cauchy-Schwarz and the fourth bounds the first term by $1$ using
$\|G^{x}-G^{x}_{g}\|\leq 1$ for all $x,g$, cyclicity of the trace and
$\\{G^{x}\\}$, $\\{M^{y}\\}$ sub-measurements, and the second term by $\chi$
using (92).

To prove the lemma we expand

$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{o}\tau\big{(}(G^{x}M^{y}_{o}-M^{y}_{o}G^{x})^{2}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\sum_{o}\Big{(}2\,\tau\big{(}G^{x}M^{y}_{o}G^{x}M^{y}_{o}\big{)}-2\,\tau\big{(}G^{x}M^{y}_{o}\big{)}\Big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\Big{(}2\,\tau\big{(}G^{x}_{g}M^{y}_{o}G^{x}M^{y}_{o}\big{)}-2\,\tau\big{(}G^{x}_{g}M^{y}_{o}\big{)}\Big{)}$
$\displaystyle\approx_{2\chi}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\Big{(}2\,\tau\big{(}G^{x}_{g}M^{y}_{o}G^{x}_{g}M^{y}_{o}\big{)}-2\,\tau\big{(}G^{x}_{g}M^{y}_{o}\big{)}\Big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\sum_{g,o}\tau\Big{(}\big{(}G^{x}_{g}M^{y}_{o}-M^{y}_{o}G^{x}_{g}\big{)}^{2}\Big{)}$
$\displaystyle\leq\chi^{2}\;.$

The third line follows from (96), and the last line follows again from (92). ∎

######  Corollary 6.14 (Commutativity of $G$’s).

Recall the error parameter $\nu_{2}$ from Lemma 6.3. Then

$\operatorname*{\mathbb{E}}_{x,y}\tau\big{(}(G^{x}G^{y}-G^{x}G^{y})^{2}\big{)}\leq
9\nu_{2}^{1/4}~{}.$

###### Proof.

We prove this via two applications of Lemma 6.13. First, by Lemma 6.3, we have
that

$G^{x}_{g}G^{y}_{h}\approx_{\nu_{2}}G^{y}_{h}G^{x}_{g}$

on average of $x,y\sim[n]$. By Lemma 6.13, we get that

$G^{x}G^{y}_{h}\approx_{3\sqrt{\nu_{2}}}G^{y}_{h}G^{x}~{}.$

By applying Lemma 6.13 again with the projective sub-measurement
$M^{x}=\\{G^{x}\\}$ with a single outcome, we get that

$G^{y}G^{x}\approx_{9\nu_{2}^{1/4}}G^{x}G^{y}~{}.$

∎

######  Corollary 6.15 (Commutativity of $\widehat{G}$).

Recall the error parameter $\nu_{2}$ from Lemma 6.3. Let
$\nu^{\prime}_{2}=27\nu_{2}^{1/4}$. Then

$\displaystyle\widehat{G}^{x}_{g}\widehat{G}^{y}_{h}$
$\displaystyle\approx_{\nu^{\prime}_{2}}\widehat{G}^{y}_{h}\widehat{G}^{x}_{g}\;.$
(97)

###### Proof.

We can write

$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{g,h\in\mathcal{C}^{\otimes
m}}\tau\big{(}(\widehat{G}^{x}_{g}\widehat{G}^{y}_{h}-\widehat{G}^{y}_{h}\widehat{G}^{x}_{g})^{2}\big{)}$
$\displaystyle=~{}\operatorname*{\mathbb{E}}_{x,y}\sum_{g,h\in\mathcal{C}^{\otimes
m}}\tau\big{(}(G^{x}_{g}G^{y}_{h}-G^{y}_{h}G^{x}_{g})^{2}\big{)}+\operatorname*{\mathbb{E}}_{x,y}\tau\big{(}(G^{x}_{\bot}G^{y}_{\bot}-G^{y}_{\bot}G^{x}_{\bot})^{2}\big{)}$
$\displaystyle+\operatorname*{\mathbb{E}}_{x,y}\sum_{g\in\mathcal{C}^{\otimes
m}}\tau\big{(}(G^{x}_{g}G^{y}_{\bot}-G^{y}_{\bot}G^{x}_{g})^{2}\big{)}+\operatorname*{\mathbb{E}}_{x,y}\sum_{h\in\mathcal{C}^{\otimes
m}}\tau\big{(}(G^{x}_{\bot}G^{y}_{h}-G^{y}_{h}G^{x}_{\bot})^{2}\big{)}~{}.$
(98)

We can bound the first term by $\nu_{2}^{2}$ by Lemma 6.3. We can bound the
second term by first writing

$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\tau\big{(}(G^{x}_{\bot}G^{y}_{\bot}-G^{y}_{\bot}G^{x}_{\bot})^{2}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\tau\big{(}((\mathbf{1}-G^{x})(\mathbf{1}-G^{y})-(\mathbf{1}-G^{y})(\mathbf{1}-G^{x}))^{2}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\tau\big{(}(G^{x}G^{y}-G^{y}G^{x})^{2}\big{)}$
$\displaystyle\leq 9^{2}\cdot\nu_{2}^{1/2}$

where the last line follows from Corollary 6.14. Similarly, we can bound the
third and fourth terms of (98) by

$\displaystyle\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\tau\big{(}(G^{x}_{g}G^{y}_{\bot}-G^{y}_{\bot}G^{x}_{g})^{2}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\tau\big{(}(G^{x}_{g}(\mathbf{1}-G^{y})-(\mathbf{1}-G^{y})G^{x}_{g})^{2}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y}\sum_{g}\tau\big{(}(G^{x}_{g}G^{y}-G^{y}G^{x}_{g})^{2}\big{)}$
$\displaystyle\leq 9\nu_{2}$

where the last line follows from Lemma 6.3 and Lemma 6.13.

Putting everything together, this implies that we can upper bound (98) by
$\nu_{2}^{2}+9^{2}\nu_{2}^{1/2}+18\nu_{2}\leq 3\cdot 9^{2}\cdot\nu_{2}^{1/2}$.
The lemma follows. ∎

####  6.4.2 Consistency of $\widehat{H}$ and $H$ with $B$ and $A$

We use the same notation as in Section 6.3.1. The following lemma is analogous
to Lemma 6.5.

######  Lemma 6.16 (Consistency of $\widehat{H}$ with $B$).

Let
$\nu^{\prime\prime}_{3}=k\cdot\nu^{\prime}_{2}+(\zeta+(2(m+1)\varepsilon)^{1/2})^{1/2}$.
For any $1\leq i\leq k$,

$\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\dots,x_{k}}\sum_{a\neq\bot}\sum_{b\neq
a}\tau\big{(}\widehat{H}^{x_{1},\dots,x_{k}}_{[(g_{1},\dots,g_{k})\mapsto
g_{i}(u)\mid a]}B^{u}_{[f\mapsto f(x_{i})\mid
b]}\big{)}\,\leq\,\nu^{\prime\prime}_{3}$ (99)

where the expectation over $(x_{1},\ldots,x_{k})$ is over independently random
$x_{1},\ldots,x_{k}\sim[n]$.

###### Proof.

The proof follows closely that of Lemma 6.5. We have

$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\dots,g_{k}:g_{i}\neq\bot}\sum_{f:f(x_{i})\neq
g_{i}(u)}\tau\left(\widehat{H}_{g_{1},\ldots,g_{k}}^{x_{1},\ldots,x_{k}}\,B^{u}_{f}\right)$
$\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\dots,g_{k}:g_{i}\neq\bot}\sum_{f:f(x_{i})\neq
g_{i}(u)}\tau\left(\widehat{G}^{x_{1}}_{g_{1}}\cdots\widehat{G}^{x_{k}}_{g_{k}}\cdots\widehat{G}^{x_{1}}_{g_{1}}\cdot
B^{u}_{f}\right)$ $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{i}}\sum_{g_{1},\ldots,g_{i}:g_{i}\neq\bot}\tau\left(B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\cdot\widehat{G}^{x_{1}}_{g_{1}}\cdots\widehat{G}^{x_{i}}_{g_{i}}\cdot\Bigl{(}\widehat{G}^{x_{i}}_{g_{i}}\cdot\widehat{G}^{x_{i-1}}_{g_{i-1}}\cdots\widehat{G}^{x_{1}}_{g_{1}}\Bigr{)}\right)$
$\displaystyle\approx_{i\cdot\nu^{\prime}_{2}\;}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{i}}\sum_{g_{1},\ldots,g_{i}}\tau\left(B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\cdot\widehat{G}^{x_{1}}_{g_{1}}\cdots\widehat{G}^{x_{i}}_{g_{i}}\cdot\Bigl{(}\widehat{G}^{x_{i-1}}_{g_{i-1}}\cdots\widehat{G}^{x_{1}}_{g_{1}}\cdot\widehat{G}^{x_{i}}_{g_{i}}\Bigr{)}\right)$
(100)

where the last approximation follows from Propositions 2.7 and 2.11 and the
approximate commutativity of the $\widehat{G}^{x}$ measurements (Corollary
6.15). Continuing, we can use Cauchy-Schwarz to bound (100) by

(100)
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{i}}\sum_{g_{1},\ldots,g_{i}:g_{i}\neq\bot}\tau\left(\widehat{G}^{x_{1}}_{g_{1}}\cdots\widehat{G}^{x_{i}}_{g_{i}}\cdots\widehat{G}^{x_{1}}_{g_{1}}\right)}$
$\displaystyle\qquad\qquad\cdot\sqrt{\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{i}}\sum_{g_{1},\ldots,g_{i}:g_{i}\neq\bot}\tau\left(\widehat{G}^{x_{1}}_{g_{1}}\cdots\widehat{G}^{x_{i-1}}_{g_{i-1}}\cdots\widehat{G}^{x_{1}}_{g_{1}}\cdot\widehat{G}^{x_{i}}_{g_{i}}\cdot{\bigl{(}B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\bigr{)}}^{2}\cdot\widehat{G}^{x_{i}}_{g_{i}}\right)}$
$\displaystyle\leq\sqrt{1}\cdot\sqrt{\operatorname*{\mathbb{E}}_{u,x_{i}}\sum_{g_{i}:g_{i}\neq\bot}\tau\left(\widehat{G}^{x_{i}}_{g_{i}}\,B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\right)}\;,$

where in the last inequality we used the fact that $\widehat{G}^{x}$ is
projective and ${\bigl{(}B^{u}_{[f:f(x_{i})\neq g_{i}(u)]}\bigr{)}}^{2}\leq
B^{u}_{[f:f(x_{i})\neq g_{i}(u)]}$ for all $u$. Notice that

$\displaystyle\operatorname*{\mathbb{E}}_{u,x_{i}}\sum_{g_{i}:g_{i}\neq\bot}\tau\left(\widehat{G}^{x_{i}}_{g_{i}}B^{u}_{[f:f(x_{i})\neq
g_{i}(u)]}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{u,x}\sum_{a,b:a\neq
b}\tau\left(G^{u,x}_{a}B^{u,x}_{b}\right)$
$\displaystyle\approx_{\sqrt{2(m+1)\varepsilon}}\operatorname*{\mathbb{E}}_{u,x}\sum_{a,b:a\neq
b}\tau\left(G^{u,x}_{a}A^{u,x}_{b}\right)$ $\displaystyle\leq\zeta\;.$

where the approximation in the second line follows from Proposition 2.9 and
Eq. 86.∎

Next we move from $\widehat{H}$ to $H$.

######  Lemma 6.17 (Consistency of $H$ with $B$).

Let $\nu^{\prime}_{3}=k\nu^{\prime\prime}_{3}+k^{2}/n$ . Then

$H_{[h|_{u}=f]}\simeq_{\nu^{\prime}_{3}}B^{u}_{f}\;.$

###### Proof.

We have

$\displaystyle\operatorname*{\mathbb{E}}_{u}\sum_{f\neq f^{\prime}}$
$\displaystyle\tau\big{(}H_{[h\mapsto h|_{u}\mid f^{\prime}]}B^{u}_{f}\big{)}$
(101) $\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{h}\sum_{f\neq
h|_{u}}\tau\big{(}H_{h}B^{u}_{f}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{k})\sim\mathsf{distinct}([n],k)}\sum_{h}\sum_{f\neq
h|_{u}}\tau\big{(}H^{x_{1},\ldots,x_{k}}_{h}B^{u}_{f}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{k})\sim\mathsf{distinct}([n],k)}\sum_{h}\sum_{w:|w|\geq
t}\sum_{f\neq
h|_{u}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}$
(102)

where $g_{i}\in\mathcal{C}^{+}$ is defined to be $\bot$ if $w_{i}=0$, and
otherwise $g_{i}=h|_{x_{i}}$. Because $|w|\geq t$, there exist at least $t$
coordinates $i$ such that $g_{i}\neq\bot$ and hence $g_{i}=h|_{x_{i}}$. Since
$t\geq n-d+1$, using the distance property of $\mathcal{C}$ it follows that if
$f\neq h|_{u}$ then there must exist an $i$ such that $g_{i}\neq\bot$ and
$g_{i}(u)\neq f(x_{i})$. Thus

$\displaystyle\eqref{eq:keep-on-expandin}~{}=~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{k})\sim\mathsf{distinct}([n],k)}\sum_{h}\sum_{w:|w|\geq
t}\sum_{\begin{subarray}{c}f:\exists i:g_{i}\neq\bot,\\\ g_{i}(u)\neq
f(x_{i})\end{subarray}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}$
$\displaystyle\leq~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(x_{1},\ldots,x_{k})\sim\mathsf{distinct}([n],k)}\sum_{g_{1},\ldots,g_{k}}\sum_{\begin{subarray}{c}f:\exists
i:g_{i}\neq\bot,\\\ g_{i}(u)\neq
f(x_{i})\end{subarray}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\;.$
(103)

Using Proposition 6.4 (which allows us to switch from sampling
$(x_{1},\ldots,x_{k})\sim\mathsf{distinct}([n],k)$ to sampling
$x_{1},\ldots,x_{k}$ independently from $[n]$) and the fact that
$\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}$
is nonnegative and, when summed over $g_{1},\ldots,g_{k}$ and $f$, is at most
$1$, we have that Equation 103 is $(k^{2}/n)$-close to

$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\ldots,g_{k}}\sum_{\begin{subarray}{c}f:\exists
i:g_{i}\neq\bot,\\\ g_{i}(u)\neq
f(x_{i})\end{subarray}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}$
$\displaystyle\leq~{}$
$\displaystyle\sum_{i}\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\ldots,g_{k}}\sum_{\begin{subarray}{c}f:g_{i}\neq\bot,\\\
g_{i}(u)\neq
f(x_{i})\end{subarray}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}$
(by the union bound) $\displaystyle=~{}$
$\displaystyle\sum_{i}\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\ldots,g_{k}:g_{i}\neq\bot}\sum_{b\neq
g_{i}(u)}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{[f\mapsto
f(x_{i})\mid b]}\big{)}$ $\displaystyle\leq~{}$
$\displaystyle\sum_{i}\nu^{\prime\prime}_{3}$ (by Lemma 6.16)
$\displaystyle=~{}$ $\displaystyle k\cdot\nu^{\prime\prime}_{3}\;.$

This establishes the lemma. ∎

######  Corollary 6.18 (Consistency of $H$ with $A$).

Let $\nu^{\prime}_{4}=\nu^{\prime}_{3}+\sqrt{2(m+1)\varepsilon}$. Then on
average over $(u,x)\sim[n]^{m}\times[n]$,

$H_{[h\mapsto h(u,x)\mid a]}\simeq_{\nu^{\prime}_{4}}A^{u,x}_{a}\;.$

###### Proof.

Applying Proposition 2.4 to Lemma 6.17 we get that

$H_{[h\mapsto h(u,x)\mid a]}\simeq_{\nu^{\prime}_{3}}B^{u}_{[f\mapsto f(x)\mid
a]}\;.$ (104)

Using (86) together with Proposition 2.9 (with measurement “$A^{x}_{a}$” in
the Proposition being set to $B^{u}_{[f\mapsto f(x)\mid a]}$, measurement
“$B^{x}_{a}$” being set to $A^{x}_{a}$ and the submeasurement “$C^{x}_{a}$”
being set to $H_{[h\mapsto h(u,x)\mid a]}$) proves the lemma. ∎

####  6.4.3 Completeness of $H$

######  Definition 6.19.

Let $\tau\in\\{0,1\\}^{k}$ be a type. We define the following two subsets of
$(\mathcal{C}^{+})^{k}$.

  * •

We define $\mathsf{Outcomes}_{\tau}$ to be the set of tuples
$(g_{1},\ldots,g_{k})$ such that $g_{i}\in\mathcal{C}^{\otimes m}$ for each
$i\in\tau$ and $g_{i}=\bot$ for each $i\notin\tau$. This is the set of
possible outcomes of the measurement $\widehat{H}$ of type $\tau$.

  * •

Let $x_{1},\ldots,x_{k}\in[n]$. We define $\mathsf{Global}_{\tau}(x)$ to be
the subset of $\mathsf{Outcomes}_{\tau}$ containing only those tuples which
are consistent with a global codeword. In other words,
$(g_{1},\ldots,g_{k})\in\mathsf{Global}_{\tau}(x)$ iff there exists an
$h\in\mathcal{C}^{\otimes(m+1)}$ such that $g_{i}=h|_{x_{i}}$ for each
$i\in\tau$ (recall that $h|_{x_{i}}$ denotes the function
$h(\cdots,x_{i})\in\mathcal{C}^{\otimes m}$). Define

$\overline{\mathsf{Global}_{\tau}(x)}=\mathsf{Outcomes}_{\tau}\setminus\mathsf{Global}_{\tau}(x).$

This contains those tuples of type $\tau$ with no consistent global codeword.

######  Lemma 6.20.

Let
$\nu^{\prime}_{5}=2\frac{k^{2}}{n}+k\cdot\nu^{\prime\prime}_{3}+\gamma_{m}$ .
Let $x_{1},\ldots,x_{k}\sim[n]$ be sampled uniformly at random. Then

$\tau\big{(}H\big{)}\,\approx_{\nu^{\prime}_{5}}\,\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}\big{)}\;.$

###### Proof.

By definition,

$\displaystyle\tau\big{(}H\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{(y_{1},\ldots,y_{k})\sim\mathsf{distinct}([n],k)}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Global}_{\tau}(y)}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}\;.$
(105)

The sum in (105) is over $g_{1},\ldots,g_{k}$ which are consistent with a
global codeword. We show that the value of this sum remains largely unchanged
if we drop this condition. In particular, we claim that

$\eqref{eq:sum-restricted-to-global-
polynomial}\approx_{\frac{k^{2}}{n}+k\cdot\nu^{\prime\prime}_{3}+\gamma_{m}}\operatorname*{\mathbb{E}}_{(y_{1},\ldots,y_{k})\sim\mathsf{distinct}([n],k)}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}\;.$
(106)

To show this, we note that $\eqref{eq:remove-the-
restriction}\geq\eqref{eq:sum-restricted-to-global-polynomial}$. Hence, it
suffices to upper bound their difference.

$\displaystyle\eqref{eq:remove-the-restriction}-\eqref{eq:sum-restricted-to-
global-polynomial}$
$\displaystyle=\operatorname*{\mathbb{E}}_{(y_{1},\ldots,y_{k})\sim\mathsf{distinct}([n],k)}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(y_{1},\ldots,y_{k})\sim\mathsf{distinct}([n],k)}\sum_{\tau:|\tau|\geq
t}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\;,$
(107)

where in the second line we used that $B$ is a measurement. Next, we claim
that

$\eqref{eq:B-appears-out-of-thin-
air}\approx_{\frac{k^{2}}{n}+k\cdot\nu^{\prime\prime}_{3}}\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{\tau:|\tau|\geq
t}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\mathbb{I}[\forall
i\in\tau,f(y_{i})=g_{i}(u)].$ (108)

To show this, we note that $\eqref{eq:B-appears-out-of-thin-
air}\geq\eqref{eq:add-in-indicator-for-f-and-g}$. Thus, it suffices to upper
bound their difference $\eqref{eq:B-appears-out-of-thin-air}-\eqref{eq:add-in-
indicator-for-f-and-g}$. This is given by

$\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{(y_{1},\ldots,y_{k})\sim\mathsf{distinct}([n],k)}\sum_{\tau:|\tau|\geq
t}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\mathbb{I}[\exists
i\in\tau,f(y_{i})\neq g_{i}(u)]\;.$ (109)

Recall that $x_{1},\ldots,x_{k}\sim[n]$ are sampled independently and
uniformly at random. Using Proposition 6.4, Equation 109 is $(k^{2}/n)$-close
to

$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(x)}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\mathbb{I}[\exists
i\in\tau,f(x_{i})\neq g_{i}(u)]$ $\displaystyle\leq~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\mathbb{I}[\exists
i\in\tau,f(x_{i})\neq g_{i}(u)]$ $\displaystyle\leq~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\mathbb{I}[\exists
i\in\tau,f(x_{i})\neq g_{i}(u)]$ $\displaystyle\leq~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\Big{(}\sum_{i\in\tau}\mathbb{I}[f(x_{i})\neq
g_{i}(u)]\Big{)}$ $\displaystyle=~{}$
$\displaystyle\sum_{i}\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\ldots,g_{k}:g_{i}\neq\bot}\sum_{f:f(x_{i})\neq
g_{i}(u)}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}$
$\displaystyle=~{}$
$\displaystyle\sum_{i}\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{g_{1},\ldots,g_{k}:g_{i}\neq\bot}\sum_{a\neq
g_{i}(u)}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{[f(x_{i})=a]}\big{)}$
$\displaystyle\leq~{}$ $\displaystyle\sum_{i}\nu^{\prime\prime}_{3}$ (by Lemma
6.16) $\displaystyle=~{}$ $\displaystyle k\cdot\nu^{\prime\prime}_{3}.$

Returning to Equation 108, we introduce the notation

$\mathsf{Consistent}_{\tau}(g,y,u)=\left\\{\begin{array}[]{rl}1&\text{if
$\exists f$ such that $f(y_{i})=g_{i}(u)$ for all $i\in\tau$\;,}\\\
0&\text{otherwise\;.}\end{array}\right.$

Clearly, for any $f$,

$\mathbb{I}[\forall
i\in\tau,f(y_{i})=g_{i}(u)]\leq\mathbb{I}[\mathsf{Consistent}_{\tau}(g,y,u)]\;.$

As a result,

$\displaystyle\eqref{eq:add-in-indicator-for-f-and-g}\leq~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{\tau:|\tau|\geq
t}\sum_{f}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}B^{u}_{f}\big{)}\cdot\mathbb{I}[\mathsf{Consistent}_{\tau}(g,y,u)]$
$\displaystyle=~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\Big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\Big{(}\sum_{f}B^{u}_{f}\Big{)}\Big{)}\cdot\mathbb{I}[\mathsf{Consistent}_{\tau}(g,y,u)]$
$\displaystyle=~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{u}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}\cdot\mathbb{I}[\mathsf{Consistent}_{\tau}(g,y,u)]$
$\displaystyle=~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}\cdot\Pr_{u}\Big{(}\mathsf{Consistent}_{\tau}(g,y,u)\Big{)}.$
(110)

Let us now fix $(y_{1},\ldots,y_{k})\in\mathsf{distinct}([n],k)$, a type
$\tau$ such that $|\tau|\geq t$, and
$(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}$. Suppose without
loss of generality that $\tau_{1}=\cdots=\tau_{t}=1$, so that
$g_{1},\ldots,g_{t}\in\mathcal{C}^{\otimes m}$. Then by Proposition 2.20 there
is a unique $h^{*}\in\mathcal{C}^{\otimes(m+1)}$ which interpolates
$g_{1},\ldots,g_{t}$. In other words, for all $1\leq i\leq t$ and for all
$u\in[n]^{m}$,

$h^{*}(u,y_{i})=g_{i}(u).$

On the other hand, because
$(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}$, there exists an
$i^{*}\in\tau$ such that $g_{i^{*}}\neq(h^{*})|_{y_{i^{*}}}$. Hence,

$\Pr_{u}\Big{(}\mathsf{Consistent}_{\tau}(g,y,u)\Big{)}\leq\Pr_{u}\Big{(}g_{i^{*}}(u)=h^{*}(u,y_{i^{*}})\Big{)}=\Pr_{u}\Big{(}g_{i^{*}}(u)=(h^{*})|_{y_{i^{*}}}(u)\Big{)}\leq\Big{(}1-\frac{d^{m}}{n^{m}}\Big{)}\,=\,\gamma_{m}\;,$

by Proposition 2.18. As a result,

$\displaystyle\eqref{eq:consistent-indicator}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\overline{\mathsf{Global}_{\tau}(y)}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}\cdot\gamma_{m}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{\begin{subarray}{c}(y_{1},\ldots,y_{k})\\\
\quad\sim\mathsf{distinct}([n],k)\end{subarray}}\sum_{g_{1},\ldots,g_{k}}\tau\big{(}\widehat{H}^{y_{1},\ldots,y_{k}}_{g_{1},\ldots,g_{k}}\big{)}\cdot\gamma_{m}$
$\displaystyle=\gamma_{m}\;.$

This establishes Equation 106. Finally, Equation 106 is $(k^{2}/n)$-close to

$\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}\big{)}\;,$

as desired. ∎

######  Lemma 6.21.

Recall the error parameter $\nu^{\prime}_{2}$ from Corollary 6.15. Let
$\nu^{\prime}_{6}=2k^{2}\nu^{\prime}_{2}$. Let $x_{1},\ldots,x_{k}\sim[n]$ be
sampled uniformly at random. Then

$\operatorname*{\mathbb{E}}_{x_{1},\dots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\dots,x_{k}}_{g_{1},\dots,g_{k}}\big{)}\approx_{\nu^{\prime}_{6}}\sum_{i=t}^{k}\binom{k}{i}\tau\big{(}G^{i}(\mathbf{1}-G)^{k-i}\big{)}\;.$

###### Proof.

We begin by introducing some notation that we will use throughout the proof.
Let $\tau\in\\{0,1\\}^{k}$ be a type. Then we define

$\tau_{<\ell}=(\tau_{1},\ldots,\tau_{\ell-1})\in\\{0,1\\}^{\ell-1}\;,\quad\tau_{>\ell}=(\tau_{\ell+1},\ldots,\tau_{k})\in\\{0,1\\}^{k-\ell}\;,$

and we define $\tau_{\leq\ell}$ and $\tau_{\geq\ell}$ similarly. In addition,
given $(g_{1},\ldots,g_{k})\in(\mathcal{C}^{+})^{k}$, we define

$g_{<\ell}=(g_{1},\ldots,g_{\ell-1})\;,\qquad
g_{>\ell}=(g_{\ell+1},\ldots,g_{k})$

and we define $g_{\leq\ell}$ and $g_{\geq\ell}$ similarly. Using this
notation, we can write

$\widehat{H}^{x_{\geq\ell}}_{g_{\geq\ell}}=\widehat{H}^{x_{\ell},\ldots,x_{k}}_{g_{\ell},\ldots,g_{k}}\;.$

Next, we introduce the notation

$\widehat{G}^{x_{\geq\ell}}_{g_{\geq\ell}}=\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdots\widehat{G}^{x_{k}}_{g_{k}}\;.$

This satisfies the recurrence relation

$\widehat{G}^{x_{\geq\ell}}_{g_{\geq\ell}}=\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdot\widehat{G}^{x_{>\ell}}_{g_{>\ell}}\;.$
(111)

Furthermore, we can write

$\widehat{H}^{x_{\geq\ell}}_{g_{\geq\ell}}=(\widehat{G}^{x_{\geq\ell}}_{g_{\geq\ell}})\cdot(\widehat{G}^{x_{\geq\ell}}_{g_{\geq\ell}})^{\dagger}.$
(112)

To prove the lemma we show that for each $1\leq\ell\leq k$,

$\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau:|\tau|\geq
t}\sum_{g_{\geq\ell}\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}\widehat{H}^{x_{\geq\ell}}_{g_{\geq\ell}}\cdot(G^{|\tau_{<\ell}|}\cdot(\mathbf{1}-G)^{(\ell-1)-|\tau_{<\ell}|})\big{)}$
$\displaystyle\approx_{2k\nu^{\prime}_{2}}~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{x_{>\ell}}\sum_{\tau:|\tau|\geq
t}\sum_{g_{>\ell}\in\mathsf{Outcomes}_{\tau_{>\ell}}}\tau\big{(}\widehat{H}^{x_{>\ell}}_{g_{>\ell}}\cdot(G^{|\tau_{\leq\ell}|}\cdot(\mathbf{1}-G)^{\ell-|\tau_{\leq\ell}|})\big{)}\;.$
(113)

If we then repeatedly apply Equation 113 for $\ell=1,\ldots,k$, we derive

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1},\dots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\dots,x_{k}}_{g_{1},\dots,g_{k}}\big{)}$
$\displaystyle=~{}$ $\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq
1}}\sum_{\tau:|\tau|\geq t}\sum_{g_{\geq
1}\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{\geq 1}}_{g_{\geq
1}}\big{)}$ $\displaystyle\approx_{2k\nu^{\prime}_{2}}~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq 2}}\sum_{\tau:|\tau|\geq
t}\sum_{g_{\geq 2}\in\mathsf{Outcomes}_{\tau_{\geq
2}}}\tau\big{(}\widehat{H}^{x_{\geq 2}}_{g_{\geq 2}}\cdot(G^{|\tau_{\leq
1}|}\cdot(\mathbf{1}-G)^{1-|\tau_{\leq 1}|})\big{)}$
$\displaystyle\approx_{2k\nu^{\prime}_{2}}~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq 3}}\sum_{\tau:|\tau|\geq
d+1}\sum_{g_{\geq 3}\in\mathsf{Outcomes}_{\tau_{\geq
3}}}\tau\big{(}\widehat{H}^{x_{\geq 3}}_{g_{\geq 3}}\cdot(G^{|\tau_{\leq
2}|}\cdot(\mathbf{1}-G)^{2-|\tau_{\leq 2}|})\big{)}$ $\displaystyle\cdots$
$\displaystyle\approx_{2k\nu^{\prime}_{2}}~{}$
$\displaystyle\sum_{\tau:|\tau|\geq
t}\tau\big{(}G^{|\tau|}\cdot(\mathbf{1}-G)^{k-|\tau|}\big{)}$
$\displaystyle=~{}$
$\displaystyle\sum_{i=t}^{k}\binom{k}{i}\tau\big{(}G^{i}(\mathbf{1}-G)^{k-i}\big{)}\;.$

This proves the lemma.

We now prove Equation 113. To begin, for each $1\leq\ell\leq k+1$ and
$\tau_{\geq\ell}\in\\{0,1\\}^{k-\ell+1}$, we define the operator

$S_{\tau_{\geq\ell}}=\sum_{\tau_{<\ell}:|\tau|\geq
t}G^{|\tau_{<\ell}|}\cdot(\mathbf{1}-G)^{(\ell-1)-|\tau_{<\ell}|}\;.$ (114)

Then the statement in Equation 113 can be rewritten as

$\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau_{\geq\ell}}\sum_{g_{\geq\ell}\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}\widehat{H}^{x_{\geq\ell}}_{g_{\geq\ell}}\cdot
S_{\tau_{\geq\ell}}\big{)}$ $\displaystyle\approx_{2k\nu^{\prime}_{2}}~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{x_{>\ell}}\sum_{\tau_{>\ell}}\sum_{g_{>\ell}\in\mathsf{Outcomes}_{\tau_{>\ell}}}\tau\big{(}\widehat{H}^{x_{>\ell}}_{g_{>\ell}}\cdot
S_{\tau_{>\ell}}\big{)}\;.$ (115)

To prove this, we will use several facts about $S_{\tau_{\geq\ell}}$. First,
$S$ is self-adjoint and positive semidefinite. This is because each term in
Equation 114 is a product of $G$ and $(\mathbf{1}-G)$. These operators commute
with each other, and both are self-adjoint and positive semidefinite. Next,
$S$ is bounded:

$\displaystyle S_{\tau_{\geq\ell}}$
$\displaystyle=\sum_{\tau_{<\ell}:|\tau|\geq
t}G^{|\tau_{<\ell}|}\cdot(\mathbf{1}-G)^{(\ell-1)-|\tau_{<\ell}|}$
$\displaystyle\leq\sum_{\tau_{<\ell}}G^{|\tau_{<\ell}|}\cdot(\mathbf{1}-G)^{(\ell-1)-|\tau_{<\ell}|}$
$\displaystyle=(G+(\mathbf{1}-G))^{\ell-1}$ $\displaystyle=\mathbf{1}\;.$
(116)

In addition, for any $\tau_{\ell}\in\\{0,1\\}$,

$\displaystyle\Big{(}\operatorname*{\mathbb{E}}_{x_{\ell}}\sum_{g_{\ell}\in\mathsf{Outcomes}_{\tau_{\ell}}}\widehat{G}^{x_{\ell}}_{g_{\ell}}\Big{)}$
$\displaystyle=\left\\{\begin{array}[]{cl}G&\text{if }\tau_{\ell}=1\;,\\\
(\mathbf{1}-G)&\text{if }\tau_{\ell}=0\;,\end{array}\right.$ (119)
$\displaystyle=G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}}\;.$ (120)

Thus, for any $\tau_{>\ell}$,

$\displaystyle\sum_{\tau_{\ell}}S_{\tau_{\geq\ell}}\cdot\Big{(}\operatorname*{\mathbb{E}}_{x_{\ell}}\sum_{g_{\ell}\in\mathsf{Outcomes}_{\tau_{\ell}}}\widehat{G}^{x_{\ell}}_{g_{\ell}}\Big{)}$
$\displaystyle=\sum_{\tau_{\ell}}S_{\tau_{\geq\ell}}\cdot(G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}})$
$\displaystyle=\sum_{\tau_{\ell}}\sum_{\tau_{<\ell}:|\tau|\geq
t}G^{|\tau_{<\ell}|}\cdot(\mathbf{1}-G)^{(\ell-1)-|\tau_{<\ell}|}\cdot(G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}})$
$\displaystyle=\sum_{\tau_{\ell}}\sum_{\tau_{<\ell}:|\tau|\geq
t}G^{|\tau_{\leq\ell}|}\cdot(\mathbf{1}-G)^{\ell-|\tau_{\leq\ell}|}$
$\displaystyle=\sum_{\tau_{\leq\ell}:|\tau|\geq
t}G^{|\tau_{\leq\ell}|}\cdot(\mathbf{1}-G)^{\ell-|\tau_{\leq\ell}|}$
$\displaystyle=S_{\tau_{>\ell}}\;.$ (121)

Finally, for any $\tau_{\geq\ell}$,

$\displaystyle
S_{\tau_{\geq\ell}}\cdot\Big{(}\operatorname*{\mathbb{E}}_{x_{\ell}}\sum_{g_{\ell}\in\mathsf{Outcomes}_{\tau_{\ell}}}\widehat{G}^{x_{\ell}}_{g_{\ell}}\Big{)}\cdot
S_{\tau_{\geq\ell}}$ $\displaystyle=~{}$ $\displaystyle
S_{\tau_{\geq\ell}}\cdot(G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}})\cdot
S_{\tau_{\geq\ell}}$ (by Equation 120) $\displaystyle=~{}$
$\displaystyle\sqrt{G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}}}\cdot(S_{\tau_{\geq\ell}})^{2}\cdot\sqrt{G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}}}$
(because $S_{\tau_{\geq\ell}}$ commutes with $G$ and $(\mathbf{1}-G)$)
$\displaystyle\leq~{}$
$\displaystyle\sqrt{G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}}}\cdot
I\cdot\sqrt{G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}}}$ (by Equation
116) $\displaystyle=~{}$ $\displaystyle
G^{\tau_{\ell}}\cdot(\mathbf{1}-G)^{1-\tau_{\ell}}$ $\displaystyle=~{}$
$\displaystyle\Big{(}\operatorname*{\mathbb{E}}_{x_{\ell}}\sum_{g_{\ell}\in\mathsf{Outcomes}_{\tau_{\ell}}}\widehat{G}^{x_{\ell}}_{g_{\ell}}\Big{)}\;,$
(122)

where the last step uses Equation 120 again. This concludes the set of facts
we will need about $S_{\tau_{\geq\ell}}$.

Now we prove Equation 115. To start, we write using the definition

$\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau_{\geq\ell}}\sum_{(g_{\ell},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}\widehat{H}^{x_{\ell},\dots,x_{k}}_{g_{\ell},\dots,g_{k}}\cdot
S_{\tau_{\geq\ell}}\big{)}$ $\displaystyle=~{}$
$\displaystyle\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau_{\geq\ell}}\sum_{(g_{\ell},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdot(\widehat{G}^{x_{>\ell}}_{g_{>\ell}}\cdot(\widehat{G}^{x_{>\ell}}_{g_{>\ell}})^{\dagger})\cdot\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdot
S_{\tau_{\geq\ell}}\big{)}\;.$ (123)

Next, we commute the leftmost $\widehat{G}^{x_{\ell}}_{g_{\ell}}$ to the
right. Using Corollary 6.15 and Proposition 2.11 we get

$\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdot\widehat{G}^{x_{>\ell}}_{g_{>\ell}}\approx_{k\nu^{\prime}_{2}}\widehat{G}^{x_{>\ell}}_{g_{>\ell}}\cdot\widehat{G}^{x_{\ell}}_{g_{\ell}}$

and similarly

$\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdot(\widehat{G}^{x_{>\ell}}_{g_{>\ell}})^{\dagger}\approx_{k\nu^{\prime}_{2}}(\widehat{G}^{x_{>\ell}}_{g_{>\ell}})^{\dagger}\cdot\widehat{G}^{x_{\ell}}_{g_{\ell}}\;.$

Combining with Proposition 2.7 and injecting back into (123) we get

$\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau_{\geq\ell}}\sum_{(g_{\ell},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}\widehat{H}^{x_{\ell},\dots,x_{k}}_{g_{\ell},\dots,g_{k}}\cdot
S_{\tau_{\geq\ell}}\big{)}\approx_{2k\nu^{\prime}_{2}}\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau_{\geq\ell}}\sum_{(g_{\ell},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}(\widehat{G}^{x_{>\ell}}_{g_{>\ell}}\cdot(\widehat{G}^{x_{>\ell}}_{g_{>\ell}})^{\dagger})\cdot\widehat{G}^{x_{\ell}}_{g_{\ell}}\cdot
S_{\tau_{\geq\ell}}\big{)}\;.$ (124)

We end by noting that

$\displaystyle\eqref{eq:move-g-over-there-2}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{\geq\ell}}\sum_{\tau_{\geq\ell}}\sum_{(g_{\ell},g_{>\ell})\in\mathsf{Outcomes}_{\tau_{\geq\ell}}}\tau\big{(}\widehat{H}^{x_{>\ell}}_{g_{>\ell}}\cdot(S_{\tau_{\geq\ell}}\cdot\widehat{G}^{x_{\ell}}_{g_{\ell}})\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{>\ell}}\sum_{\tau_{>\ell}}\sum_{g_{>\ell}\in\mathsf{Outcomes}_{\tau_{>\ell}}}\tau\big{(}\widehat{H}^{x_{>\ell}}_{g_{>\ell}}\cdot\Big{(}\sum_{\tau_{\ell}}S_{\tau_{\geq\ell}}\cdot\Big{(}\operatorname*{\mathbb{E}}_{x_{\ell}}\sum_{g_{\ell}\in\mathsf{Outcomes}_{\tau_{\ell}}}\widehat{G}^{x_{\ell}}_{g_{\ell}}\Big{)}\Big{)}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{>\ell}}\sum_{\tau_{>\ell}}\sum_{g_{>\ell}\in\mathsf{Outcomes}_{\tau_{>\ell}}}\tau\big{(}\widehat{H}^{x_{>\ell}}_{g_{>\ell}}\cdot
S_{\tau_{>\ell}}\big{)}\;.$ (by Equation 121)

This concludes the proof of Equation 115 and therefore proves the lemma. ∎

The following lemma follows from the functional calculus for bounded self-
adjoint operators. In the lemma, $\mathscr{A}$ may be any von Neumann
subalgebra of $\mathrm{B}(\mathcal{H})$ and $\tau$ a normal tracial state on
$\mathscr{A}$, but we state (and use it) for the algebra and tracial state
associated with the strategy $\mathscr{S}$.

######  Lemma 6.22.

Let $0<\theta<1$ and let $k,t>0$ be integers such that $k\geq 2t/\theta$.
Define the function $F:\mathbb{R}\to\mathbb{R}$ by

$F(x)=\sum_{r=t}^{k}\binom{k}{r}x^{r}(1-x)^{k-r}.$

Then for any self-adjoint $X\in\mathscr{A}$ such that $0\leq X\leq\mathbf{1}$
and $\tau\big{(}X\big{)}\geq 1-\kappa$, it holds that $F(X)\in\mathscr{A}$ and
moreover

$\tau\big{(}F(X)\big{)}\geq 1-\frac{\kappa}{1-\theta}-e^{-\theta^{2}k/2}.$

###### Proof.

The statement that $F(X)\in\mathscr{A}$ follows from the functional calculus
for bounded self-adjoint operators. Let $\mu$ be the projection-valued measure
on the Borel $\sigma$-algebra in $[0,1]$ associated to $X$ by the spectral
theorem for bounded self-adjoint operators (see e.g. [Hal13, Theorem 7.12]).
Then $X=\int_{[0,1]}\lambda\,\mathrm{d}\mu(\lambda)$, and using that $\tau$ is
normal, there exists a trace class operator $A\in\mathrm{B}(\mathcal{H})$ such
that

$\displaystyle\tau(X)$ $\displaystyle=\mbox{\rm
tr}\Big{(}\int_{[0,1]}\lambda\,\mathrm{d}\mu(\lambda)A\Big{)}$
$\displaystyle=\int_{[0,1]}\lambda\,\mbox{\rm
tr}\big{(}A\,\mathrm{d}\mu(\lambda)\big{)}$
$\displaystyle=\int_{[0,1]}\lambda\,\mathrm{d}\nu(\lambda)\;,$

where $\nu$ is the real-valued measure on $[0,1]$ defined by
$\,\mathrm{d}\nu(E)=\int_{E}\mbox{\rm tr}(A\,\mathrm{d}\mu(\lambda))$. Thus
the assumption $\tau(X)\geq 1-\kappa$ implies that
$\int_{\lambda}\lambda\,\mathrm{d}\nu(\lambda)\geq 1-\kappa$. By Markov’s
inequality, for any $0<\theta<1$,

$\int_{[0,1]}\mathbb{I}[1-\lambda\geq
1-\theta]\,\mathrm{d}\nu(\lambda)\,\leq\,\frac{\int_{[0,1]}(1-\lambda)\,\mathrm{d}\nu}{1-\theta}\,\leq\,\frac{\kappa}{1-\theta}\;.$
(125)

We now evaluate $\tau(F(X))$. Observe that for $0\leq p\leq 1$, $F(p)$ is
precisely the probability of observing at least $t$ successes out of $k$
i.i.d. Bernoulli trials, each of which succeeds with probability $p$. In other
words, it is the probability that $Y:=Y_{1}+\cdots+Y_{k}\geq t$, where
$Y_{1},\ldots,Y_{k}\sim\mathrm{Bernoulli}(p)$. We can bound this probability
by the additive Chernoff bound (see the second additive bound in [Blu11]):

$\displaystyle\Pr(Y<t)$ $\displaystyle=\Pr(Y<pk-(pk-t))$
$\displaystyle=\Pr\Big{(}Y<pk-\Big{(}p-\frac{t}{k}\Big{)}\cdot k\Big{)}$
$\displaystyle\leq\exp\Big{(}-2\Big{(}p-\frac{t}{k}\Big{)}^{2}\cdot
k\Big{)}\;.$

Thus,

$F(p)=\Pr(Y\geq t)=1-\Pr(Y<t)\geq
1-\exp\Big{(}-2\Big{(}p-\frac{t}{k}\Big{)}^{2}\cdot k\Big{)}\;.$ (126)

Putting the pieces together, we compute $\tau(F(X))$:

$\displaystyle\tau\big{(}F(X)\big{)}$
$\displaystyle=\tau\Big{(}\int_{[0,1]}F(\lambda)\,\mathrm{d}\mu(\lambda)\Big{)}$
$\displaystyle=\int_{[0,1]}F(\lambda)\,\tau\big{(}A\,\mathrm{d}\mu(\lambda)\big{)}$
$\displaystyle\geq\int_{[0,1]}F(\lambda)\,\mathbb{I}[\lambda\geq\theta]\,\mathrm{d}\nu(\lambda)$
($F$ is nonnegative) $\displaystyle\geq
F(\theta)\,\int_{[0,1]}\mathbb{I}[\lambda\geq\theta]\,\mathrm{d}\nu(\lambda)$
($F$ is non-decreasing)
$\displaystyle\geq\Big{(}1-\frac{\kappa}{1-\theta}\Big{)}\cdot F(\theta)$ (by
Equation 125)
$\displaystyle\geq\Big{(}1-\frac{\kappa}{1-\theta}\Big{)}\cdot\Big{(}1-\exp\Big{(}-2\Big{(}\theta-\frac{t}{k}\Big{)}^{2}\cdot
k\Big{)}\Big{)}$ (Equation 126) $\displaystyle\geq
1-\frac{\kappa}{1-\theta}-\exp\Big{(}-2\Big{(}\theta-\frac{d}{k}\Big{)}^{2}\cdot
k\Big{)}\;.$ (127)

Finally, we note that because $k\geq 2t/\theta$, we have $\theta/2\geq t/k$.
This implies that $\theta-t/k\geq\theta-\theta/2=\theta/2$, and so
$(\theta-t/k)^{2}\geq(\theta/2)^{2}=\theta^{2}/4$. As a result,

$\exp\Big{(}2\Big{(}\theta-\frac{t}{k}\Big{)}^{2}\cdot
k\Big{)}\geq\exp\Big{(}\theta^{2}k/2\Big{)}\;.$

Equivalently,

$\exp\Big{(}-2\Big{(}\theta-\frac{t}{k}\Big{)}^{2}\cdot
k\Big{)}\leq\exp\Big{(}-\theta^{2}k/2\Big{)}\;.$

Thus, we conclude

$\tau\big{(}F(X)\big{)}\geq
1-\frac{\kappa}{1-\theta}-\exp\Big{(}-\theta^{2}k/2\Big{)}\;.\qed$

######  Corollary 6.23 (Completeness of $H$).

Recall the error parameters $\nu_{5}^{\prime},\nu_{6}^{\prime}$ from Lemma
6.20 and Lemma 6.21, respectively. Let $\nu=\nu_{5}^{\prime}+\nu_{6}^{\prime}$
and let $k\geq 12mt$ be an integer. Then $\nu$ is equal to some polynomial
function
$\mathrm{poly}(m,t,k)\cdot\mathrm{poly}(\varepsilon,\delta,\zeta,n^{-1})$ and
furthermore

$\tau\big{(}H\big{)}\geq
1-\kappa\cdot\left(1+\frac{1}{3m}\right)-\nu-e^{-\frac{k}{72m^{2}}}\;.$

###### Proof.

We begin by approximating the completeness as follows.

$\displaystyle\tau\big{(}H\big{)}$
$\displaystyle\approx_{\nu^{\prime}_{5}}\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{k}}\sum_{\tau:|\tau|\geq
t}\sum_{(g_{1},\ldots,g_{k})\in\mathsf{Outcomes}_{\tau}}\tau\big{(}\widehat{H}^{x_{1},\ldots,x_{k}}_{g_{1},\ldots,g_{k}}\big{)}$
(by Lemma 6.20)
$\displaystyle\approx_{\nu^{\prime}_{6}}\sum_{i=d+1}^{k}\binom{k}{i}\tau\big{(}G^{i}(\mathbf{1}-G)^{k-i}\big{)}$
(by Lemma 6.21) $\displaystyle=\tau\big{(}F(G)\big{)}\ $

where $F$ is the function from Lemma 6.22. We unroll the error parameters in
terms of $\varepsilon,\delta,\zeta,m,n,t,k$:

$\displaystyle\gamma_{m}=1-\frac{d^{m}}{n^{m}}\leq\frac{mt}{n}$ (Proposition
2.18) $\displaystyle\nu_{1}=8(\sqrt{\zeta}+\sqrt{(m+1)\delta})$ (Lemma 6.2)
$\displaystyle\nu_{2}=4(\gamma_{m}+\nu_{1})$ (Lemma 6.3)
$\displaystyle\nu_{2}^{\prime}=27\nu_{2}^{1/4}$ (Corollary 6.15)
$\displaystyle\nu_{3}^{\prime}=k\nu^{\prime\prime}_{3}+k^{2}/n$ (Lemma 6.17)
$\displaystyle\nu_{4}^{\prime}=\nu^{\prime}_{3}+\sqrt{2(m+1)\varepsilon}$
(Corollary 6.18)
$\displaystyle\nu_{5}^{\prime}=2\frac{k^{2}}{n}+k\nu^{\prime\prime}_{3}+\gamma_{m}$
(Lemma 6.20) $\displaystyle\nu_{6}^{\prime}=2k^{2}\nu^{\prime}_{2}$ (Lemma
6.21)

One can see that each of the error parameters
$\gamma_{m},\nu_{1},\ldots,\nu_{6}^{\prime}$ can be expressed in the form
$\mathrm{poly}(m,t,k)\cdot\mathrm{poly}(\varepsilon,\delta,\zeta,n^{-1})$
where each error parameter is a different polynomial function. Thus letting
$\nu=\nu_{5}^{\prime}+\nu_{6}^{\prime}=\mathrm{poly}(m,t,k)\cdot\mathrm{poly}(\varepsilon,\delta,\zeta,n^{-1})$,
we have that

$\tau(H)\geq\tau(F(G))-\nu~{}.$

Define $\theta=\frac{1}{6m}$. Note that $k\geq 2t/\theta$ by assumption, and
that $\frac{1}{1-\theta}\leq 1+\frac{1}{3m}$. As a result, $k$ and $\theta$
satisfy the hypotheses of Lemma 6.22, which implies

$\displaystyle\tau\big{(}F(G)\big{)}$ $\displaystyle\geq
1-\frac{\kappa}{1-\theta}-e^{-\theta^{2}k/2}$ $\displaystyle\geq
1-\frac{\kappa}{1-\theta}-e^{-\frac{k}{72m^{2}}}$ $\displaystyle\geq
1-\kappa\cdot\left(1+\frac{1}{3m}\right)-e^{-\frac{k}{72m^{2}}}.$

In total, we have

$\tau\big{(}H\big{)}\geq
1-\kappa\cdot\left(1+\frac{1}{3m}\right)-\nu-e^{-\frac{k}{72m^{2}}}.$

This completes the proof. ∎

We conclude by observing that the conclusion of Lemma 4.3 follows immediately
by letting $k$ denote the parameter $r$ in the statement of Lemma 4.3 101010We
use $r$ in the statement of Lemma 4.3 in order to avoid confusion with the
dimension of the code $\mathcal{C}$, which is also denoted by $k$., combining
the bounds from Corollary 6.18, and Corollary 6.23 using the same “completion”
procedure as described in Section 6.3.3.

##  Appendix A Operators on expander graphs

Let $G$ be an $n$-vertex graph with some distribution on the edges, such that
the marginal distribution on the vertices is uniform. Let

$K=\operatorname*{\mathbb{E}}_{(u,v)\sim G}|u\rangle\\!\langle v|$

and let

$L=\frac{1}{n}\mathbf{1}-K$

denote the normalized Laplacian of $G$.

######  Proposition A.1.

$L=\frac{1}{2}\cdot\operatorname*{\mathbb{E}}_{(u,v)\sim
G}({|u\rangle}-{|v\rangle})({\langle u|}-{\langle v|})$.

Thus $L$ is positive semidefinite and has $0$-eigenvector

${|\varphi_{0}\rangle}=\frac{1}{\sqrt{n}}\sum_{u\in V(G)}{|u\rangle}$

where $V(G)$ denotes the vertex set of $G$.

Let $0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ denote the
eigenvalues of $L$ in non-decreasing order. Then we have that

$L\geq\lambda_{2}\,(\mathbf{1}-|\varphi_{0}\rangle\\!\langle\varphi_{0}|).$
(128)

The following lemma is a variant of the familiar Poincaré inequality for
expander graphs. It states that “global” averages of an operator-valued
function on an expander graph can be approximated by averages of the function
on random edges of the graph.

######  Lemma A.2.

Let $\mathcal{H}$ be a Hilbert space and let $\rho$ be a positive linear
functional on $\mathrm{B}(\mathcal{H})$. Let $\\{A^{u}\\}_{u\in[n]}$ be
bounded operators on $\mathcal{H}$. Suppose $G$ is an $n$-vertex graph
associated with an edge distribution that has the uniform marginal
distribution on the vertices. Then

$\operatorname*{\mathbb{E}}_{u,v\sim[n]}\,\rho((A^{u}-A^{v})^{*}(A^{u}-A^{v}))\leq\frac{1}{n\lambda_{2}}\operatorname*{\mathbb{E}}_{(u,v)\sim
G}\,\rho((A^{u}-A^{v})^{*}(A^{u}-A^{v}))$

where the expectation on the left hand side is over uniformly random vertices
$u,v\sim[n]$.

###### Proof.

Define the following map $V:\mathcal{H}\to\mathbb{C}^{n}\otimes\mathcal{H}$:

$V=\sum_{u}{|u\rangle}\otimes A^{u}.$

The proof is based on estimating the Rayleigh quotient

$\frac{V^{*}(L\otimes\mathbf{1})V}{V^{*}V}\;.$

Observe that

$V^{*}(L\otimes\mathbf{1})V=\frac{1}{2}\operatorname*{\mathbb{E}}_{(u,v)\sim
G}(A^{u}-A^{v})^{*}(A^{u}-A^{v}).$ (129)

On the other hand, we have

$\displaystyle V^{*}(L\otimes\mathbf{1})V$ $\displaystyle\geq\lambda_{2}\cdot
V^{*}\Big{(}\mathbf{1}-|\varphi_{0}\rangle\\!\langle\varphi_{0}|\Big{)}V$
(130)
$\displaystyle\geq\lambda_{2}\cdot\Big{(}\sum_{u}(A^{u})^{*}A^{u}-\big{(}\sum_{v}n^{-1/2}A^{v}\big{)}^{*}\big{(}\sum_{v}n^{-1/2}A^{v}\big{)}\Big{)}$
(131)
$\displaystyle=n\lambda_{2}\cdot\Big{(}\operatorname*{\mathbb{E}}_{u\sim[n]}(A^{u})^{*}A^{u}-\overline{A}^{*}\overline{A}\Big{)}$
(132)
$\displaystyle=n\lambda_{2}\cdot\Big{(}\operatorname*{\mathbb{E}}_{u\sim[n]}(A^{u})^{*}(A^{u}-\overline{A})\Big{)}$
(133)
$\displaystyle=\frac{n\lambda_{2}}{2}\cdot\Big{(}\operatorname*{\mathbb{E}}_{u,v\sim[n]}(A^{u}-A^{v})^{*}(A^{u}-A^{v})\Big{)}\;.$
(134)

where in the second line we computed $V^{*}V=\sum_{u}(A^{u})^{*}A^{u}$ and
$V^{*}{|\varphi_{0}\rangle}=\sum_{u}n^{-1/2}(A^{u})^{*}$, and in the third
line we defined $\overline{A}=\operatorname*{\mathbb{E}}_{v\sim[n]}A^{v}$.
Applying the positive linear functional $\rho$ on Equation 129 and Equation
134 yields the statement of the Lemma. ∎

## References

  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  Journal of the ACM (JACM), 45(3):501–555, 1998.
  * [Ara02] PK Aravind.  A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities.  arXiv preprint quant-ph/0206070, 2002.
  * [AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of $\mathsf{NP}$.  Journal of the ACM (JACM), 45(1):70–122, 1998.
  * [BFL91] László Babai, Lance Fortnow, and Carsten Lund.  Non-deterministic exponential time has two-prover interactive protocols.  Computational complexity, 1(1):3–40, 1991.
  * [Bla06] Bruce Blackadar.  Operator algebras: theory of C*-algebras and von Neumann algebras, volume 122.  Springer Science & Business Media, 2006.
  * [Blu11] Avrim Blum.  Lecture 5 from 15-859(M): Randomized Algorithms.  Found at http://www.cs.cmu.edu/~avrim/Randalgs11/lectures/lect0124.pdf, 2011.
  * [BSS06] Eli Ben-Sasson and Madhu Sudan.  Robust locally testable codes and products of codes.  Random Structures & Algorithms, 28(4):387–402, 2006.
  * [CLP15] Valerio Capraro, Martino Lupini, and Vladimir Pestov.  Introduction to sofic and hyperlinear groups and Connes’ embedding conjecture, volume 1.  Springer, 2015.
  * [dlS21] Mikael de la Salle.  Orthogonalization of positive operator valued measures.  arXiv preprint arXiv:2103.14126, 2021.
  * [DP16] Kenneth J Dykema and Vern Paulsen.  Synchronous correlation matrices and connes’ embedding conjecture.  Journal of Mathematical Physics, 57(1):015214, 2016.
  * [DSW06] Irit Dinur, Madhu Sudan, and Avi Wigderson.  Robust local testability of tensor products of LDPC codes.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 304–315. Springer, 2006.
  * [GLR+91] Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson.  Self-testing/correcting for polynomials and for approximate functions.  In STOC, volume 91, pages 32–42, 1991.
  * [GS06] Oded Goldreich and Madhu Sudan.  Locally testable codes and PCPs of almost-linear length.  Journal of the ACM (JACM), 53(4):558–655, 2006.
  * [Hal13] Brian C Hall.  Quantum theory for mathematicians, volume 267.  Springer, 2013.
  * [IV12] Tsuyoshi Ito and Thomas Vidick.  A multi-prover interactive proof for $\mathsf{NEXP}$ sound against entangled provers.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 243–252. IEEE, 2012.
  * [JNV+20a] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.  $\mathsf{MIP}^{*}=\mathsf{RE}$.  arXiv preprint arXiv:2001.04383, 2020.
  * [JNV+20b] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.  Quantum soundness of the classical low individual degree test.  arXiv preprint arXiv:2009.12982, 2020.
  * [KPS18] Se-Jin Kim, Vern Paulsen, and Christopher Schafhauser.  A synchronous game for binary constraint systems.  Journal of Mathematical Physics, 59(3):032201, 2018.
  * [KV11] Julia Kempe and Thomas Vidick.  Parallel repetition of entangled games.  In Proceedings of the forty-third annual ACM Symposium on Theory of Computing, pages 353–362, 2011.
  * [Mer90] David Mermin.  Simple unified form for the major no-hidden-variables theorems.  Phys. Rev. Lett., 65(27):3373, 1990.
  * [MR08] Dana Moshkovitz and Ran Raz.  Two-query PCP with subconstant error.  Journal of the ACM (JACM), 57(5):1–29, 2008.
  * [NV18a] Anand Natarajan and Thomas Vidick.  Low-degree testing for quantum states, and a quantum entangled games PCP for $\mathsf{QMA}$.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 731–742. IEEE, 2018.
  * [NV18b] Anand Natarajan and Thomas Vidick.  Two-player entangled games are $\mathsf{NP}$-hard.  In Proceedings of the 33rd Computational Complexity Conference, pages 1–18, 2018.
  * [NW19] Anand Natarajan and John Wright.  $\mathsf{NEEXP}\subseteq\mathsf{MIP}^{*}$.  In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 510–518, 2019.
  * [Per90] Asher Peres.  Incompatible results of quantum measurements.  Physics Letters A, 151(3-4):107–108, 1990.
  * [PSS+16] Vern I Paulsen, Simone Severini, Daniel Stahlke, Ivan G Todorov, and Andreas Winter.  Estimating quantum chromatic numbers.  Journal of Functional Analysis, 270(6):2188–2222, 2016.
  * [PX03] Gilles Pisier and Quanhua Xu.  Non-commutative $L^{p}$-spaces.  Handbook of the geometry of Banach spaces, 2:1459–1517, 2003.
  * [RS92] Ronitt Rubinfeld and Madhu Sudan.  Self-testing polynomial functions efficiently and over rational domains.  In SODA, pages 23–32, 1992.
  * [RS97] Ran Raz and Shmuel Safra.  A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of $\mathsf{NP}$.  In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 475–484, 1997.
  * [Vid15] Michael Viderman.  A combination of testability and decodability by tensor products.  Random Structures & Algorithms, 46(3):572–598, 2015.
  * [Vid16] Thomas Vidick.  Three-player entangled XOR games are $\mathsf{NP}$-hard to approximate.  SIAM Journal on Computing, 45(3):1007–1063, 2016.
  * [Vid20] Thomas Vidick.  Erratum: Three-player entangled XOR games are $\mathsf{NP}$-hard to approximate.  SIAM Journal on Computing, 49(6):1423–1427, 2020.
  * [Vid21] Thomas Vidick.  Almost synchronous quantum correlations.  arXiv preprint arXiv:2103.02468, 2021.

[zji] Zhengfeng Ji
Tsinghua University
jizhengfengtsinghuaeducn [anand] Anand Natarajan
Massachusetts Institute of Technology
anandnmitedu
[thomas] Thomas Vidick
California Institute of Technology
vidickcaltechedu [john] John Wright
University of Texas at Austin
wrightcsutexasedu [henry] Henry Yuen
Columbia University
hyuencscolumbiaedu