# Quantum Soundness of Testing Tensor Codes

Zhengfeng Ji Supported by Australian Research Council (DP200100950). Conducted
this work while at University of Technology, Sydney. Anand Natarajan  Thomas
Vidick Supported by MURI Grant FA9550-18-1-0161, NSF QLCI Grant OMA-2016245,
and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with
support of the Gordon and Betty Moore Foundation (GBMF-12500028). John Wright
Henry Yuen Supported by AFOSR award FA9550-21-1-0040, NSF CAREER award
CCF-2144219, and the Sloan Foundation.

###### Abstract

A locally testable code is an error-correcting code that admits very efficient
probabilistic tests of membership. Tensor codes provide a simple family of
combinatorial constructions of locally testable codes that generalize the
family of Reed-Muller codes. The natural test for tensor codes, the axis-
parallel line vs. point test, plays an essential role in constructions of
probabilistically checkable proofs.

We analyze the axis-parallel line vs. point test as a two-prover game and show
that the test is sound against quantum provers sharing entanglement. Our
result implies the quantum-soundness of the low individual degree test, which
is an essential component of the $\mathsf{MIP}^{*}=\mathsf{RE}$ theorem. Our
proof generalizes to the infinite-dimensional _commuting-operator model_ of
quantum provers.

title = Quantum Soundness of Testing Tensor Codes, author = Zhengfeng Ji,
Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen, plaintextauthor =
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen,
plaintexttitle = Quantum Soundness of Testing Tensor Codes, keywords = quantum
multiplayer games, tensor codes, entanglement tests, year=2022, number=17,
received=8 February 2022, published=6 December 2022, doi=10.19086/da.55554,

[classification=text]

##  1 Introduction

Let $\Sigma$ denote a finite field and let $\mathcal{C}$ denote a subspace of
the vector space $\Sigma^{n}$ of dimension $k\leq n$. We say that
$\mathcal{C}$ is a _(linear) code over alphabet $\Sigma$ with blocklength $n$
and dimension $k$_. Viewing the elements $c\in\mathcal{C}$ (called
_codewords_) as functions mapping $[n]=\\{1,2,\ldots,n\\}$ to $\Sigma$, if it
further holds that for any two distinct $c,c^{\prime}\in\mathcal{C}$ the
number of $i\in[n]$ such that $c(i)\neq c^{\prime}(i)$ is at least $d$ then we
say that $\mathcal{C}$ has _distance $d$_.

A natural method to build large codes out of smaller codes is to take their
_tensor product_. Let $\mathcal{C}$ denote a code (called the _base code_)
over alphabet $\Sigma$ with blocklength $n$, dimension $k$, distance $d$. The
_tensor code_ $\mathcal{C}^{\otimes m}$ is defined as the collection of all
functions $c:[n]^{m}\to\Sigma$ such that for all
$(u_{1},\ldots,u_{m})\in[n]^{m}$, for all $j\in[m]$, the function
$g(s)=c(u_{1},\ldots,u_{j-1},s,u_{j+1},\ldots,u_{m})$ is a codeword of
$\mathcal{C}$ (see Definition 2.16 and Definition 2.17). The blocklength of
$\mathcal{C}^{\otimes m}$ is $n^{m}$, its dimension is $k^{m}$, and its
distance is at least $d^{m}$. One can also consider taking tensor products of
_different_ codes $\mathcal{C}_{1}\otimes\mathcal{C}_{2}\otimes\cdots$, but we
focus our attention on tensor codes of the form $\mathcal{C}^{\otimes m}$.

Tensor codes have been extensively studied in theoretical computer science
because they provide natural constructions of _locally testable codes_ [GS06,
BSS06, DSW06, Vid15]. A code $\mathcal{C}$ is locally testable if it has a
_tester_ algorithm that makes a small number of queries to a given
$w:[n]\to\Sigma$, accepts if $w$ is a codeword of $\mathcal{C}$, and rejects
with noticeable probability if $w$ is far from every codeword. In other words
the code has efficient probabilistic tests for membership. Locally testable
codes are central components of probabilistically checkable proofs (PCPs); in
particular improvements in PCPs have been continually driven by the
development of improved _low-degree tests_ , which are tests for codes based
on low-degree polynomials [AS98, ALM+98, RS97, MR08].

In the context of PCPs it is common to present a testing procedure for a code
as a game between a _referee_ and two non-communicating _provers_. The goal of
the referee is to determine, by making a few queries to the provers, whether
the provers’ responses are globally consistent with a codeword from the code.
Let $\mathcal{C}^{\otimes m}$ denote a tensor code; it has a natural two-
prover test (called the _tensor code test_) associated to it:

  1. 1.

The referee samples a uniformly random $u\sim[n]^{m}$ and sends $u$ to prover
A. They respond with a value $a\in\Sigma$.

  2. 2.

The referee samples a uniformly random $j\sim[m]$ and sends the axis-parallel
line
$\ell=\\{(u_{1},\ldots,u_{j-1},s,u_{j+1},\ldots,u_{m}):s\in[n]\\}$ to prover
B. They respond with a codeword $g\in\mathcal{C}$.

  3. 3.

The referee accepts iff $g(u_{j})=a$.

If $c\in\mathcal{C}^{\otimes m}$ is a codeword and the provers respond with
$c(u)$ and $c|_{\ell}$ (i.e. the restriction of $c$ to the line $\ell$) then
they will pass with probability $1$. _Soundness_ of of the tensor code test
refers to the converse statement, namely that provers who succeed with high
probability must be (approximately) responding according to some codeword
$c\in\mathcal{C}^{\otimes m}$. This is formalized as follows.

######  Theorem 1.1.

Let $\mathcal{C}$ be an interpolable111The _interpolable_ qualifier on the
base code $\mathcal{C}$ is a technical condition stating that for every
$t=n-d+1$ coordinates $i_{1},\ldots,i_{t}\in[n]$ and values
$a_{1},\ldots,a_{t}\in\Sigma$ there exists a unique codeword $c\in\mathcal{C}$
such that $c(i_{j})=a_{j}$ for $j\in[t]$. We discuss the interpolability
condition in more detail in Section 1.2. code. Suppose provers A and B are
deterministic and pass the tensor code test corresponding to
$\mathcal{C}^{\otimes m}$ with probability $1-\varepsilon$. Let
$f:[n]^{m}\to\Sigma$ denote the responses of prover A. Then there exists a
codeword $c\in\mathcal{C}^{\otimes m}$ such that

$\Pr_{u\sim[n]^{m}}[f(u)=c(u)]\geq
1-\mathrm{poly}(m,t)\cdot(\mathrm{poly}(\varepsilon)+\mathrm{poly}(1/n))\;,$

where $t=n-d+1$.

The proof of Theorem 1.1 follows almost directly from the analysis of the low-
degree test of Babai, Fortnow and Lund [BFL91], a central ingredient of their
characterization $\mathsf{MIP}=\mathsf{NEXP}$ of (classical) multiprover
interactive proof systems. They analyzed the tensor code test for the case
when the base code $\mathcal{C}$ is the set of univariate polynomials over a
finite field $\mathbb{F}$ of degree at most $s$, and the tensor code
$\mathcal{C}^{\otimes m}$ is the set of $m$-variate polynomials over
$\mathbb{F}$ with _individual_ degree at most $s$ (i.e. each variable has
degree at most $s$). 222Technically speaking, Babai, Fortnow and Lund analyzed
the low-degree test for _multilinear_ polynomials (i.e. polynomials with
individual degree at most $1$), but as noted in Remark 5.15 of [BFL91], their
analysis generalizes to polynomials with larger individual degree. By noting
that their proof only uses the tensor code structure of low individual degree
polynomials and the fact that univariate polynomials with degree at most $s$
form a code with distance $n-s$ we see that their proof implies Theorem 1.1.

The analysis of Babai, Fortnow, and Lund’s low-degree test in the _quantum_
setting has played a major role in the study of the class $\mathsf{MIP}^{*}$
of languages having quantum multi-prover interactive proofs [IV12, Vid16,
NV18b, NV18a, NW19]. In this setting, the provers are no longer modeled as
deterministic but instead are allowed to use a _quantum strategy_ , in which
their responses are generated by performing measurements on a shared entangled
state. While entanglement does not allow the provers to communicate with each
other, it gives rise to stronger correlations that cannot be achieved
classically. Thus the classical analysis does not extend in any direct way.

Quantum soundness of a variant of the multilinearity test (i.e. the case
$s=1$) played with three entangled provers is at the heart of the proof of
$\mathsf{NEXP}\subseteq\mathsf{MIP}^{*}$ [IV12]. This analysis is extended to
general degree $s$ in [Vid16], and to the case of two provers in [NV18b].
However, it was later discovered [Vid20] that the argument contained in
[Vid16] contains a mistake. The case of two provers and general $s$ is
essential in the proof of the recent characterization
$\mathsf{MIP}^{*}=\mathsf{RE}$, which shows that every recursively enumerable
language (including the Halting problem) has an interactive proof in the
entangled provers model [JNV+20a]. Our main contribution is a proof of
soundness of the low individual degree test that is used in the proof of
$\mathsf{MIP}^{*}=\mathsf{RE}$.333The present paper is an updated version of
an earlier arXiv posting by the same authors [JNV+20b], which was posted after
the mistake in the earlier works had been discovered. We discuss additional
improvements compared to that earlier draft below.  We show that quantum
provers who succeed with high probability in the test must still – in a
certain sense – respond according to a low individual degree polynomial.
Informally, our main result is the following:

######  Theorem 1.2 (Quantum soundness of the tensor code test, informal).

Let $\mathcal{C}$ be an interpolable code. Suppose provers A and B are quantum
and pass the (augmented 444The qualifier “augmented” refers to the addition of
a subtest which is used to enforce approximate commutation relations between
the measurement operators used by prover A. This is a technical point that we
discuss in more detail in Section 1.2. ) tensor code test corresponding to
$\mathcal{C}^{\otimes m}$ with probability $1-\varepsilon$. Let
$\\{A^{u}\\}_{u\in[n]^{m}}$ denote the “points” measurements of prover A, who
upon receiving question $u\in[n]^{m}$ performs measurement $A^{u}$ to obtain
outcome $a\in\Sigma$. Then there exists a measurement $G$ with outcome set
$\mathcal{C}^{\otimes m}$ satisfying the following properties:

  * •

(Self-consistency) If prover A and prover B both perform the measurement $G$,
they both obtain the same outcome $c\in\mathcal{C}^{\otimes m}$ with
probability at least $1-\delta$.

  * •

(Consistency with points) If prover A measures $A^{u}$ for a uniformly random
point $u\in[n]^{m}$ to obtain an outcome $a\in\Sigma$ and prover B measures
$G$ to obtain an outcome $c\in\mathcal{C}^{\otimes m}$, then $a=c(u)$ with
probability at least $1-\delta$.

Here, $\delta=\mathrm{poly}(m,t)\cdot\mathrm{poly}(\varepsilon,1/n)$ with
$t=n-d+1$ .

The formal statement of this theorem is presented as Theorem 4.1. Intuitively
the theorem states that even though the provers are allowed to employ quantum
strategies, their strategy is essentially equivalent to a classical one: the
provers would have roughly the same winning probability if they both measured
$G$ (which does not depend on any question) to obtain a codeword
$c\in\mathcal{C}^{\otimes m}$ and then responded according to $c$. In other
words, the “points” measurements $\\{A^{u}\\}$ of prover A are – despite not
necessarily commuting with each other – approximately consistent with a single
“global” codeword measurement $G$.

This paper generalizes our previous manuscript [JNV+20b] which established
Theorem 1.2 for the low individual degree test. In addition we significantly
simplify the earlier analysis of [JNV+20b] by working in the framework of
_synchronous strategies_ for the quantum provers. Synchronous strategies are a
subclass of quantum strategies where the provers are assumed to use the same
measurement operators whenever they receive the same question, and furthermore
the entangled state that they share is a maximally entangled state. These
assumptions allow us to shortcut many technical calculations that appear in
[JNV+20b]. Furthermore, it is without loss of generality since recent work by
one of us establishes that soundness with synchronous strategies for a large
class of two-prover games (including the tensor code test) can be translated
back into soundness for general quantum strategies [Vid21]. As a result,
Theorem 1.2 extends in a straightforward manner to general strategies; see
Theorem 4.7 for the precise statement.

An additional benefit of our streamlined analysis is that synchronous
strategies can also be defined in infinite dimensions. In this case the
condition that the entangled state is maximally entangled is replaced by the
condition that the state is _tracial_ , a notion which we introduce formally
below. Our proof naturally extends to this situation, and we are thus able to
prove soundness of the tensor code test against _infinite-dimensional_
(synchronous) quantum strategies. We explain the synchronous strategies
framework in more detail in Section 1.1. We motivate the consideration of
infinite-dimensional strategies from a complexity-theoretic viewpoint in
Section 1.3.

###  1.1 Nonlocal games and synchronous strategies

A _nonlocal game_ $G$ is specified by a quadruple
$(\mathcal{X},\mathcal{A},\mu,D)$ which corresponds to the following scenario:
a referee first samples a pair of questions $(x,y)$ from a distribution $\mu$
over a finite product set $\mathcal{X}\times\mathcal{X}$ and sends $x$ to
prover A and $y$ to prover B. The provers respond with answers
$a,b\in\mathcal{A}$ respectively and the referee accepts if and only if
$D(x,y,a,b)=1$, where
$D:\mathcal{X}\times\mathcal{X}\times\mathcal{A}\times\mathcal{A}\to\\{0,1\\}$
is a decision predicate. Different kinds of restrictions on the provers’
allowed actions to determine their answers lead to different optimal success
probabilities for them in the game. The tensor code test described earlier is
an example of a nonlocal game, and the analysis of it with deterministic non-
communicating provers is a key component in the aforementioned complexity-
theoretic results, e.g. [BFL91].

A quantum strategy for a nonlocal game describes the provers’ behavior during
the game. We focus on the class of _synchronous strategies_. A synchronous
strategy $\mathscr{S}$ for a game $G$ is specified by a separable Hilbert
space $\mathcal{H}$ (which could be infinite-dimensional), a von Neumann
algebra $\mathscr{A}$ on $\mathcal{H}$, a tracial state $\tau$ on the algebra
$\mathscr{A}$,555A _von Neumann algebra_ $\mathscr{A}$ on a Hilbert space
$\mathcal{H}$ is a $*$-subalgebra of $\mathrm{B}(\mathcal{H})$ (the set of
bounded operators on $\mathcal{H}$) that contains the identity operator and is
closed under the weak operator topology. A _tracial state_ $\tau$ on the
algebra $\mathscr{A}$ is a positive, unital linear functional that satisfies
the _trace property_ : $\tau\left(AB\right)=\tau\left(BA\right)$ for all
$A,B\in\mathscr{A}$.  and a collection of projective measurements
$\\{M^{x}\\}_{x\in\mathcal{X}}$ in $\mathscr{A}$ (each $M^{x}$ is a set of
projections $\\{M^{x}_{a}\\}_{a\in\mathcal{A}}$ summing to the
identity).666Unlike in the finite-dimensional setting, we cannot without loss
of generality take $\mathscr{A}$ to be all of $\mathrm{B}(\mathcal{H})$; this
is because a tracial state on $\mathscr{A}$ does not extend to a tracial state
on $\mathrm{B}(\mathcal{H})$, which is not finite. Given questions $(x,y)$,
the probability of obtaining answers $(a,b)$ is given by
$\tau(M^{x}_{a}\,M^{y}_{b})$. Thus the probability that the strategy
$\mathscr{S}$ succeeds in the game $G$ is given by

$\sum_{x,y\in\mathcal{X}}\mu(x,y)\,\sum_{a,b\in\mathcal{A}}D(x,y,a,b)\,\tau\big{(}M^{x}_{a}\,M^{y}_{b}\big{)}~{}.$

Readers who are not familiar with von Neumann algebras and tracial states may
find the finite-dimensional setting easier to understand. (No additional
difficulty is posed by the infinite-dimensional setting; we include it because
it is more general and, once one gets used to it, simpler.) When
$\mathcal{H}=\mathbb{C}^{r}$ for some dimension $r$, then we can without loss
of generality take the algebra $\mathscr{A}$ to be the set
$\mathrm{B}(\mathcal{H})$ of all bounded operators on $\mathcal{H}$ (which in
finite dimensions is simply the set of all linear operators). In this case
there is a _unique_ tracial state, the normalized trace
$\tau(X)=\frac{1}{r}\mbox{\rm tr}(X)$. In terms of strategies for nonlocal
games, this corresponds to the provers using the projective measurements that
are transposed from each other and sharing the maximally entangled state
${|\Phi\rangle}=\frac{1}{\sqrt{r}}\sum_{e=1}^{r}{|e\rangle}{|e\rangle}$. (The
transposition is because in general we have ${\langle\Phi|}A\otimes
B{|\Phi\rangle}=\frac{1}{r}\mbox{\rm tr}(AB^{T})$.) Such a strategy has the
property that if both provers receive the same question $x\in\mathcal{X}$ then
they always output the same answer $a\in\mathcal{A}$ (this is why these
strategies are called “synchronous”).

In the infinite-dimensional setting synchronous strategies give rise to
_commuting operator_ strategies: as shown in [PSS+16, Theorem 5.5], for every
synchronous strategy $\mathscr{S}=(\tau,\\{M^{x}\\})$ with Hilbert space
$\mathcal{H}$ there exist another Hilbert space $\mathcal{H}^{\prime}$, a
state ${|\psi\rangle}\in\mathcal{H}^{\prime}$, and measurements
$\\{A^{x}\\},\\{B^{x}\\}$ on $\mathcal{H}^{\prime}$ for the provers
respectively such that for all $x,y\in\mathcal{X}$ and $a,b\in\mathcal{A}$,
the operators $A^{x}_{a}$ and $B^{y}_{b}$ commute and we have

$\tau(M^{x}_{a}\,M^{y}_{b})={\langle\psi|}A^{x}_{a}\,B^{y}_{b}{|\psi\rangle}~{}.$

A consequence of the characterization $\mathsf{MIP}^{*}=\mathsf{RE}$
(specifically, of the fact that $\mathsf{MIP}^{*}$ contains undecidable
languages) is that there exists a game that can be won with probability $1$
using a (synchronous) commuting-operator strategy but tensor product
strategies (even infinite-dimensional ones) cannot succeed with probability
larger than $\frac{1}{2}$.

Synchronous strategies arise naturally when considering _synchronous games_ :
these are games where the provers must output the same answers whenever they
receive the same question (i.e. for all $x$, $D(x,x,a,b)=1$ if and only if
$a=b$). Many games studied in quantum information theory and theoretical
computer science are synchronous games; for example the games constructed in
the proof of $\mathsf{MIP}^{*}=\mathsf{RE}$ are all synchronous. The augmented
tensor code test (presented formally in Section 3) studied in this paper is
also a synchronous game.

It was shown by [PSS+16, KPS18] that if a synchronous game has a perfect
strategy (i.e. a strategy that wins with probability $1$) then it also has a
perfect synchronous strategy. Furthermore, if the former strategy is finite-
dimensional, then so is the latter synchronous strategy. This characterization
of perfect (finite-dimensional) strategies for synchronous games was recently
extended to the case of near-perfect strategies in [Vid21]: any finite-
dimensional strategy for a synchronous game $G$ that succeeds with high
probability can be well-approximated by a convex combination of finite-
dimensional synchronous strategies. In particular, results such as Theorem 1.2
for synchronous strategies extend in a natural way to general strategies.

Besides the greater generality there are several advantages to focusing on
synchronous strategies when analyzing the tensor code test. We list the three
most important, in our opinion. The first advantage is that it simplifies
notation. In the standard formulation of strategies for nonlocal games,
separate measurement operators are specified for both provers, and in the
finite-dimensional setting they are associated to separate Hilbert spaces.
With synchronous strategies there is a single Hilbert space and a single set
of measurement operators. Furthermore, in the finite-dimensional setting there
is no need to specify the state used by the provers; it is assumed that they
use _the_ maximally entangled state. (In infinite dimensions there can be
multiple non-unitarily equivalent tracial states.)

The second advantage is that it simplifies certain routine steps that
typically occur in analyses of quantum strategies. For example, an often-
repeated argument is “prover switching”: this is to argue that prover A’s
measurement operator $A^{x}_{a}$ corresponding to a question $x\in\mathcal{X}$
and answer $a\in\mathcal{A}$ can be approximately mapped to an analogous
measurement operator on prover B’s side. This allows for “cycling” of
measurement operators in the following manner:

${\langle\psi|}A^{z}_{c}\,A^{y}_{b}\,A^{x}_{a}\otimes\mathbf{1}{|\psi\rangle}\approx{\langle\psi|}A^{z}_{c}\,A^{y}_{b}\otimes
B^{x}_{a}{|\psi\rangle}\approx{\langle\psi|}A^{x}_{a}\,A^{z}_{c}\,A^{y}_{b}\otimes\mathbf{1}{|\psi\rangle}~{},$

where here the first approximation sees $A^{x}_{a}$ as acting on the state
${|\psi\rangle}$ on the right-hand side, while the second approximation sees
$B^{x}_{a}$ as acting on the state ${\langle\psi|}$ on the left-hand side.
Though fundamentally elementary, such steps can obfuscate the argument in a
proof and are tedious to verify. With synchronous strategies prover switching
comes “for free” because of the tracial property
$\tau(A^{z}_{c}\,A^{y}_{b}\,A^{x}_{a})=\tau(A^{x}_{a}\,A^{z}_{c}\,A^{y}_{b})$.

The third advantage is the operator-algebraic implications of
$\mathsf{MIP}^{*}=\mathsf{RE}$ can be still be obtained by focusing on
synchronous strategies. In fact, as shown by Dykema and Paulsen [DP16] the
connection with Connes’ Embedding Problem (CEP) arises arguably more naturally
in the synchronous setting, e.g. a negative answer to CEP is equivalent to
whether there is a nonlocal game $G$ such that the optimal success probability
with finite-dimensional synchronous strategies is strictly smaller than the
optimal success probability with infinite-dimensional synchronous strategies.

###  1.2 Proof overview

At a high level our proof follows the approach of [BFL91], and it is useful to
start by summarizing their analysis, rephrased in terms of tensor codes rather
than low-degree polynomials.

In the setting of [BFL91], we consider classical (i.e. deterministic)
strategies: the provers’ strategy is described by a “points function,”
assigning a value in $\Sigma$ to each point $u\in[n]^{m}$, and a “lines
function,” assigning a codeword of $\mathcal{C}$ to each axis-parallel line
$\ell\subset[n]^{m}$ queried in the test. From the assumption that the points
and lines functions agree at a randomly chosen point with high probability, we
would like to construct a “global” codeword of $\mathcal{C}^{\otimes m}$ that
has high agreement with the “local” points function, on average over a
uniformly random $u$ at which both are evaluated. This is done by inductively
constructing “subspace functions” defined on axis-aligned “affine subspaces”:
subsets of $[n]^{m}$ where $m-k$ coordinates have been fixed, for some $1\leq
k\leq m$. We refer to the parameter $k$ as the _dimension_ of the subspace. As
special cases, a subspace of dimension $k=0$ is a single point in $[n]^{m}$, a
subspace of dimension $k=1$ is an axis-aligned line, and a subspace with
dimension $k=m$ is the entire space $[n]^{m}$.

The induction proceeds on the dimension parameter $k$. The base case is $k=1$,
and the “global” codeword is automatically supplied by the lines function. At
each step, to construct the subspace function for a subspace $S$ of dimension
$k+1$, we pick $t$ parallel subspaces of dimension $k$ that lie within $S$,
for some large enough $t$, and compute the unique function in
$\mathcal{C}^{\otimes(k+1)}$ that interpolates them. The analysis shows that
at each stage the function constructed through interpolation has high
agreement on average with the points function and lines function. In the end,
when we reach the ambient dimension $k=m$, the subspace function we construct
is the desired global codeword.

##### Interpolation

Before delving into more detail about the analysis, we first discuss a
required property of the codes considered in this paper, which is the ability
to uniquely _interpolate_ a codeword from a few positions. Let $\mathcal{C}$
be a code with blocklength $n$ and distance $d$. Let $t=n-d+1$. The distance
property of the code implies that given $t$ coordinates
$i_{1},\ldots,i_{t}\in[n]$ and values $a_{1},\ldots,a_{t}\in\Sigma$, there
exists _at most_ one codeword $c\in\mathcal{C}$ such that $c(i_{j})=a_{j}$ for
$j\in[t]$. We say that the code $\mathcal{C}$ is _interpolable_ if for all
$i_{1},\ldots,i_{t}\in[n]$ and $a_{1},\ldots,a_{t}\in\Sigma$ there _always_
exists a codeword $c$ with the prescribed values $c(i_{j})=a_{j}$.

Interpolability is a direct generalization of the same property of
polynomials. The code $\mathcal{C}$ consisting of the evaluations of all
degree-$s$ polynomials over a finite field $\mathbb{F}$ is a code with
blocklength $|\mathbb{F}|$ and distance $|\mathbb{F}|-s$. Given $t=s+1$ points
and values, there always exists a degree $s$ polynomial interpolating through
them.

Not all codes are interpolable; for example consider a code where some of the
coordinates are always fixed to a predetermined symbol. However, a wide class
of error-correcting codes are interpolable, including all polynomial codes.

In this paper, we assume all base codes $\mathcal{C}$ are linear (meaning that
they form a subspace of a vector space over a finite field) and interpolable.
These two properties ensure that the tensor codes $\mathcal{C}^{\otimes m}$
are also linear interpolable.

##### The classical zero-error case

We return to giving an overview of the proof. To start building intuition, it
is useful to think about how to carry out the above program in a highly
simplified setting: the classical zero-error case, for $m=3$ and $d=n-1$. In
this case, we assume that we have access to a points function
$f:[n]^{m}\to\Sigma$ and lines function $g:L_{n,m}\to\mathcal{C}$ that
_perfectly_ pass the tensor code test, where $L_{n,m}$ denotes the set of
axis-parallel lines in $[n]^{m}$. Moreover, we will focus on the _final_ step
of the induction: thus, we assume that we have already constructed a set of
planes functions defined for every axis-parallel plane that are perfectly
consistent with the line and point functions. In the final step of the
induction our goal is to combine these planes functions to create a single
global codeword $h\in\mathcal{C}^{\otimes 3}$ that is consistent with the
points and lines functions.

To do this we interpolate the planes as follows. Let us label the 3
coordinates in the space $x$, $y$, and $z$, and consider planes parallel to
the $(x,y)$-plane. Each plane $S_{z}$ is specified by a value of the $z$
coordinate:

$S_{z}=\\{(x,y,z):(x,y)\in[n]^{2}\\}.$

By the induction hypothesis, for every such plane $S_{z}$ there exists a
function $g_{z}:[n]^{2}\to\Sigma$ belonging to the code $\mathcal{C}^{\otimes
2}$ that agrees with the points function. To construct a global function
$h:[n]^{3}\to\Sigma$ belonging to $\mathcal{C}^{\otimes 3}$, we pick two
distinct values $z_{1}\neq z_{2}$ and “paste” the two plane functions
$g_{z_{1}}$ and $g_{z_{2}}$ together using the interpolability of the code.
Specifically, we define $h$ to be the unique function in $\mathcal{C}^{\otimes
3}$ that interpolates between $g_{z_{1}}$ on the plane $S_{z_{1}}$ and
$g_{z_{2}}$ on the plane $S_{z_{2}}$. This interpolation is guaranteed to
exist because the code $\mathcal{C}$ (and thus $\mathcal{C}^{\otimes 3}$) is
linear interpolable.

Why is $h$ consistent with the points function? To show this we need to
consider the lines function on lines parallel to the $z$ axis. Given a point
$(x,y,z)$, let $\ell$ be the line parallel to the $z$ axis through this point,
and let $g_{\ell}$ be the associated lines function. By construction, $h$
agrees with $g_{\ell}$ at the two points $z_{1}$ and $z_{2}$. But $g_{\ell}$
and $h|_{\ell}$ (the restriction of $h$ to $\ell$) are both codewords in
$\mathcal{C}$, and hence if they agree at two points, they must agree
_everywhere_. (This is because the distance of the code $\mathcal{C}$ is
$d=n-1$.) Thus, $h$ agrees with $g_{\ell}$ at the original point $z$ as well.
By success in the test, $g_{\ell}$ in turn agrees with the points function $f$
at $(x,y,z)$, and thus, $h(x,y,z)=f(x,y,z)$. Thus, we have shown that the
global function $h$ is a codeword in $\mathcal{C}^{\otimes 3}$ and agrees with
the points function $f$ exactly.

##### Dealing with errors

To extend the sketch above to the general case, with nonzero error, requires
some modifications. At the most basic level, we may consider what happens when
we allow for deterministic classical strategies that succeed with probability
less than $1$ in the test. Such strategies may have “mislabeling” error: the
points function $f$ may be imagined to be a global codeword of
$\mathcal{C}^{\otimes 3}$ that has been corrupted at a small fraction of the
points. This type of error is handled by the analysis in [BFL91]. The main
modification to the zero-error sketch above is a careful analysis of the
probability that the pasting step produces a “good” interpolated codeword for
a randomly chosen pair of planes $S_{z_{1}},S_{z_{2}}$. This analysis makes
use of the distance property of the code together with combinatorial
properties of the point-line test itself (namely, the expansion of the
hypercube graph associated with $[n]^{m}$).

At the next level of generality, we could consider classical _randomized_
strategies. Suppose we are given a randomized strategy that succeeds in the
test with probability $1-\varepsilon$. Any randomized strategy can be modeled
by first sampling a random seed, and then playing a deterministic strategy
conditioned on the value of the seed. A success probability of $1-\varepsilon$
could have two qualitatively different underlying causes: (1) on
$O(\varepsilon)$ fraction of the seeds, the strategy uses a function which is
totally corrupted, and (2) on a large fraction of the seeds, the strategy uses
functions which are only $\varepsilon$-corrupted. An analysis of randomized
strategies could naturally proceed in a “seed-by-seed” fashion, applying the
deterministic analysis of [BFL91] to the large fraction of “good” seeds (which
are each only $\varepsilon$-corrupted), while giving up entirely on the “bad”
seeds.

Here we consider quantum strategies, which have much richer possibilities for
error. Nevertheless, we are able to preserve some intuition from the
randomized case by working with _submeasurements_ , which are quantum
measurements that do not always yield an outcome. Working with a
submeasurement allows us to distinguish two kinds of error: _consistency
error_ (the probability that a submeasurement returns a wrong outcome) and
_completeness error_ (the probability that the submeasurement fails to return
an outcome at all). Roughly speaking, the completeness error corresponds to
the probability of obtaining a “bad” seed in the randomized case, while the
consistency error corresponds to how well the strategies do on “good” seeds.

The technique of using submeasurements and managing the two types of error
separately goes back to [IV12]. That work developed a crucial tool to convert
between these two types of error called the _self-improvement lemma_ , and in
our analysis we make extensive use of a refined version of this lemma (Lemma
4.2), that in particular applies to the two-prover setting as opposed to three
provers in [IV12].

Essentially, the self-improvement lemma says the following: suppose that (a)
the provers pass the test with probability $1-\varepsilon$, and (b) there is a
complete measurement $G_{g}$ whose outcomes are codewords
$g\in\mathcal{C}^{\otimes m}$ that has consistency error $\nu$: that is, $G$
always returns an outcome, but has probability $\nu$ of producing an outcome
$g$ that disagrees with the points measurement $A^{u}_{a}$ at a random point
$u$. Then there exists an “improved” submeasurement $H_{h}$ with consistency
error $\zeta$ depending _only_ on $\varepsilon$, and with completeness error
(i.e. probability of not producing an outcome at all) of $\nu+\zeta$. Thus the
lemma says that we can always “reset” the consistency error of any measurement
we construct at intermediate points in the analysis to a universal function
$\zeta$ depending only on the provers’ success in the test, at the cost of
introducing some amount completeness error. Intuitively, one may think of the
action of the lemma as correcting $G$ on the portions of Hilbert space where
it is only mildly corrupted, while “cutting out” the portions of Hilbert space
where $G$ is too corrupted to be correctable. In some sense, this lemma is the
quantum analogue of the idea of identifying “good” and “bad” random seeds in
the classical randomized case. The proof of the lemma uses a version of
semidefinite programming duality together with the combinatorial facts used in
[BFL91].

Armed with the self-improvement lemma, we set up the following variant of the
induction loop sued in [BFL91]. We say that an affine subspace $S$ is
“$k$-aligned” if $S$ has dimension $k$ and for all $u,v\in S$, the projection
of $u,v$ to the first $m-k$ coordinates are the same. For $k$ running from $1$
to $m$, for all $k$-aligned subspaces $S$, we construct a “subspace
measurement” $\\{G^{S}_{g}\\}$ that returns a codeword
$g\in\mathcal{C}^{\otimes k}$, as follows.

  1. 1.

By the induction hypothesis, we know that there exists a measurement
$G^{S}_{g}$ for every $k$-aligned subspace $S$, which has (on average over the
the subspaces $S$) consistency error $\delta(k)$ with the points measurement.
(For the base case $k=1$, this is the lines measurement from the provers’
strategy).

  2. 2.

We apply the self-improvement lemma to these measurements, yielding
submeasurements $\hat{G}^{S}_{g}$ that have (on average) consistency error
$\zeta$ independent of $\delta(k)$, and completeness error
$\kappa(k)=\delta(k)+\zeta$.

  3. 3.

For each $(k+1)$-aligned subspace $S^{\prime}$, we construct a pasted
submeasurement $G^{S^{\prime}}_{g^{\prime}}$, by performing a quantum version
of the classical interpolation argument: we define the pasted submeasurement
by sequentially measuring several parallel $k$-aligned subspaces $S\subseteq
S^{\prime}$ and interpolate the resulting outcomes. This pasted submeasurement
has (on average) consistency error slightly worse than $\zeta$, and
completeness error which is slightly worse than $\kappa(k)$. It is at this
step that it is crucial to treat the two types of error separately: in
particular, we need the consistency error to be low to ensure that the
interpolation produces a good result.

  4. 4.

We convert the resulting submeasurement into a full measurement, by assigning
a random outcome whenever the submeasurement fails to yield an outcome. This
measurement will have (on average) consistency error $\delta(k+1)$ which is
larger than $\delta(k)$ by some additive factor.

At the end of the loop, when $k=m$, we obtain a single measurement that
returns a global codeword as desired.

##### The subcube commutation test

The “augmented” qualifier of the tensor code test in Theorem 1.2 refers to an
additional component called the “subcube commutation test”, which is described
in detail in Section 3. This additional test is not needed in the classical
setting, but appears necessary in the noncommutative setting. The purpose of
this test is to certify that the points measurements used by the provers
approximately commute on average over all pairs of points
$x,y\in[n]^{m}$—something which is automatically true in the classical case.
This is done by asking one prover to report values for a pair randomly chosen
points $(u,v)$ from a randomly chosen _subcube_ , asking the other prover to
report values for either $u$ or $v$ (chosen randomly), and checking
consistency between their reported values. A subcube is a subset of points in
$[n]^{m}$ that all share the same values in the last $k$ coordinates for some
$1\leq k\leq n-1$. The reason for choosing a pair of points uniformly at
random in a subcube of this form, as opposed to a pair of points uniformly at
random in the entire cube, biases their distribution in a way that is
appropriate for the induction.

The (approximate) commutation guarantee plays an important role in our
analysis of the tensor code test, and it is an interesting question whether it
is truly necessary to test it directly with the subcube commutation test;
might it not automatically follow from success in the axis-parallel lines
test? An interesting contrast can be drawn to the Magic Square game [Mer90,
Per90, Ara02], in which questions are either cells or axis-parallel lines in a
$3\times 3$ square grid. This has the same question distribution as the axis-
parallel line-point test over $[3]^{2}$. For the Magic Square game, “points”
measurements along the same axis-parallel “line” commute, but points that are
not axis-aligned do _not_ commute: indeed, for the perfect strategy, they
anticommute.

###  1.3 Future directions

This paper has several motivations. The first is to provide a complete proof
of quantum soundness of the tensor code test (and thus the low individual
degree test), which as already mentioned plays a central role in the result
$\mathsf{MIP}^{*}=\mathsf{RE}$.

Second, although $\mathsf{MIP}^{*}=\mathsf{RE}$ is ostensibly a complexity-
theoretic result about the power of quantum multiprover interactive proof
systems, it also provides negative answers to seemingly-unrelated questions in
mathematical physics and operator algebras, namely Tsirelson’s Problem and
Connes’ Embedding Problem. Unfortunately there is still a large gap between
the methods used to prove $\mathsf{MIP}^{*}=\mathsf{RE}$ (which combine
techniques from theoretical computer science, complexity theory, and quantum
information theory) and the traditional methods to study the problems of
Tsirelson and Connes in functional analysis. We believe that the simpler
analysis of the tensor code test and its presentation in the synchronous
strategies framework will help researchers in pure mathematics as well as
theoretical computer science gain a better understanding of
$\mathsf{MIP}^{*}=\mathsf{RE}$. A simpler, more direct proof may lead to the
resolution of other long-standing open problems such as the existence of a
non-hyperlinear group [CLP15].

Third, we believe that the study of locally testable codes in the quantum
setting is a subject that is interesting in its own right. At its core, the
quantum soundness of tensor codes is about robustly deducing a global
“consistency” property of a set of operators on a Hilbert space that do not
necessarily commute. This hints at a more general study of _noncommutative
property testing_ , which could combine questions from property testing in
theoretical computer science and questions from functional analysis and
operator algebras. The field of property testing, which studies how global
properties of combinatorial objects such as Boolean functions and graphs can
be robustly detected by only examining local views of the object, was
initially motivated by the $\mathsf{MIP}=\mathsf{NEXP}$ and PCP theorems.
Similarly, $\mathsf{MIP}^{*}=\mathsf{RE}$ and its mathematical consequences
suggest the occurrence of “local-to-global” phenomena in the noncommutative
setting that seem worth studying independently of interactive proofs and
complexity theory.

We conclude with an open question. The complexity of quantum multiprover
interactive proofs with _infinite-dimensional commuting operator_ strategies,
i.e. the class $\mathsf{MIP}^{co}$ (where $co$ stands for “commuting
operator”), remains unknown. It is natural to conjecture that
$\mathsf{MIP}^{co}=\mathsf{coRE}$, as this would nicely complement the
$\mathsf{MIP}^{*}=\mathsf{RE}$ result.777Note that the $co$ on either side of
$\mathsf{MIP}^{co}=\mathsf{coRE}$ refer to different things! The analysis of
the soundness of the tensor code test for infinite-dimensional strategies
establishes a first step towards proving this conjecture.

#### Acknowledgments

We thank the anonymous referees for their feedback. We thank William Slofstra
and Vern Paulsen for their explanations regarding synchronous strategies.

##  2 Preliminaries

We write $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. For positive integers
$a,b,c,\ldots$, that we treat as growing to infinity, we write
$\mathrm{poly}(a,b,c,\ldots)$ to denote a function $C(a+b+c\cdots)^{C}$ for
some universal constant $C\geq 1$. For nonnegative real numbers
$0\leq\alpha,\beta,\gamma,\ldots<1$ that we treat as going to $0$, we write
$\mathrm{poly}(\alpha,\beta,\gamma,\ldots)$ to denote a function
$C(\alpha^{1/C}+\beta^{1/C}+\gamma^{1/C})$ for some universal constant $C\geq
1$. In either case, the universal constant $C$ can vary each time the
$\mathrm{poly}(\cdot)$ notation is used.

For a finite set $S$, we write $x\sim S$ to indicate that $x$ is sampled from
$S$ according to some distribution specified by context (usually the uniform
distribution). For an event $E$ in a probability space, we write
$\mathbb{I}[E]$ to denote the indicator for the event $E$.

###  2.1 Algebras, tracial states, and norms

Let $\mathcal{H}$ be a (separable) Hilbert space and let
$\mathrm{B}(\mathcal{H})$ denote the set of bounded linear operators on
$\mathcal{H}$. We write $\mathbf{1}_{\mathcal{H}}$ to denote the identity
operator on $\mathcal{H}$ (and simply write $\mathbf{1}$ when the Hilbert
space is clear from context).

A von Neumann algebra on a Hilbert space $\mathcal{H}$ is a unital
$*$-subalgebra of bounded operators $\mathrm{B}(\mathcal{H})$ that is closed
in the _weak operator topology_. Let
$\mathscr{A}\subseteq\mathrm{B}(\mathcal{H})$ denote a von Neumann algebra on
$\mathcal{H}$. We say that a positive linear functional
$\tau:\mathscr{A}\to\mathbb{C}$ is

  * •

_Unital_ if $\tau(\mathbf{1})=1$ ;

  * •

_Normal_ if there exists a positive trace class888An operator
$A\in\mathrm{B}(\mathcal{H})$ is _trace class_ if the trace of $A$ is well-
defined; i.e. for all orthonormal bases $\\{{|e_{k}\rangle}\\}$ for
$\mathcal{H}$, the quantity $\sum_{k}{\langle e_{k}|}A{|e_{k}\rangle}$ is
well-defined and independent of the choice of basis. operator $A$ such that
for all $X\in\mathscr{A}$, $\tau(X)=\mbox{\rm tr}(XA)$ ;

  * •

_Tracial_ if for all $A,B\in\mathscr{A}$, we have $\tau(AB)=\tau(BA)$ ;

In this paper, $\tau$ will always represent a positive linear functional that
is tracial, normal, and unital. We call such functionals a _normal tracial
state_. For brevity we often drop the “normal” qualifier.

If $\mathcal{H}$ is finite dimensional (i.e. isomorphic to $\mathbb{C}^{r}$),
then we will without loss of generality take the algebra to be
$\mathrm{B}(\mathcal{H})$. There is a unique tracial state on
$\mathrm{B}(\mathcal{H})$ which is the _normalized trace_ :

$\tau(A)=\frac{1}{r}\mbox{\rm tr}(A).$

For a more comprehensive reference on von Neumann algebras, we refer the
reader to [Bla06].

We record some basic properties of tracial states. First, the map
$(A,B)\mapsto\tau(A^{*}B)$ is a semi-inner product and in particular satisfies
the Cauchy-Schwarz inequality, i.e.

$|\tau(A^{*}B)|^{2}\leq\tau(A^{*}A)\,\tau(B^{*}B).$

Second, tracial states give rise to a seminorm on $\mathscr{A}$: we define the
_$\tau$ -norm_ of an operator $A\in\mathscr{A}$ to be

$\|A\|_{\tau}=\sqrt{\tau(A^{*}A)}=\sqrt{\tau(AA^{*})}.$

The $\|\cdot\|_{\tau}$ norm satisfies the triangle inequality: i.e.,
$\|A+B\|_{\tau}\leq\|A\|_{\tau}+\|B\|_{\tau}$. If $\mathcal{H}$ is finite-
dimensional, then $\tau$-norm is the normalized Frobenius norm.

More generally, tracial states give rise to $p$-seminorms for $1\leq p<\infty$
via $\|A\|_{p}=\tau(|A|^{p})^{1/p}$, where for all $A\in\mathscr{A}$, the
operator absolute value $|A|$ denotes $(A^{*}A)^{1/2}$. These $p$-seminorms
satisfy triangle and Hölder inequalities (see [PX03] for an in-depth
discussion of these norms and noncommutative $L_{p}$ spaces); we record some
special cases here.

######  Proposition 2.1 (Triangle and Hölder inequalities).

Let $\tau$ be a tracial state on a von Neumann algebra $\mathscr{A}$, and let
$A,B\in\mathscr{A}$. Then

  1. 1.

$|\tau(A)|\leq\tau(|A|)$ .

  2. 2.

(Hölder inequality 1)
$\tau\left(\left|{AB}\right|\right)\leq\left\|A\right\|_{\tau}\cdot\left\|B\right\|_{\tau}$
.

  3. 3.

(Hölder inequality 2)
$\tau\left(\left|{AB}\right|\right)\leq\left\|A\right\|\cdot\tau\left(\left|{B}\right|\right)$
.

  4. 4.

(Triangle inequality for $1$-norm) $\tau(|A+B|)\leq\tau(|A|)+\tau(|B|)$.

###### Proof.

The proof of the first item is as follows. By the polar decomposition, there
exists a partial isometry $U\in\mathscr{A}$ such that $A=U|A|$. Then by
Cauchy-Schwarz,

$\displaystyle|\tau(A)|=|\tau(U|A|)|=|\tau(|A|^{1/2}U|A|^{1/2})|\leq\sqrt{\tau(|A|^{1/2}U^{*}U|A|^{1/2})\tau(|A|)}=\tau(|A|).$

The proof of the first Hölder inequality is as follows. By the polar
decomposition, there exists a partial isometry $U\in\mathscr{A}$ such that
$|AB|=UAB$. Then

$\displaystyle\tau\left(\left|{AB}\right|\right)=|\tau(UAB)|\leq\sqrt{\tau\left(A^{*}U^{*}UA\right)\cdot\tau\left(B^{*}B\right)}=\left\|A\right\|_{\tau}\cdot\left\|B\right\|_{\tau}$

where we used Cauchy-Schwarz and that $U$ is a partial isometry.

The proof of the second Hölder inequality is as follows. Let $|AB|=UAB$ and
$B=V|B|$ for partial isometries $U,V\in\mathscr{A}$. Then

$\displaystyle\tau\left(\left|{AB}\right|\right)=|\tau(UAV|B|)|=|\tau(\left|{B}\right|^{1/2}UAV\left|{B}\right|^{1/2})|\leq\sqrt{\tau\left(\left|{B}\right|^{1/2}UAA^{*}U^{*}\left|{B}\right|^{1/2}\right)\cdot\tau\left(|B|\right)}$

where we used the cyclicity of the trace and Cauchy-Schwarz. Since
$AA^{*}\leq\left\|AA^{*}\right\|\mathbf{1}$, we have that this is at most

$\displaystyle\sqrt{\tau\left(\left|{B}\right|^{1/2}(\left\|AA^{*}\right\|\cdot\mathbf{1})\left|{B}\right|^{1/2}\right)\cdot\tau\left(|B|\right)}=\left\|A\right\|\cdot\tau\left(|B|\right)$

where we use that $\sqrt{\left\|AA^{*}\right\|}=\left\|A\right\|$.

The proof of the triangle inequality is as follows. By the polar
decomposition, there exists a partial isometry $U\in\mathscr{A}$ such that
$|A+B|=U(A+B)$. Therefore

$\displaystyle\tau(|A+B|)=|\tau(U(A+B))|=|\tau(UA)+\tau(UB)|\leq|\tau(UA)|+|\tau(UB)|\leq\tau(|A|)+\tau(|B|)$

where the first equality follows from the positivity of $|A+B|$ and the last
inequality follows from the second Hölder inequality. ∎

###  2.2 Measurements and distance measures on them

Let $M=\\{M_{a}\\}_{a\in\mathcal{A}}$ and $N=\\{N_{a}\\}_{a\in\mathcal{A}}$
denote sets of operators, indexed by a finite set $\mathcal{A}$, in a von
Neumann algebra $\mathscr{A}$ with trace $\tau$. We measure the distance
between $M$ and $N$, denoted by $\|M-N\|_{\tau}$, as

$\|M-N\|_{\tau}=\sqrt{\sum_{a\in\mathcal{A}}\left\|M_{a}-N_{a}\right\|^{2}_{\tau}}\;.$

We say that $M$ is _$\delta$ -close_ to $N$, denoted by
$M_{a}\approx_{\delta}N_{a}$, if $\|M-N\|_{\tau}\leq\delta$.

A _submeasurement on $\mathcal{H}$ with answer/outcome set $\mathcal{A}$_ is a
set of positive operators $\\{M_{a}\\}_{a\in\mathcal{A}}$ such that
$\sum_{a\in\mathcal{A}}M_{a}\leq\mathbf{1}$. We say that
$\\{M_{a}\\}_{a\in\mathcal{A}}$ is a _measurement_ if
$\sum_{a}M_{a}=\mathbf{1}$. A _projective (sub)measurement_ is a
(sub)measurement such that each element $M_{a}$ is a projection. To denote
“data processed” measurements, i.e., apply a function
$f:\mathcal{A}\to\mathcal{B}$ to the outcome of a measurement, we use the
following notation: $M_{[f]}$ denotes the (sub)measurement with elements

$M_{[f\mid b]}=\sum_{a:f(a)=b}M_{a}$

for all $b\in\mathcal{B}$. As an example, suppose $\mathcal{A}=\\{0,1\\}^{n}$
and $\mathcal{B}=\\{0,1\\}$. Then we write $M_{[a\mapsto a_{i}]}$ to denote
the processed measurement that measures a string $a$, and then returns the
$i$-th bit of $a$. To refer to the element of $M_{[a\mapsto a_{i}]}$
corresponding to outcome $b\in\\{0,1\\}$, we write $M_{[a\mapsto a_{i}\mid
b]}$. For a predicate $P:\mathcal{A}\to\\{0,1\\}$, we also use the notation

$M_{[a:P(a)]}=\sum_{a:P(a)=1}M_{a}~{}.$

For example, the operator $M_{[a:f(a)\neq b]}$ denotes the sum over all
$M_{a}$ such that $f(a)\neq b$.

Throughout this paper (sub)measurements are often indexed by a finite set
$\mathcal{X}$, and the elements in the set $\mathcal{X}$ are generally drawn
from a distribution $\mu$. The set $\mathcal{X}$ is typically called a
_question set_ and $\mu$ is typically called a _question distribution_ ,
because these will correspond to questions that are sampled in a nonlocal game
such as the tensor codes test. Questions appear as superscripts and answers
appear as subscripts of a measurement operator; for example, $M^{x}_{a}$
denotes the measurement operator corresponding to question $x$ and answer $a$.

We introduce two important distance measures between (sub)measurements that
will be used throughout this paper. We fix a question set $\mathcal{X}$, a
question distribution $\mu$, and an answer set $\mathcal{A}$. Let
$M=\\{M^{x}\\}_{x}$ and $N=\\{N^{x}\\}_{x}$ denote two sets of
submeasurements, where each $M^{x}=\\{M^{x}_{a}\\}_{a}$ and
$N^{x}=\\{N^{x}_{a}\\}_{a}$.

The first distance measure we define is called _consistency_. We say that $M$
and $N$ are _$\delta$ -consistent_ if

$\operatorname*{\mathbb{E}}_{x\sim\mu}\sum_{\begin{subarray}{c}a,b\in\mathcal{A}:\\\
a\neq b\end{subarray}}\tau(M_{a}^{x}\,N_{b}^{x})\leq\delta\;.$

We also refer to the quantity on the left-hand side as the _inconsistency_
between $M$ and $N$. So, saying that $M$ and $N$ are $\delta$-consistent is
equivalent to saying that the inconsistency of $M$ and $N$ is at most
$\delta$. When the question set $\mathcal{X}$, question distribution $\mu$,
and answer set $\mathcal{A}$ are clear from context, we write
$M_{a}\simeq_{\delta}N_{a}$ to denote that $M$ and $N$ are
$\delta$-consistent. Observe that in case $M$ and $N$ are measurements then
$M$ and $N$ are $\delta$-consistent if and only if

$\operatorname*{\mathbb{E}}_{x\sim\mu}\sum_{\begin{subarray}{c}a\in\mathcal{A}\end{subarray}}\tau(M_{a}^{x}\,N_{a}^{x})\geq
1-\delta\;.$

The second distance measure we introduce is called _closeness_. We say that
sets $M,N$ of (sub)measurements are _$\delta$ -close_ if

$\sqrt{\operatorname*{\mathbb{E}}_{x\sim\mu}\sum_{a}\|M^{x}_{a}-N^{x}_{a}\|_{\tau}^{2}}\leq\delta.$

Similarly, when $\mathcal{X},\mathcal{A},\mu$ are clear from context, we write
$M_{a}^{x}\approx_{\delta}N_{a}^{x}$ to denote that $M^{x}$ and $N^{x}$ are
$\delta$-close on average over $x\sim\mu$. Observe that this notion of
closeness is also well-defined when the operators $M_{a}^{x}$, $N_{a}^{x}$ are
not necessarily positive. Thus we will also write
$M_{a}^{x}\approx_{\delta}N_{a}^{x}$ to denote closeness of arbitrary operator
sets that are indexed by question and answer sets $\mathcal{X},\mathcal{A}$.

####  2.2.1 Utility lemmas about consistency and closeness of measurements

We now establish several utility lemmas concerning consistency, closeness, and
measurements. In what follows, we let $\mathcal{X}$ denote a finite question
set, $\mu$ a distribution over $\mathcal{X}$, and $\mathcal{A}$ a finite
answer set. All expectations are over $x$ sampled from $\mu$.

######  Proposition 2.2 (Cauchy-Schwarz for operator sets).

Let $M=\\{M_{a}\\}_{a\in\mathcal{A}}$ and $N=\\{N_{a}\\}_{a\in\mathcal{A}}$
denote sets of operators (not necessarily submeasurements). Then

$\Big{|}\sum_{a\in\mathcal{A}}\tau(M_{a}\cdot
N_{a})\Big{|}^{2}\leq\Big{(}\sum_{a\in\mathcal{A}}\|M_{a}\|_{\tau}^{2}\Big{)}\cdot\Big{(}\sum_{a\in\mathcal{A}}\|N_{a}\|_{\tau}^{2}\Big{)}\;.$

###### Proof.

Applying Cauchy-Schwarz twice,

$\displaystyle\Big{|}\sum_{a\in\mathcal{A}}\tau(M_{a}\cdot
N_{a})\Big{|}\leq\sum_{a\in\mathcal{A}}\Big{|}\tau(M_{a}\cdot N_{a})\Big{|}$
$\displaystyle\leq\sum_{a\in\mathcal{A}}\sqrt{\tau(M_{a}M_{a}^{*})\tau(N_{a}^{*}N_{a})}$
$\displaystyle=\sum_{a\in\mathcal{A}}\|M_{a}\|_{\tau}\|N_{a}\|_{\tau}\leq\sqrt{\sum_{a\in\mathcal{A}}\|M_{a}\|_{\tau}^{2}}\cdot\sqrt{\sum_{a\in\mathcal{A}}\|N_{a}\|_{\tau}^{2}}.$

The proposition follows by squaring both sides. ∎

######  Corollary 2.3.

Let $\\{M^{x}_{a}\\}$ and $\\{N^{x}_{a}\\}$ be sets of operators indexed by
both $\mathcal{X}$ and $\mathcal{A}$. Then

$\Big{|}\operatorname*{\mathbb{E}}_{x}\sum_{a\in\mathcal{A}}\tau(M_{a}^{x}\cdot
N_{a}^{x})\Big{|}^{2}\leq\Big{(}\operatorname*{\mathbb{E}}_{x}\sum_{a\in\mathcal{A}}\|M_{a}^{x}\|_{\tau}^{2}\Big{)}\cdot\Big{(}\operatorname*{\mathbb{E}}_{x}\sum_{a\in\mathcal{A}}\|N_{a}^{x}\|_{\tau}^{2}\Big{)}$

.

###### Proof.

We apply Cauchy-Schwarz twice:

$\displaystyle\Big{|}\operatorname*{\mathbb{E}}_{x}\sum_{a\in\mathcal{A}}\tau(M_{a}^{x}\cdot
N_{a}^{x})\Big{|}^{2}$
$\displaystyle\leq\Big{(}\operatorname*{\mathbb{E}}_{x}\Big{|}\sum_{a\in\mathcal{A}}\tau(M_{a}^{x}\cdot
N_{a}^{x})\Big{|}\Big{)}^{2}$
$\displaystyle\leq\Big{(}\operatorname*{\mathbb{E}}_{x}\sqrt{\sum_{a\in\mathcal{A}}\|M^{x}_{a}\|_{\tau}^{2}}\cdot\sqrt{\sum_{a\in\mathcal{A}}\|N^{x}_{a}\|_{\tau}^{2}}\Big{)}^{2}$
$\displaystyle\leq\Big{(}\operatorname*{\mathbb{E}}_{x}\sum_{a\in\mathcal{A}}\|M_{a}^{x}\|_{\tau}^{2}\Big{)}\cdot\Big{(}\operatorname*{\mathbb{E}}_{x}\sum_{a\in\mathcal{A}}\|N_{a}^{x}\|_{\tau}^{2}\Big{)}~{}.$

∎

######  Proposition 2.4 (Data processing inequality for consistency).

Let $M^{x}=\\{M_{a}^{x}\\}$ and $N^{x}=\\{N_{a}^{x}\\}$ be submeasurements
with outcomes in $\mathcal{A}$ such that $M_{a}^{x}\simeq_{\delta}N_{a}^{x}$
on average over $x$. Let $f:\mathcal{A}\to\mathcal{B}$. Then

$M^{x}_{[f\mid b]}\simeq_{\delta}N^{x}_{[f\mid b]}$

on average over $x$ where the answer summation is over $b\in\mathcal{B}$.

###### Proof.

$\operatorname*{\mathbb{E}}_{x}\sum_{b\neq
b^{\prime}\in\mathcal{B}}\tau(M^{x}_{[f\mid b]}N^{x}_{[f\mid
b^{\prime}]})=\operatorname*{\mathbb{E}}_{x}\sum_{\begin{subarray}{c}b\neq
b^{\prime}\in\mathcal{B}\\\ a,a^{\prime}\in\mathcal{A}\\\ f(a)=b\\\
f(a^{\prime})=b^{\prime}\end{subarray}}\tau(M_{a}^{x}N^{x}_{a^{\prime}})\leq\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
a^{\prime}\in\mathcal{A}}\tau(M_{a}^{x}N^{x}_{a^{\prime}})\leq\delta.\qed$

######  Proposition 2.5 (Consistency to closeness).

Let $M^{x}=\\{M_{a}^{x}\\}$ and $N^{x}=\\{N_{a}^{x}\\}$ be measurements with
outcomes in $\mathcal{A}$ such that $M_{a}^{x}\simeq_{\delta}N_{a}^{x}$ on
average over $x$. Then $M_{a}^{x}\approx_{\sqrt{2\delta}}N_{a}^{x}$ on average
over $x$.

###### Proof.

$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\|M_{a}^{x}-N_{a}^{x}\|_{\tau}^{2}}$
$\displaystyle=\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau((M_{a}^{x}-N_{a}^{x})^{2})}$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(M_{a}^{x}+N_{a}^{x}-2M_{a}^{x}N_{a}^{x})}$
$\displaystyle=\sqrt{\operatorname*{\mathbb{E}}_{x}2-2\sum_{a}\tau(M_{a}^{x}N_{a}^{x})}$
$\displaystyle=\sqrt{2\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(M_{a}^{x}(\mathbf{1}-N_{a}^{x}))}$
$\displaystyle\leq\sqrt{2\delta}.$

The second line follows because $M_{a}^{x}-(M_{a}^{x})^{2}\geq 0$ as
$\\{M_{a}^{x}\\}$ are measurements. ∎

######  Proposition 2.6 (Closeness to consistency).

Let $M^{x}=\\{M_{a}^{x}\\}$ be projective submeasurements and let
$N^{x}=\\{N_{a}^{x}\\}_{a\in\mathcal{A}}$ be submeasurements with outcomes in
$\mathcal{A}$. Suppose that $M_{a}^{x}\approx_{\delta}N_{a}^{x}$ on average
over $x$. Then $M_{a}^{x}\simeq_{\delta}N_{a}^{x}$ on average over $x$.

###### Proof.

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau(M^{x}_{a}N^{x}_{b})$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(M_{a}^{x}(\mathbf{1}-N_{a}^{x}))$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(M_{a}^{x}(M_{a}^{x}-N_{a}^{x}))$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau((M_{a}^{x})^{2})}\cdot\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau((M_{a}^{x}-N_{a}^{x})(M_{a}^{x}-N_{a}^{x})^{*})}$
(by Cauchy-Schwarz) $\displaystyle\leq\delta$

where we used that $\sum_{a}\tau((M_{a}^{x})^{2})\leq 1$. ∎

######  Proposition 2.7.

Let $A^{x}=\\{A_{a}^{x}\\}$ and $B^{x}=\\{B_{a}^{x}\\}$ be two sets of
operators indexed by subscripts in $\mathcal{A}$ such that
$A^{x}_{a}\approx_{\delta}B^{x}_{a}$. Let $M^{x}_{a}$ be operators satisfying
$\sum_{a}M^{x}_{a}{(M^{x}_{a})}^{*}\leq\mathbf{1}$ for all $x$. Then

$\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(M^{x}_{a}A^{x}_{a}\right)\approx_{\delta}\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(M^{x}_{a}B^{x}_{a}\right).$

In particular, if $C^{x}=\\{C^{x}_{a}\\}$ are submeasurements, then

$\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(C^{x}_{a}A^{x}_{a})\approx_{\delta}\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(C^{x}_{a}B^{x}_{a}).$

###### Proof.

Via Cauchy-Schwarz we have:

$\Big{|}\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(M^{x}_{a}(A^{x}_{a}-B^{x}_{a}))\Big{|}\leq\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau(M^{x}_{a}{(M^{x}_{a})}^{*})}\cdot\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\|A^{x}_{a}-B^{x}_{a}\|_{\tau}^{2}}\leq\delta.\qed$

######  Proposition 2.8.

Let $M=\\{M_{a}\\}_{a\in\mathcal{A}},N=\\{N_{a}\\}_{a\in\mathcal{A}}$ be sets
of operators (not necessarily measurements), and let
$R=\\{R_{b}\\}_{b\in\mathcal{B}}$ be a set of operators such that
$\sum_{b}R_{b}^{*}R_{b}\leq\mathbf{1}$. Suppose that
$M_{a}\approx_{\delta}N_{a}$. Then $R_{b}M_{a}\approx_{\delta}R_{b}N_{a}$
where the answer summation is over $(a,b)\in\mathcal{A}\times\mathcal{B}$.
Similarly, if $\sum_{b}R_{b}R_{b}^{*}\leq\mathbf{1}$, we have
$M_{a}R_{b}\approx_{\delta}N_{a}R_{b}$.

###### Proof.

We prove the approximation $R_{b}M_{a}\approx_{\delta}R_{b}N_{a}$:

$\displaystyle\sum_{a\in\mathcal{A},b\in\mathcal{B}}\|R_{b}(M_{a}-N_{a})\|_{\tau}^{2}$
$\displaystyle=\sum_{a\in\mathcal{A},b\in\mathcal{B}}\tau\Big{(}(M_{a}-N_{a})^{*}R_{b}^{*}R_{b}(M_{a}-N_{a})\Big{)}$
$\displaystyle=\sum_{a}\tau\Big{(}(M_{a}-N_{a})^{*}\Big{(}\sum_{b}R_{b}^{*}R_{b}\Big{)}(M_{a}-N_{a})\Big{)}$
$\displaystyle\leq\sum_{a}\tau\Big{(}(M_{a}-N_{a})^{*}(M_{a}-N_{a})\Big{)}$
$\displaystyle=\sum_{a}\|M_{a}-N_{a}\|_{\tau}^{2}$
$\displaystyle\leq\delta^{2}.$

where in the first inequality we used the assumption that
$\sum_{b}R_{b}^{*}R_{b}\leq\mathbf{1}$ and positivity of the trace. The proof
for the approximation $M_{a}R_{b}\approx_{\delta}N_{a}R_{b}$ follows
similarly. ∎

######  Proposition 2.9 (Transfering “$\simeq$” using “$\approx$”).

Let $\\{A^{x}_{a}\\}$ and $\\{B^{x}_{a}\\}$ be measurements, and let
$\\{C^{x}_{a}\\}$ be a submeasurement. Suppose that
$A^{x}_{a}\simeq_{\delta}C^{x}_{a}$ and
$A^{x}_{a}\approx_{\varepsilon}B^{x}_{a}$. Then
$B^{x}_{a}\simeq_{\delta+\varepsilon}C^{x}_{a}$.

###### Proof.

Let $C^{x}=\sum_{a}C^{x}_{a}$ and $C=\operatorname*{\mathbb{E}}_{x}C^{x}$.
First, we can rewrite the inconsistency between $\\{A^{x}_{a}\\}$ and
$\\{C^{x}_{a}\\}$ as

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\left(A^{x}_{a}C^{x}_{b}\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(A^{x}_{a}(C^{x}-C^{x}_{a})\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{x}\tau\left(C^{x}\right)-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(A^{x}_{a}C^{x}_{a}\right)$
(because $\\{A^{x}_{a}\\}$ is a measurement)
$\displaystyle=\tau\left(C\right)-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(A^{x}_{a}C^{x}_{a}\right).$

Likewise, we can rewrite the inconsistency between $\\{B^{x}_{a}\\}$ and
$\\{C^{x}_{a}\\}$ as

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\left(B^{x}_{a}C^{x}_{b}\right)$
$\displaystyle=\tau\left(C\right)-\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(B^{x}_{a}C^{x}_{a}\right).$

We want to show that the inconsistency between $B$ and $C$ is close to the
inconsistency between $A$ and $B$. In particular, we claim that

$\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\left(A^{x}_{a}C^{x}_{b}\right)\approx_{\varepsilon}\operatorname*{\mathbb{E}}_{x}\sum_{a\neq
b}\tau\left(B^{x}_{a}C^{x}_{b}\right).$

To show this, we bound the magnitude of the difference using Cauchy-Schwarz.

$\displaystyle\Big{|}\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left((A^{x}_{a}-B^{x}_{a})C^{x}_{a}\right)\Big{|}$
$\displaystyle\leq\;\;$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left({(A^{x}_{a}-B^{x}_{a})}^{2}\right)}\cdot\sqrt{\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left({(C^{x}_{a})}^{2}\right)}$
$\displaystyle\leq$ $\displaystyle\varepsilon\cdot 1.$ (because
$\\{C^{x}_{a}\\}$ is a submeasurement)

This completes the proof. ∎

The following fact is useful for translating between statements about
consistency and closeness between submeasurements.

######  Proposition 2.10.

Let $\\{A^{x}_{a}\\}$ be a submeasurement and let $\\{B^{x}_{a}\\}$ be a
measurement such that on average over $x$,

$A^{x}_{a}\simeq_{\gamma}B^{x}_{a}.$

Then

$\displaystyle
A^{x}_{a}\approx_{\sqrt{\gamma}}A^{x}_{a}B^{x}_{a}\approx_{\sqrt{\gamma}}A^{x}B^{x}_{a},$
(1)

where $A^{x}=\sum_{a}A^{x}_{a}$. As a result, by the triangle inequality,

$A^{x}_{a}\approx_{2\sqrt{\gamma}}A^{x}B^{x}_{a}$

###### Proof.

We establish the first approximation in Eq. 1:

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(\bigl{(}A^{x}_{a}(\mathbf{1}-B^{x}_{a})\bigr{)}^{*}(A^{x}_{a}(\mathbf{1}-B^{x}_{a}))\right)=$
$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left({(A^{x}_{a})}^{2}{(\mathbf{1}-B^{x}_{a})}^{2}\right)$
$\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left(A^{x}_{a}(\mathbf{1}-B^{x}_{a})\right)$
$\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{\begin{subarray}{c}a,b:\\\
b\neq a\end{subarray}}\tau\left(A^{x}_{a}B^{x}_{b}\right)$ $\displaystyle\leq$
$\displaystyle\gamma.$

The first equality uses that positive operators are self-adjoint and follows
from cyclicity of the trace. The first inequality folows from the fact that
${(A^{x}_{a})}^{2}\leq A^{x}_{a}$,
${(\mathbf{1}-B^{x}_{a})}^{2}\leq\mathbf{1}-B^{x}_{a}$, and positicity of the
trace. The last line follows from the assumption of consistency between the
$A$ and $B$ (sub)measurements.

To establish the second approximation in Eq. 1, we compute the difference:

$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left({(A^{x}-A^{x}_{a})}^{2}{(B^{x}_{a})}^{2}\right)\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a}\tau\left((A^{x}-A^{x}_{a})B^{x}_{a}\right)$
$\displaystyle=$ $\displaystyle\operatorname*{\mathbb{E}}_{x}\sum_{a,b:a\neq
b}\tau\left(A^{x}_{b}B^{x}_{a}\right)$ $\displaystyle\leq$
$\displaystyle\gamma.$

The first inequality follows from the fact that ${(A^{x}-A^{x}_{a})}^{2}\leq
A^{x}-A^{x}_{a}$ and ${(B^{x}_{a})}^{2}\leq B^{x}_{a}$, and the last
inequality follows from the consistency between the $A$ and $B$
(sub)measurements. ∎

The following proposition states that, if a collection of measurements
approximately pairwise commute, then they can also be approximately commuted
within longer products of operators.

######  Proposition 2.11.

For all $x\in\mathcal{X}$ let $A^{x}=\\{A^{x}_{a}\\}$ denote a submeasurement
with answer set $\mathcal{A}$. Furthermore suppose that on average over
$x,y\sim\mathcal{X}$, it holds that

$A^{x}_{a}A^{y}_{b}\approx_{\varepsilon}A^{y}_{b}A^{x}_{a}\;.$ (2)

Then for all $k\in\mathbb{N}$ it holds that on average over $x\sim\mathcal{X}$
and uniformly random $s\sim\mathcal{X}^{k}$,

$P^{s}_{\vec{a}}\,A^{x}_{b}\approx_{k\varepsilon}A^{x}_{b}\,P^{s}_{\vec{a}}$
(3)

where for all integers $k\geq 1$, vectors $\vec{a}\in\mathcal{A}^{k}$, and
sequences $s\in\mathcal{X}^{k}$ we define

$P^{s}_{\vec{a}}=A^{s_{1}}_{{a}_{1}}\cdot A^{s_{2}}_{{a}_{2}}\cdots
A^{s_{k}}_{{a}_{k}}.$

###### Proof.

We prove Equation 3 by induction on $k$. The base case for $k=1$ follows from
the assumption of the approximate commutativity of the $A^{x}$ measurements.
Assuming the inductive hypothesis holds for some $k\geq 1$, we now prove it
for $k+1$: let $s\in\mathcal{X}^{k},t\in\mathcal{X}$. We can treat $(s,t)$ as
a sequence of length $k+1$. Then for all $x\in\mathcal{X}$, we have

$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\left\|P^{s,t}_{\vec{a},b}A^{x}_{c}-A^{x}_{c}P^{s,t}_{\vec{a},b}\right\|_{\tau}^{2}}$
$\displaystyle=$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\left\|P^{s}_{\vec{a}}A^{t}_{b}A^{x}_{c}-A^{x}_{c}P^{s}_{\vec{a}}A^{t}_{b}\right\|_{\tau}^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\Big{(}\left\|P^{s}_{\vec{a}}\Big{(}A^{t}_{b}A^{x}_{c}-A^{x}_{c}A^{t}_{b}\Big{)}\right\|_{\tau}+\left\|\Big{(}P^{s}_{\vec{a}}A^{x}_{c}-A^{x}_{c}P^{s}_{\vec{a}}\Big{)}A^{t}_{b}\right\|_{\tau}\Big{)}^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\left\|P^{s}_{\vec{a}}\Big{(}A^{t}_{b}A^{x}_{c}-A^{x}_{c}A^{t}_{b}\Big{)}\right\|_{\tau}^{2}}+\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\left\|\Big{(}P^{s}_{\vec{a}}A^{x}_{c}-A^{x}_{c}P^{s}_{\vec{a}}\Big{)}A^{t}_{b}\right\|_{\tau}^{2}}$

where the third line follows from the triangle inequality, and the third line
follows from squaring both sides and applying Cauchy-Schwarz. Next, notice
that

$\displaystyle\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\left\|P^{s}_{\vec{a}}\Big{(}A^{t}_{b}A^{x}_{c}-A^{x}_{c}A^{t}_{b}\Big{)}\right\|_{\tau}^{2}}$
$\displaystyle=\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\tau\Big{(}\Big{(}A^{t}_{b}A^{x}_{c}-A^{x}_{c}A^{t}_{b}\Big{)}^{*}(P^{s}_{\vec{a}})^{*}P^{s}_{\vec{a}}\Big{(}A^{t}_{b}A^{x}_{c}-A^{x}_{c}A^{t}_{b}\Big{)}\Big{)}}$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{t,x\sim\mathcal{X}}\,\sum_{b,c}\left\|A^{t}_{b}A^{x}_{c}-A^{x}_{c}A^{t}_{b}\right\|_{\tau}^{2}}\leq\varepsilon$

where the last inequality follows from the assumption (2). Similarly, we can
bound

$\sqrt{\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sum_{\vec{a},b,c}\left\|\Big{(}P^{s}_{\vec{a}}A^{x}_{c}-A^{x}_{c}P^{s}_{\vec{a}}\Big{)}A^{t}_{b}\right\|_{\tau}^{2}}\leq\sqrt{\operatorname*{\mathbb{E}}_{s\sim\mathcal{X}^{k},x\sim\mathcal{X}}\,\sum_{\vec{a},c}\|P^{s}_{\vec{a}}A^{x}_{c}-A^{x}_{c}P^{s}_{\vec{a}}\|_{\tau}^{2}}\leq
k\varepsilon$

using the fact that $\\{A^{t}_{b}\\}$ is a submeasurement for the first
inequality and using the inductive hypothesis for the second inequality. Thus
we have established that

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}s\sim\mathcal{X}^{k}\\\
t,x\sim\mathcal{X}\end{subarray}}\,\sqrt{\sum_{\vec{a},b,c}\left\|P^{s,t}_{\vec{a},b}A^{x}_{c}-A^{x}_{c}P^{s,t}_{\vec{a},b}\right\|_{\tau}^{2}}\leq(k+1)\varepsilon$

which proves the inductive hypothesis for $k+1$. By induction, the hypothesis
holds for all $k$. ∎

###  2.3 Codes

Recall the definition of a code from the introduction.

######  Definition 2.12.

A linear $[n,k,d]_{\Sigma}$ code over a finite field $\Sigma$ is a set
$\mathcal{C}$ of functions $c:[n]\to\Sigma$ with size
$|\mathcal{C}|=|\Sigma|^{k}$ that is closed under linear combination, such
that for any two distinct $c\neq c^{\prime}\in\mathcal{C}$, the number of
coordinates $i\in[n]$ such that $c(i)\neq c^{\prime}(i)$ is at least $d$. The
parameter $n$ is called the _blocklength_ , $k$ is called the _dimension_ ,
and $d$ is called the _distance_ of the code.

Since all codes in this paper are linear, we drop the qualifier “linear” for
brevity. The distance property of a code implies the following simple fact:

######  Proposition 2.13.

Let $\mathcal{C}$ be an $[n,k,d]_{\Sigma}$ code, and let $t=n-d+1$. Suppose
that $i_{1},\dots,i_{t}$ are $t$ distinct elements in $[n]$. Then given a set
of values $a_{1},\dots,a_{t}\in\Sigma$, there exists _at most one_ codeword
$c\in\mathcal{C}$ such that $c(i_{j})=a_{j}$ for all $1\leq j\leq t$.

###### Proof.

Suppose not. Then there are two distinct codewords $c,c^{\prime}$ that agree
on at least $n-d+1$ locations, and thus disagree on at most $d-1$ locations.
This contradicts the assumption that the code has distance $d$. ∎

We now formally define the _interpolability_ condition on codes, which was
discussed in Section 1.2. All codes we consider in the paper are interpolable.

######  Definition 2.14.

Let $\mathcal{C}$ be a linear $[n,k,d]_{\Sigma}$ code, and let $t=n-d+1$. We
say $\mathcal{C}$ is _interpolable_ if, for all collections of $t$ coordinates
$i_{1},\dots,i_{t}\in[n]$, there exists a linear _interpolation map_
$\phi_{i_{1},\dots,i_{t}}:\Sigma^{t}\to\mathcal{C}$ that maps a collection of
values $(a_{1},\dots,a_{t})\in\Sigma^{t}$ to the unique codeword
$c\in\mathcal{C}$ such that $c(i_{j})=a_{j}$ for all $j\in[t]$.

######  Remark 2.15.

The condition of being interpolable is equivalent to saying that any $t$ rows
of the generator matrix $G\in\Sigma^{n\times k}$ of the code are linearly
independent. We observe that the Reed-Solomon code is interpolable for any
degree: for Reed-Solomon with degree $s$, the distance of the code is $n-s$,
and a degree-$s$ polynomial can be uniquely interpolated from its value at
$t=s+1$ points.

####  2.3.1 Tensor codes

######  Definition 2.16.

Given $j\in[m]$ and $u\in[n]^{m-1}$, the _axis-parallel line_ $\ell(j,u)$
through axis $j$ and with intercept $u$ is the set

$\ell(j,u)=\\{(u_{1},u_{2},\dots,u_{j-1},i,u_{j},\dots,u_{m-1})\in[n]^{m}:i\in[n]\\}.$

######  Definition 2.17.

Let $\mathcal{C}$ be a $[n,k,d]_{\Sigma}$ code and let $m\geq 1$ be an
integer. The _tensor code_ $\mathcal{C}^{\otimes m}$ is the set of all
functions $c:[n]^{m}\to\Sigma$ such that the restriction $c|_{\ell}$ of $c$ to
any axis-parallel line $\ell$ is a codeword of $\mathcal{C}$.

######  Proposition 2.18.

Let $\gamma_{m}=1-\frac{d^{m}}{n^{m}}$. For any $c\neq
c^{\prime}\in\mathcal{C}^{\otimes m}$ it holds that

$\Pr_{u\in[n]^{m}}\big{(}c(u)=c^{\prime}(u)\big{)}\,\leq\,\gamma_{m}\,\leq\,\frac{mt}{n}\;.$

###### Proof.

The first inequality follows from the fact that the distance of
$\mathcal{C}^{\otimes m}$ is $d^{m}$. (This is easily seen by verifying that
codewords of $\mathcal{C}^{\otimes m}$ are exactly the tensor products of
(possibly different) codewords from $\mathcal{C}$.) For the second inequality
we use Bernoulli’s inequality,

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

∎

The following two propositions relate codewords of
$\mathcal{C}^{\otimes(m+1)}$ to tuples of codewords of $\mathcal{C}^{\otimes
m}$.

######  Proposition 2.19.

Let $\mathcal{C}$ be an $[n,k,d]_{\Sigma}$ code, and let $t\geq n-d+1$. Let
$x_{1},\dots,x_{t}\in[n]$, and define the subset
$S\subseteq{\left(\mathcal{C}^{\otimes{m}}\right)}^{t}$ as

$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}\\},$

where $h|_{x_{j}}$ denotes the function $h(\cdot,\dots,\cdot,x_{j})$. Then
there is a one-to-one correspondence between $S$ and
$\mathcal{C}^{\otimes(m+1)}$.

###### Proof.

The correspondence maps a tuple $(g_{1},\dots,g_{t})\in S$ to the unique
corresponding element $h\in\mathcal{C}^{\otimes(m+1)}$ such that
$h_{|x_{j}}=g_{j}$ for all $j$. By the definition of $S$ such an $h$ exists;
to show that this is well defined, suppose there are two distinct $h\neq
h^{\prime}$ such that $h|_{x_{j}}=g_{j}=h^{\prime}|_{x_{j}}$ for all $j$.
Since $h\neq h^{\prime}$, there must exist some axis-parallel line
$\ell(m+1,u)$ along the $(m+1)$-st axis such that $h|_{\ell}\neq
h^{\prime}|_{\ell}$ (this is because such lines partition the entire space
$[n]^{m+1}$. At the same time, we have that

$(h|_{\ell})(x_{j})=g_{j}(u)=(h^{\prime}|_{\ell})(x_{j})$

for all $1\leq j\leq t$. Thus, $h|_{\ell}$ and $h^{\prime}|_{\ell}$ are two
codewords of $\mathcal{C}$ which are not equal, yet agree on at least $n-d+1$
points. By the distance property of $\mathcal{C}$, this is impossible. Hence,
$h$ is unique.

So far, we have established the the correspondence is well defined. It remains
to show that it is one-to-one. First, we observe that it is clearly injective
by definition. Next, observe that it is also onto: for any
$h\in\mathcal{C}^{\otimes(m+1)}$, it holds that the tuple
$(h|_{x_{1}},\dots,h|_{x_{t}})$ is in $S$ and maps to $h$ under the
correspondence. Therefore, it is one-to-one. ∎

######  Proposition 2.20.

Let $\mathcal{C}$ be a $[n,k,d]_{\Sigma}$ code that is interpolable, and let
$t=n-d+1$. Let $S$ be as in Proposition 2.19. Then
$S={\left(\mathcal{C}^{\otimes{m}}\right)}^{t}$.

###### Proof.

Fix coordinates $x_{1},\ldots,x_{t}\in[n]$ and let
$\phi_{x_{1},\ldots,x_{t}}:\Sigma^{t}\to\mathcal{C}$ denote the corresponding
linear interpolation map for $\mathcal{C}$. It suffices to show that all
tuples $(g_{1},\dots,g_{t})\in{\left(\mathcal{C}^{\otimes{m}}\right)}^{t}$ are
contained in $S$ (which is a set defined with respect to
$x_{1},\ldots,x_{t}$). Indeed, given such a tuple, let $h:[n]^{m+1}\to\Sigma$
be the function defined by

$h(z_{1},\dots,z_{m},x)=\phi_{x_{1},\dots,x_{t}}(g_{1}(z),\dots,g_{t}(z))(x).$

It follows from the definition of $\phi$ that for any fixed
$z_{1},\dots,z_{m}\in[n]^{m}$, the function $h(z_{1},\dots,z_{m},\cdot)$ is a
codeword of $\mathcal{C}$, and that for any $j\in[t]$ we have

$h(\cdot,\dots,\cdot,x_{j})=g_{j}(\cdot,\dots,\cdot).$

Moreover, by the linearity of $\phi$, it holds that for any fixed $x$,
$h(\cdot,\dots,\cdot,x)$ is a linear combination of $g_{1},\dots,g_{t}$ and is
thus a codeword of $\mathcal{C}^{\otimes m}$. This establishes that
$h\in\mathcal{C}^{\otimes(m+1)}$, and therefore that $(g_{1},\dots,g_{t})\in
S$. ∎

##  3 The tensor code test

Let $\mathcal{C}$ be an interpolable code (called the _base code_) over
alphabet $\Sigma$ with blocklength $n$, dimension $k$, and distance $d$, and
let $m\geq 2$ be an integer. Informally, the augmented tensor code test
proceeds as follows. With probability $1/2$, the referee performs the line-vs-
point test as described in the introduction. With probability $1/2$, the
referee performs a _subcube commutation test_. Here, a _subcube_ of $[n]^{m}$
denotes a subset of points of the form
$H_{x_{m-j+2},\ldots,x_{m}}=\\{(x_{1},\ldots,x_{m-j+1},x_{m-j+2},\ldots,x_{m})\in[n]^{m}:x_{1},\ldots,x_{m-j+1}\in[n]\\}$
where $x_{m-j+2},\ldots,x_{m}$ are fixed elements of $[n]$. If $j=1$, then we
define the subcube $H$ to be all of $[n]^{m}$. The purpose of the subcube
commutation test is to enforce that for an average subcube
$H_{x_{m-j+2},\ldots,x_{m}}$, the measurements corresponding to two randomly
chosen points $u,v\in H_{x_{m-j+2},\ldots,x_{m}}$ approximately commute. The
motivation for choosing the specific distribution on pairs of points used in
the test comes from its use in the analysis, and in particular on how the
induction is structured; see the induction step in the proof of Lemma 4.4.

The augmented tensor code test for the tensor code $\mathcal{C}^{\otimes m}$
is described precisely in Figure 1. From here on we omit the qualifier
“augmented” and simply refer to the test described in Figure 1 as the tensor
code test.

######  Definition 3.1.

A _tracial strategy_ $\mathscr{S}$ for the tensor code test is a tuple
$(\tau,A,B,P)$ where $\tau:\mathscr{A}\to\mathbb{C}$ is a tracial state on a
von Neumann algebra $\mathscr{A}$, and $A,B,P$ are the following projective
measurements:

  1. 1.

_Points measurements_ : for every $u\in[n]^{m}$, let
$A^{u}=\\{A^{u}_{a}\\}_{a\in\Sigma}$ denote the measurement corresponding to
the points question $u$.

  2. 2.

_Lines measurements_ : for every axis-parallel line $\ell\subset[n]^{m}$, let
$B^{\ell}=\\{B^{\ell}_{g}\\}_{g\in\mathcal{C}}$ denote the measurement
corresponding to the lines question $\ell$.

  3. 3.

_Pair measurements_ : for every subcube $H$ and for every $u,v\in H$, let
$P^{u,v}=\\{P^{u,v}_{a,b}\\}_{a,b\in\Sigma}$ denote the measurement
corresponding to the points pair question $(u,v)$.

Aside from the discussion in Section 4.1 all strategies considered in the
paper are tracial strategies as defined in Definition 3.1, and we simply say
“strategy”, omitting the qualifier “tracial”.

######  Definition 3.2.

We say that $\mathscr{S}$ is an $(\varepsilon,\delta)$-good (tracial) strategy
if the following hold:

  1. 1.

_(Consistency between points and lines:)_

$B^{\ell}_{[g\mapsto g(u)|a]}\simeq_{\varepsilon}A^{u}_{a}\;,$

where the expectation is over a uniformly random axis-parallel line
$\ell\subset[n]^{m}$ and a uniformly random point $u\in\ell$, and the answer
summation is over values $a\in\Sigma$. We wrote $g(u)$ to denote $g(u_{j})$
where $\ell$ varies in the $j$-th coordinate.

  2. 2.

_(Consistency between points and pairs:)_

$P^{u,v}_{[(a,b)\mapsto a|a]}\simeq_{\delta}A^{u}_{a}\qquad\text{and}\qquad
P^{u,v}_{[(a,b)\mapsto b|b]}\simeq_{\delta}A^{v}_{b}\;,$

where the expectation is over a uniformly random subcube
$H=H_{x_{m-j+2},\ldots,x_{m}}$ (sampled by choosing a random $j\sim[m]$ and
random $x_{m-j+2},\ldots,x_{m}\sim[n]$) and uniformly random points $u,v\sim
H$, and the answer summation is over values $a\in\Sigma$ and $b\in\Sigma$
respectively.

Perform one of the following tests with probability $\tfrac{1}{2}$ each.

  1. 1.

Axis-parallel lines test: Let $u\sim[n]^{m}$ be a uniformly random point.
Select $j\sim\\{1,\ldots,m\\}$ uniformly at random and let
$\ell=\\{(u_{1},\ldots,u_{j-1},s,u_{j+1},\ldots,u_{m})\in[n]^{m}:s\in[n]\\}$
be the axis-parallel line passing through $u$ in the $j$-th direction.

     * $\circ$

Give $\ell$ to prover A and receive $g\in\mathcal{C}$.

     * $\circ$

Give $u$ to prover B and receive $a\in\Sigma$.

Accept if $g(u_{j})=a$. Reject otherwise.

  2. 2.

Subcube commutation test: Select $j\sim\\{1,\ldots,m\\}$ uniformly at random,
and select $x_{m-j+2},\ldots,x_{m}\sim[n]$ uniformly at random. Select $u,v$
independently and uniformly at random from the subcube
$H_{x_{m-j+2},\ldots,x_{m}}$. Select $t\in\\{0,1\\}$ uniformly at random.

     * $\circ$

If $t=0$, then give $(u,v)$ to prover A and receive
$(b_{u},b_{v})\in\Sigma^{2}$; otherwise, give $(v,u)$ to prover A and receive
$(b_{v},b_{u})\in\Sigma^{2}$.

     * $\circ$

Give $u$ to prover B; receive $a\in\Sigma$.

Accept if $b_{u}=a$. Reject otherwise.

Figure 1: The tensor code test.

Thus a strategy $\mathscr{S}$ that is $(\varepsilon,\delta)$-good according to
Definition 3.2 passes the tensor code test with probability
$1-\frac{1}{2}(\varepsilon+\delta)\geq 1-\varepsilon-\delta$. Conversely, a
strategy $\mathscr{S}$ that passes the tensor code test with probability
$1-\varepsilon$ is $(2\varepsilon,4\varepsilon)$-good.

##  4 Analysis of quantum-soundness of tensor code test

Our main result is the following. Let $\mathcal{C}$ denote an interpolable
$[n,k,d]_{\Sigma}$ code.

######  Theorem 4.1 (Quantum soundness of the tensor code test).

There exists a function

$\eta(m,t,r,\varepsilon,n^{-1})=\mathrm{poly}(m,t,r)\cdot\mathrm{poly}(\varepsilon,n^{-1},e^{-\Omega(r/m^{2})})$

such that the following holds. Let $\mathscr{S}=(\tau,A,B,P)$ be a synchronous
strategy that passes the (augmented) tensor code test for
$\mathcal{C}^{\otimes m}$ with probability $1-\varepsilon$, and let $r\geq
12mt$ be an integer. Let $\mathscr{A}$ denote the algebra associated with the
tracial state $\tau$. Then there exists a projective measurement
$\\{G_{c}\\}_{c\in\mathcal{C}^{\otimes m}}\subset\mathscr{A}$ such that

$\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\sum_{c\in\mathcal{C}^{\otimes
m}}\tau\big{(}G_{c}\,A^{u}_{c(u)}\big{)}\,\geq\,1-\eta\;,$

where $\eta=\eta(m,t,r,\varepsilon,n^{-1})$ with $t=n-d+1$.

The proof of Theorem 4.1 proceeds by induction on the dimension $m$. As
described in the proof overview (Section 1.2) there are two main steps in the
induction, called “self-improvement” and “pasting”. The self-improvement step
is based on the following lemma, whose proof we give in Section 5.

######  Lemma 4.2 (Self-improvement).

There exists a function
$\zeta(m,t,\varepsilon,n^{-1})=\mathrm{poly}(m,t)\cdot\mathrm{poly}(\varepsilon,n^{-1})$
such that the following holds. Let $\mathscr{S}=(\tau,A,B,P)$ be an
$(\varepsilon,\delta)$-good strategy for the tensor code test for
$\mathcal{C}^{\otimes m}$. Suppose that $\\{G_{g}\\}$ is a measurement with
outcomes in $\mathcal{C}^{\otimes m}$ satisfying:

  1. (Consistency with $A$): On average over $x\in[n]^{m}$, $G_{[g\mapsto g(x)\mid a]}\simeq_{\nu}A^{x}_{a}$.

Then there exists a projective submeasurement
$H=\\{H_{h}\\}\subset\mathscr{A}$ with outcomes in $\mathcal{C}^{\otimes m}$
with the following properties:

  1. 1.

(Completeness): $\tau(H)\geq 1-\nu-\zeta$ where $H=\sum_{h}H_{h}$.

  2. 2.

(Consistency with $A$): On average over $x\sim[n]^{m}$, $H_{[h\mapsto h(x)\mid
a]}\simeq_{\zeta}A^{x}_{a}$.

  3. 3.

(Agreement is explained by the complete part of $H$): There exists a positive
linear map $\psi:\mathscr{A}\to\mathbb{C}$ such that

$\psi(\mathbf{1}-H)\leq\zeta$

and for each $h\in\mathcal{C}^{\otimes m}$ and all positive $X\in\mathscr{A}$,
we have

$\psi(X)\geq\operatorname*{\mathbb{E}}_{x\sim[n]^{m}}\tau(X\cdot
A^{x}_{h(x)}).$

where $\zeta=\zeta(m,t,\varepsilon,n^{-1})$ with $t=n-d+1$.

While the first two conclusions of the lemma are intuitive, the third one
deserves some explanation. Intuitively the condition guarantees the existence
of a certain “measure”, $\psi$, such that firstly the measure of the
“incomplete part” of $H$, i.e. $\mathbf{1}-H$, is small (in the lemma, one
should think of $\zeta$ as an error parameter that is $\ll\nu$), and secondly
$\psi$ satisfies a “non-triviality” condition in that it is required to be
large on any $X$ such that also $\operatorname*{\mathbb{E}}_{x}\tau(X\cdot
A^{x}_{h(x)})$ is large, i.e. such that $X$ correlates well with the averaged
operator $\operatorname*{\mathbb{E}}_{x}A^{x}_{h(x)}$ for a given $h$. This
condition is used in the next lemma, Lemma 4.3, to guarantee that the $H$
measurements from Lemma 4.2 for different subcubes need to be compatible in
the sense that their incomplete parts mostly overlap. If this condition were
not present in the assumptions of Lemma 4.3 then instead of $\nu=\kappa+error$
we could only guarantee $\nu=t\cdot\kappa+error$, which is insufficient to
complete the $m$ steps of induction.

The pasting step is based on the following lemma, whose proof is given in
Section 6.

######  Lemma 4.3 (Pasting).

There exists a function

$\nu(m,t,r,\varepsilon,\delta,\zeta,n^{-1})=\mathrm{poly}(m,t,r)\cdot\mathrm{poly}(\varepsilon,\delta,\zeta,n^{-1})$
(4)

such that the following holds. Let $\mathscr{S}=(\tau,A,B,P)$ be an
$(\varepsilon,\delta)$-good strategy for the code $\mathcal{C}^{\otimes m+1}$
with points measurements $A=\\{A^{u,x}\\}_{(u,x)\in[n]^{m}\times[n]}$. Let
$\\{G^{x}\\}_{x\in[n]}$ denote projective submeasurements with outcomes in
$\mathcal{C}^{\otimes m}$ with the following properties:

  1. 1.

(Completeness): $\tau(G)\geq 1-\kappa$ where
$G=\operatorname*{\mathbb{E}}_{x}\sum_{g}G^{x}_{g}$.

  2. 2.

(Consistency with $A$): On average over $(u,x)\in[n]^{m}\times[n]$,
$G^{x}_{[g\mapsto g(u)\mid a]}\simeq_{\zeta}A^{u,x}_{a}$.

  3. 3.

(Agreement is explained by the complete part of $G$): For each $x\in[n]$ there
exists a positive linear map $\psi^{x}$ such that

$\operatorname*{\mathbb{E}}_{x}\psi^{x}(\mathbf{1}-G^{x})\leq\zeta$

and for all $x\in[n]$, $g\in\mathcal{C}^{\otimes m}$, and positive
$X\in\mathscr{A}$, we have

$\psi^{x}(X)\geq\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\tau(X\cdot
A^{u,x}_{g(u)}).$

Then for all integers $r\geq 12mt$ there exists a “pasted” measurement
$H=\\{H_{h}\\}\subset\mathscr{A}$ with outcomes
$h\in\mathcal{C}^{\otimes(m+1)}$, satisfying the following property:

> (Consistency with $A$): On average over $(u,x)\in[n]^{m}\times[n]$,
> $H_{[h\mapsto h(u,x)\mid a]}\simeq_{\mu}A^{u,x}_{a}$

where

$\mu=\mu(\kappa,m,t,r,\varepsilon,\delta,\zeta,n^{-1})\,=\,\kappa\Big{(}1+\frac{1}{3m}\Big{)}+\nu(m,t,r,\varepsilon,\delta,\zeta,n^{-1})+e^{-\frac{r}{72m^{2}}}$
(5)

with $t=n-d+1$.

We now put these two steps together and prove Theorem 4.1. The proof is by
induction on $m$. The inductive argument directly establishes the following
lemma which, together with the self-improvement lemma, implies Theorem 4.1.

######  Lemma 4.4.

There exists a function

$\sigma(m,t,r,\varepsilon,\delta,n^{-1})=\mathrm{poly}(m,t,r)\cdot\big{(}\mathrm{poly}(\varepsilon,\delta,n^{-1})+\exp(-\Omega(r/m^{2}))\big{)}$

such that the following holds. Let $\mathscr{S}=(\tau,A,B,P)$ be an
$(\varepsilon,\delta)$-good strategy for the code $\mathcal{C}^{\otimes m}$
and let $r\geq 12mt$. Let $\mathscr{A}$ denote the algebra associated with
$\mathscr{S}$. Then there exists a measurement $\\{G_{c}\\}\subset\mathscr{A}$
with outcomes in $\mathcal{C}^{\otimes m}$ such that

$\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\sum_{c\in\mathcal{C}^{\otimes
m}}\tau\big{(}G_{c}\,A^{u}_{c(u)}\big{)}\,\geq\,1-\sigma\;,$

where $\sigma=\sigma(m,t,r,\varepsilon,\delta,n^{-1})$ with $t=n-d+1$.

###### Proof of Theorem 4.1 from Lemma 4.4.

The measurement $\\{G_{c}\\}$ produced by Lemma 4.4 satisfies the conclusions
of Theorem 4.1 except it is not projective. To remedy this we apply the self-
improvement lemma to produce a projective submeasurement, and then complete
the result into a projective measurement.

More formally, let $\\{H_{c}\\}$ be the projective submeasurement guaranteed
by applying Lemma 4.2 to $G_{c}$. This submeasurement has the following
properties.

  1. 1.

(Projectivity): $H_{c}$ is projective.

  2. 2.

(Completeness): If $H=\sum_{h}H_{h}$, then $\tau(H)\geq 1-\sigma-\zeta$.

  3. 3.

(Consistency with $A$): On average over $u\sim[n]^{m}$, $H_{[h\mapsto h(u)\mid
a]}\simeq_{\zeta}A^{u}_{a}$.

Let $\tilde{H}$ be the measurement obtained by completing $H$ arbitrarily,
that is by setting $\tilde{H}_{c^{*}}=H_{c^{*}}+\mathbf{1}-\sum_{h}H_{h}$ for
an arbitrarily chosen outcome $c^{*}$, and setting $\tilde{H}_{c}=H_{c}$ for
all other outcomes $c\neq c^{*}$. Then $\tilde{H}$ has the following
properties:

  1. 1.

(Projectivity): $\tilde{H}$ is projective. This holds by the projectivity of
$H$, which implies that $\mathbf{1}-\sum_{h}H_{h}$ is a projector and is
orthogonal to each $H_{c}$ for every outcome $c$.

  2. 2.

(Completeness): $\sum_{h}\tilde{H}_{h}=\mathbf{1}$. This holds by definition.

  3. 3.

(Consistency with $A$): We evaluate the (in)consistency between $\tilde{H}$
and the points measurements. We have

$\displaystyle\operatorname*{\mathbb{E}}_{u}\sum_{a\neq
b}\tau\Big{(}\tilde{H}_{[h\mapsto h(u)\mid a]}\,A^{u}_{b}\Big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{h,b\neq
h(u)}\tau\Big{(}\tilde{H}_{h}\,A^{u}_{b}\Big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{h,b\neq
h(u)}\tau\Big{(}H_{h}\,A^{u}_{b}\Big{)}+\tau\Big{(}(\mathbf{1}-\sum_{h}H_{h})\,\sum_{b\neq
c^{*}(u)}A^{u}_{b}\Big{)}$
$\displaystyle\leq\zeta+\tau\Big{(}\mathbf{1}-\sum_{h}H_{h}\Big{)}$
$\displaystyle\leq 2\zeta+\sigma$

where in the second-to-last inequality we used that $H$ is $\zeta$-consistency
with the points measurements $\\{A^{u}\\}$ and that $\sum_{b\neq
c^{*}(u)}A^{u}_{b}\leq\mathbf{1}$, and in the last inequality we used that the
completeness of $H$ is at least $1-\zeta-\sigma$. Thus on average of
$u\sim[n]^{m}$, we have

$\tilde{H}_{[h\mapsto h(u)\mid a]}\simeq_{2\zeta+\sigma}A^{u}_{a}.$

Setting $\delta=\varepsilon$, and
$\eta(m,t,r,\varepsilon,n^{-1})=2\zeta(m,t,\varepsilon,n^{-1})+\sigma(m,t,r,\varepsilon,\delta,n^{-1})=\mathrm{poly}(m,t,r)\cdot\Big{(}\mathrm{poly}(\varepsilon,n^{-1})+e^{-\Omega(r/m^{2})}\Big{)}$,
we see that $\tilde{H}$ satisfies the conclusion of Theorem 4.1. ∎

###### Proof of Lemma 4.4.

Define $s_{m}=2m$. We argue that there is a choice of universal constants
$c_{0},c_{1},c_{2},c_{3}\geq 1$ such that Lemma 4.4 holds with the function

$\sigma(m,t,r,\varepsilon,\delta,n^{-1})=s_{m}\cdot\Big{(}c_{0}\cdot(mtr)^{c_{1}}\cdot(\varepsilon^{1/c_{2}}+\delta^{1/c_{2}}+n^{-1/c_{2}})+e^{-c_{3}r/m^{2}}\Big{)}\;.$

The constants $c_{0},c_{1},c_{2},c_{3}$ are set in terms of the universal
constants that are implicit in the $\mathrm{poly}(\cdot)$ notation for the
functions $\zeta,\nu,\mu$ from Lemma 4.2 and Lemma 4.3. We now explicitly
identify these constants:

$\displaystyle\zeta(m,t,\varepsilon,n^{-1})$
$\displaystyle=z_{0}\cdot(mt)^{z_{1}}\cdot(\varepsilon^{1/z_{1}}+n^{-1/z_{1}})$
(6) $\displaystyle\nu(m,t,r,\varepsilon,\delta,\zeta,n^{-1})$
$\displaystyle=b_{0}\cdot(mtr)^{b_{1}}\cdot(\varepsilon^{1/b_{2}}+\delta^{1/b_{2}}+\zeta^{1/b_{2}}+n^{-1/b_{2}})$
(7) $\displaystyle\mu(\kappa,m,t,r,\varepsilon,\delta,\zeta,n^{-1})$
$\displaystyle=\kappa\Big{(}1+\frac{1}{3m}\Big{)}+\nu(m,t,r,\varepsilon,\delta,\zeta,n^{-1})+e^{-\frac{r}{72m^{2}}}$
(8)

where $z_{0},z_{1},z_{2},b_{0},b_{1},b_{2}\geq 1$. Now we set the constants
$c_{0},c_{1},c_{2},c_{3}$ as follows.

  1. 1.

Let $c_{0}=4b_{0}z_{0}$.

  2. 2.

Let $c_{1}=b_{1}+z_{1}+1$.

  3. 3.

Let $c_{2}=b_{2}z_{2}$.

  4. 4.

Let $c_{3}=1/72$.

We prove that Lemma 4.4 holds with this choice of function
$\sigma(m,t,r,\varepsilon,\delta,n^{-1})$ via induction on $m$, starting with
$m=1$.

##### Base case.

For the case $m=1$ there is only one line $\ell=\\{(\beta):\beta\in[n]\\}$ .
This means that the lines measurement $B=\\{B^{\ell}\\}$ contains a single
measurement $B^{\ell}$. Because $\mathscr{S}$ passes the tensor codes test
with probability $1-\varepsilon$, it is $(2\varepsilon,4\varepsilon)$-good. As
a result,

$B^{\ell}_{[g\mapsto g(u)\mid a]}\simeq_{2\varepsilon}A^{u}_{a}\;.$

The theorem follows by setting $G=\\{G_{g}\\}$ equal to $B^{\ell}$, since
$c_{0}\geq 2$ (which implies that $\sigma\geq 2\varepsilon$).

##### Induction step.

Assuming, as the inductive hypothesis, that Lemma 4.4 holds for some $m\geq
1$, we prove it for $m+1$. Let $\mathscr{S}=(\tau,A,B,P)$ be a
$(\varepsilon,\delta)$-good strategy for the tensor code test with
$\mathcal{C}^{\otimes(m+1)}$, and let $r\geq 12(m+1)t$. For each $x\in[n]$, we
define $\mathscr{S}^{x}=(\tau,A^{x},B^{x},P^{x})$ to be the strategy
restricted on the last coordinate being $x$. In other words, we write
rClrClrCl A^x &:= {A^u,x}_u ∈[n]^m, B^x := {B^ℓ,x}_ℓ⊂[n]^m, P^x := {P^u,
v,x}_u, v ∈[n]^m,
where A^u, x := A^u ∘x, B^ℓ, x := B^ℓ∘x, P^u, v, x := P^u ∘x, v ∘x, where
“$\circ$” denotes string concatenation, and $\ell\circ x=\\{\alpha\circ
x:\alpha\in\ell\\}$. Then $\mathscr{S}^{x}$ is a strategy for the
$\mathcal{C}^{\otimes m}$ tensor code test. Write $1-\varepsilon_{x}$ and
$1-\delta_{x}$ for the probability that $\mathscr{S}^{x}$ passes the axis-
parallel lines test and subcube commutation test, respectively. Then
$\mathscr{S}^{x}$ is an $(\varepsilon_{x},\delta_{x})$-good strategy.

We claim that on average over $x$ chosen uniformly from $[n]$,

$\operatorname*{\mathbb{E}}_{x\sim[n]}\varepsilon_{x}\leq\left(\frac{m+1}{m}\right)\cdot\varepsilon,\;\operatorname*{\mathbb{E}}_{x\sim[n]}\delta_{x}\leq\left(\frac{m+1}{m}\right)\cdot\delta.$

Indeed, observe that in the axis-parallel lines test over $[n]^{m+1}$, the
probability that an axis-parallel line along axis $m+1$ is chosen is
$1/(m+1)$. Thus,

$\varepsilon=\frac{1}{m+1}\cdot\Pr\Big{(}\text{success for $\ell$ parallel to
axis
$m+1$}\Big{)}+\frac{m}{m+1}\cdot\operatorname*{\mathbb{E}}_{x}\varepsilon_{x}\geq\frac{m}{m+1}\cdot\operatorname*{\mathbb{E}}_{x}\varepsilon_{x},$

which yields the claimed bound on the expectation of $\varepsilon_{x}$. A
similar calculation holds for the subcube test (the probability that the
subcube does not fix the $m+1$st coordinate is $1/(m+1)$).

Now we apply the inductive hypothesis, noting that $r\geq 12mt$. To do so, fix
an $x\in[n]$. The inductive hypothesis states the existence of a measurement
$G^{x}=\\{G^{x}_{g}\\}_{g\in\mathcal{C}^{\otimes m}}$ such that on average
over $u\in[n]^{m}$,

$G^{x}_{[g\mapsto g(u)\mid a]}\simeq_{\sigma_{x}}A^{u,x}_{a},$

where $\sigma_{x}=\sigma(m,t,r,\varepsilon_{x},\delta_{x},n^{-1})$. Setting
$\zeta_{x}=\zeta(m,t,\varepsilon_{x},n^{-1})$, self-improvement (Lemma 4.2)
then implies the existence of a projective submeasurement
$H^{x}=\\{H^{x}_{h}\\}_{h\in\mathcal{C}^{\otimes m}}$ with the following
properties:

  1. 1.

(Completeness): If $H^{x}=\sum_{h}H^{x}_{h}$, then $\tau(H^{x})\geq
1-\sigma_{x}-\zeta_{x}$.

  2. 2.

(Consistency with $A^{x}$): On average over $u\sim[n]^{m}$, $H^{x}_{[h\mapsto
h(u)\mid a]}\simeq_{\zeta_{x}}A^{u,x}_{a}$.

  3. 3.

(Agreement is explained by the complete part of $H^{x}$): There exists a
positive linear map $\psi^{x}$ such that

$\psi^{x}(\mathbf{1}-H^{x})\leq{\zeta_{x}},$

and for each $h\in\mathcal{C}^{\otimes m}$ and all positive $X\in\mathscr{A}$,
we have

$\psi^{x}(X)\geq\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\tau(X\cdot
A^{u,x}_{h(u)}).$

These guarantees are almost of the form demanded by the hypotheses of the
pasting lemma (Lemma 4.3). However, the error bounds depend on $x$, whereas we
would like the errors to be averaged over $x$. To obtain such bounds, we will
bound the average of $\sigma_{x},\zeta_{x}$ over $x\sim[n]$. Observe that
$\sigma_{x}$ and $\zeta_{x}$ depend on $x$ only through
$\varepsilon_{x},\delta_{x}\in[0,1]$, and are polynomial functions of
$\varepsilon_{x},\delta_{x}$. For any distribution over a random variable
$\alpha$ drawn from the interval $[0,1]$, for $c\geq 1$, it holds that
$\operatorname*{\mathbb{E}}\alpha^{c}\leq\operatorname*{\mathbb{E}}\alpha$,
and by concavity, for any $c<1$,
$\operatorname*{\mathbb{E}}\alpha^{c}\leq(\operatorname*{\mathbb{E}}\alpha)^{c}$.
Hence, the averaged quantities $\operatorname*{\mathbb{E}}_{x}\sigma_{x}$ and
$\operatorname*{\mathbb{E}}_{x}\zeta_{x}$, which we denote $\hat{\sigma}$ and
$\hat{\zeta}$, are polynomial functions of
$\operatorname*{\mathbb{E}}_{x}\varepsilon_{x}\leq\frac{m+1}{m}\varepsilon$
and $\operatorname*{\mathbb{E}}_{x}\delta_{x}\leq\frac{m+1}{m}\delta$:

$\displaystyle\hat{\sigma}=\operatorname*{\mathbb{E}}_{x}\sigma_{x}$
$\displaystyle=s_{m}\cdot
c_{0}(mtr)^{c_{1}}\cdot\operatorname*{\mathbb{E}}_{x}(\varepsilon_{x}^{1/c_{2}}+\delta_{x}^{1/c_{2}}+n^{-1/c_{2}})+s_{m}\cdot
e^{-c_{3}r/m^{2}}$ (9) $\displaystyle\leq s_{m}\cdot
c_{0}(mtr)^{c_{1}}\cdot\left(\left(\frac{m+1}{m}\varepsilon\right)^{1/c_{2}}+\left(\frac{m+1}{m}\delta\right)^{1/c_{2}}+n^{-1/c_{2}}\right)+s_{m}\cdot
e^{-c_{3}r/m^{2}}$ (10) $\displaystyle\leq s_{m}\cdot
c_{0}(mtr)^{c_{1}}\cdot\Big{(}\frac{m+1}{m}\Big{)}^{\frac{1}{c_{2}}}\cdot\left(\varepsilon^{1/c_{2}}+\delta^{1/c_{2}}+n^{-1/c_{2}}\right)+s_{m}\cdot
e^{-c_{3}r/m^{2}}$ (11)
$\displaystyle\hat{\zeta}=\operatorname*{\mathbb{E}}_{x}\zeta_{x}$
$\displaystyle=z_{0}(mt)^{z_{1}}\cdot\operatorname*{\mathbb{E}}_{x}(\varepsilon^{1/z_{2}}+n^{-1/z_{2}})$
(12) $\displaystyle\leq
z_{0}(mt)^{z_{1}}\cdot\left(\left(\frac{m+1}{m}\varepsilon\right)^{1/z_{2}}+n^{-1/z_{2}}\right)$
(13) $\displaystyle\leq
z_{0}((m+1)t)^{z_{1}}\cdot(\varepsilon^{1/z_{2}}+n^{-1/z_{2}})$ (14)

Thus we have the following guarantees on the submeasurements $\\{H^{x}\\}$:

  1. 1.

(Completeness): If
$H=\operatorname*{\mathbb{E}}_{x\sim[n]^{m}}\sum_{h}H^{x}_{h}$, then
$\tau(H)\geq 1-\hat{\sigma}-\hat{\zeta}$.

  2. 2.

(Consistency with $A^{x}$): On average over $(u,x)\sim[n]^{m}\times[n]$,
$H^{x}_{[h\mapsto h(u)\mid a]}\simeq_{\hat{\zeta}}A^{u,x}_{a}$.

  3. 3.

(Agreement is explained by the complete part of $H^{x}$): For each $x$ there
exists a positive linear map $\psi^{x}$ such that

$\operatorname*{\mathbb{E}}_{x}\psi^{x}(\mathbf{1}-H^{x})\leq{\hat{\zeta}},$

and for each $h\in\mathcal{C}^{\otimes m}$ and all positive $X\in\mathscr{A}$,
we have

$\psi(X)\geq\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\tau(X\cdot
A^{u,x}_{h(u)}).$

Define $\hat{\kappa}=\hat{\sigma}+\hat{\zeta}$. We see that the measurements
$H^{x}$ satisfy the hypotheses of the pasting lemma (Lemma 4.3) with error
parameters $\hat{\kappa}$ and $\hat{\zeta}$. Applying the lemma, we conclude
that the resulting measurement $\tilde{H}$ satisfies the following consistency
relation with $A$: on average over $(u,x)\in[n]^{m}\times[n]$,

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

where

$\displaystyle\mu$
$\displaystyle=\mu(\hat{\kappa},m,t,r,\varepsilon,\delta,\hat{\zeta},n^{-1})\,=\,\hat{\kappa}\Big{(}1+\frac{1}{3m}\Big{)}+\nu(m,t,r,\varepsilon,\delta,\hat{\zeta},n^{-1})+e^{-c_{3}r/m^{2}}$
(15)
$\displaystyle=\Big{(}\hat{\sigma}+\hat{\zeta}\Big{)}\Big{(}1+\frac{1}{3m}\Big{)}+b_{0}(mtr)^{b_{1}}\cdot\big{(}\varepsilon^{1/b_{2}}+\delta^{1/b_{2}}+\hat{\zeta}^{1/b_{2}}+n^{-1/b_{2}}\big{)}+e^{-c_{3}r/m^{2}}.$
(16)

If we show that $\mu\leq\sigma(m+1,t,r,\varepsilon,\delta,n^{-1})$, then we
will have established the inductive step and we would be done. To proceed, we
first substitute (14) in for $\hat{\zeta}$. Let $b^{\prime}=b_{2}z_{2}$.

$\displaystyle\hat{\zeta}^{1/b_{2}}$
$\displaystyle\leq(z_{0}((m+1)t)^{z_{1}})^{1/b_{2}}\cdot(\varepsilon^{1/z_{2}}+n^{-1/z_{2}})^{1/b_{2}}$
$\displaystyle\leq
z_{0}((m+1)t)^{z_{1}}\cdot(\varepsilon^{1/b^{\prime}}+n^{-1/b^{\prime}})$

where we used that $z_{0}((m+1)t)^{z_{1}}\geq 1$ and $b_{2}\geq 1$. Plugging
these bounds into (16), we get

$\displaystyle\mu$
$\displaystyle\leq\big{(}1+\frac{1}{3m}\big{)}\cdot\big{(}\hat{\sigma}+\hat{\zeta}\big{)}+2b_{0}(mtr)^{b_{1}}\cdot
z_{0}((m+1)t)^{z_{1}}\cdot\big{(}\varepsilon^{1/b^{\prime}}+\delta^{1/b^{\prime}}+n^{-1/b^{\prime}}\big{)}+e^{-c_{3}r/m^{2}}$
$\displaystyle\leq\big{(}1+\frac{1}{3m}\big{)}\cdot\big{(}\hat{\sigma}+\hat{\zeta}\big{)}+2b_{0}z_{0}((m+1)tr)^{b_{1}+z_{1}}\big{(}\varepsilon^{1/b^{\prime}}+\delta^{1/b^{\prime}}+n^{-1/b^{\prime}}\big{)}+e^{-c_{3}r/m^{2}}~{}.$
(17)

Similarly, we can upper bound

$\big{(}1+\frac{1}{3m}\big{)}\cdot\hat{\zeta}\leq 2\cdot
z_{0}((m+1)t)^{z_{1}}\cdot(\varepsilon^{1/b^{\prime}}+n^{-1/b^{\prime}})$

because, for example, $\varepsilon^{1/b_{2}}\leq\varepsilon^{1/b^{\prime}}$.
Thus we get that (17) is at most

(17)
$\displaystyle\leq\big{(}1+\frac{1}{3m}\big{)}\hat{\sigma}+4b_{0}z_{0}((m+1)tr)^{b_{1}+z_{1}}\big{(}\varepsilon^{1/b^{\prime}}+\delta^{1/b^{\prime}}+n^{-1/b^{\prime}}\big{)}+e^{-c_{3}r/m^{2}}$
(18)

Substituting (11) in for $\hat{\sigma}$ and using that $c_{2}\geq b^{\prime}$
we get

(18) $\displaystyle\leq\big{(}1+\frac{1}{3m}\big{)}s_{m}\cdot
c_{0}(mtr)^{c_{1}}\cdot\Big{(}\frac{m+1}{m}\Big{)}^{\frac{1}{c_{2}}}\cdot\left(\varepsilon^{1/c_{2}}+\delta^{1/c_{2}}+n^{-1/c_{2}}\right)$
$\displaystyle\qquad\qquad+4b_{0}z_{0}((m+1)tr)^{b_{1}+z_{1}}\cdot\big{(}\varepsilon^{1/c_{2}}+\delta^{1/c_{2}}+n^{-1/c_{2}}\big{)}$
$\displaystyle\qquad\qquad+\Big{(}\big{(}1+\frac{1}{3m}\big{)}s_{m}+1\Big{)}\cdot
e^{-c_{3}r/m^{2}}~{}.$ (19)

Next, using that $\big{(}1+\frac{1}{3m}\big{)}s_{m}\leq s_{m+1}$, we have

(19) $\displaystyle\leq\Big{(}s_{m+1}\cdot
c_{0}(mtr)^{c_{1}}\cdot\Big{(}\frac{m+1}{m}\Big{)}^{\frac{1}{c_{2}}}+4b_{0}z_{0}((m+1)tr)^{b_{1}+z_{1}}\Big{)}\cdot\big{(}\varepsilon^{1/c_{2}}+\delta^{1/c_{2}}+n^{-1/c_{2}}\big{)}$
$\displaystyle\qquad\qquad+\Big{(}\big{(}1+\frac{1}{3m}\big{)}s_{m}+1\Big{)}\cdot
e^{-c_{3}r/m^{2}}~{}.$ (20)

If we argue both

$\displaystyle s_{m+1}\cdot
c_{0}(mtr)^{c_{1}}\cdot\Big{(}\frac{m+1}{m}\Big{)}^{\frac{1}{c_{2}}}+4b_{0}z_{0}((m+1)tr)^{b_{1}+z_{1}}\qquad$
$\displaystyle\leq\qquad s_{m+1}c_{0}((m+1)tr)^{c_{1}}$ (21)
$\displaystyle\big{(}1+\frac{1}{3m}\big{)}s_{m}+1\qquad$
$\displaystyle\leq\qquad s_{m+1}$ (22)

then we would be done as (20) would be at most
$\sigma(m+1,t,r,\varepsilon,\delta,n^{-1})$ as desired. To argue (21) we first
note that it is equivalent to showing that

$s_{m+1}c_{0}(tr)^{c_{1}}\Big{(}(m+1)^{c_{1}}-m^{c_{1}-\frac{1}{c_{2}}}(m+1)^{\frac{1}{c_{2}}}\Big{)}\geq
4b_{0}z_{0}((m+1)tr)^{b_{1}+z_{1}}~{}.$

Since $s_{m+1}\geq 1$, $c_{0}\geq 4b_{0}z_{0}$ by definition, and $c_{1}\geq
b_{1}+z_{1}+1$ by definition, it suffices to argue that

$(m+1)^{c_{1}}-m^{c_{1}-\frac{1}{c_{2}}}(m+1)^{\frac{1}{c_{2}}}\geq(m+1)^{b_{1}+z_{1}}~{}.$

This is equivalent to showing

$(m+1)^{c_{1}-(b_{1}+z_{1})}-m^{c_{1}-\frac{1}{c_{2}}}(m+1)^{\frac{1}{c_{2}}-(b_{1}+z_{1})}\geq
1~{}.$

Since $b_{1},z_{1},c_{2}\geq 1$ it holds that
$(m+1)^{\frac{1}{c_{2}}-(b_{1}+z_{1})}\leq m^{\frac{1}{c_{2}}-(b_{1}+z_{1})}$
and thus

$\displaystyle(m+1)^{c_{1}-(b_{1}+z_{1})}-m^{c_{1}-\frac{1}{c_{2}}}(m+1)^{\frac{1}{c_{2}}-(b_{1}+z_{1})}$
$\displaystyle\geq(m+1)^{c_{1}-(b_{1}+z_{1})}-m^{c_{1}-\frac{1}{c_{2}}}m^{\frac{1}{c_{2}}-(b_{1}+z_{1})}$
$\displaystyle=(m+1)^{c_{1}-(b_{1}+z_{1})}-m^{c_{1}-(b_{1}+z_{1})}$
$\displaystyle\geq 1$

as desired, where we used that $c_{1}\geq b_{1}+z_{1}+1$ again.

To argue (22) one can see by definition of $s_{m}$ and $s_{m+1}$ that

$\displaystyle
s_{m+1}-\big{(}1+\frac{1}{3m}\big{)}s_{m}=2(m+1)-2m\big{(}1+\frac{1}{3m}\big{)}\geq
1$

as desired.

∎

###  4.1 Extension to general states

As mentioned in the introduction, Theorem 4.1 is formulated in the framework
of synchronous strategies, which is particularly convenient to state and prove
the result as it involves a single Hilbert space and set of measurement
operators. For some applications one may wish to extend the guarantees of
Theorem 4.1 to the more general setting of strategies that are not assumed to
be perfectly synchronous a priori. This extension is essentially provided in
the work [Vid21]. For completeness in this section we include all details of
the reduction.

We first recall the following definition of a (not necessarily synchronous)
two-prover strategy for a game $G$, which we immediately specialize to the
case of the tensor code test.

######  Definition 4.5.

A _two-prover strategy_ $\mathscr{S}$ for the tensor code test is a tuple
$({|\psi\rangle},A,B,P,\tilde{A},\tilde{B},\tilde{P})$ where
${|\psi\rangle}\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ is a state in the
tensor product of two finite-dimensional Hilbert spaces $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$, and $A,B,P$ (resp. $\tilde{A},\tilde{B},\tilde{P}$) are the
following families of projective measurements:

  1. 1.

_Points measurements_ : for every $u\in[n]^{m}$, let
$A^{u}=\\{A^{u}_{a}\\}_{a\in\Sigma}$ (resp.
$\tilde{A}^{u}=\\{\tilde{A}^{u}_{a}\\}_{a\in\Sigma}$) denote the first (resp.
second) prover’s measurement corresponding to the points question $u$.

  2. 2.

_Lines measurements_ : for every axis-parallel line $\ell\subset[n]^{m}$, let
$B^{\ell}=\\{B^{\ell}_{g}\\}_{g\in\mathcal{C}}$ (resp.
$\tilde{B}^{\ell}=\\{\tilde{B}^{\ell}_{g}\\}_{g\in\mathcal{C}}$) denote the
first (resp. second) prover’s measurement corresponding to the lines question
$\ell$.

  3. 3.

_Pair measurements_ : for every subcube $H$ and for every $u,v\in H$, let
$P^{u,v}=\\{P^{u,v}_{a,b}\\}_{a,b\in\Sigma}$ (resp.
$\tilde{P}^{u,v}=\\{\tilde{P}^{u,v}_{a,b}\\}_{a,b\in\Sigma}$) denote the first
(resp. second) prover’s measurement corresponding to the points pair question
$(u,v)$.

This definition is the same as Definition 3.1 given at the start of Section 3,
except that we have decoupled the measurement operators associated with each
prover and the tracial state $\tau$ has been replaced by the state
${|\psi\rangle}$, with the additional tensor product structure. (There is a
more general class of strategies where all prover operators act on the same
possibly infinite-dimensional Hilbert space $\mathcal{H}$ but all operators
associated with one prover are required to commute with the other prover’s
operators; we do not consider such _commuting-operator_ strategies here.)

Because we do not assume a priori that the provers must employ the same
measurement operators we modify the tensor code test by adding a
“synchronicity test’ described in Figure 2. To distinguish this test from the
original tensor code test we refer to it as “the two-prover tensor code test.”

With probably $\tfrac{1}{3}$ each, perform either of the two tests described
in Figure 1, where the roles of “prover $A$” and “prover $B$” are attributed
at random (under the constraint that each prover gets assigned a different
role). With the remaining probability $\frac{1}{3}$ perform the following
test.

  1. 3.

Synchronicity test: Let $\ell\subset[n]^{m}$ be a line sampled according to
the same distribution as in the axis-parallel line test, i.e. $\ell$ is a
uniformly random axis-parallel line. Let $(u,v)$ be a pair of points sampled
according to the same distribution as in the commutation test, i.e. $u$ and
$v$ are both uniformly distributed in the same random subcube. With
probability $\frac{1}{3}$ each, send either $\ell$, or $u$, or the pair
$(u,v)$, to both provers. Accept if and only if the provers’ answers are
identical.

Figure 2: The two-prover tensor code test.

The following is analogous to Definition 3.2.

######  Definition 4.6.

We say that $\mathscr{S}$ is an $(\varepsilon,\delta,\xi)$-good strategy for
the two-prover tensor code test if the following hold:

  1. 1.

_(Consistency between points and lines:)_ The strategy passes the axis-
parallel line test with probability at least $1-\varepsilon$. Formally,

$\operatorname*{\mathbb{E}}_{\ell\subset[n]^{m}}\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a\in\Sigma}\,\frac{1}{2}\Big{(}{\langle\psi|}B^{\ell}_{[g\mapsto
g(u)|a]}\otimes\tilde{A}^{u}_{a}{|\psi\rangle}+{\langle\psi|}A^{u}_{a}\otimes\tilde{B}^{\ell}_{[g\mapsto
g(u)|a]}{|\psi\rangle}\Big{)}\,\geq\,1-\varepsilon\;,$

where the expectation is over a uniformly random axis-parallel line
$\ell\subset[n]^{m}$ and a uniformly random point $u\in\ell$.

  2. 2.

_(Consistency between points and pairs:)_

$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}H\\\ u,v\sim
H\end{subarray}}\sum_{a,b\in\Sigma}\,\frac{1}{2}\Big{(}{\langle\psi|}P^{u,v}_{[(a,b)\mapsto
a|a]}\otimes\tilde{A}^{u}_{a}{|\psi\rangle}+{\langle\psi|}A^{u}_{a}\otimes\tilde{P}^{u,v}_{[(a,b)\mapsto
a|a]}{|\psi\rangle}\Big{)}$ $\displaystyle\geq\,1-\delta\;,$
$\displaystyle\operatorname*{\mathbb{E}}_{\begin{subarray}{c}H\\\ u,v\sim
H\end{subarray}}\sum_{a,b\in\Sigma}\,\frac{1}{2}\Big{(}{\langle\psi|}P^{u,v}_{[(a,b)\mapsto
b|b]}\otimes\tilde{A}^{v}_{b}{|\psi\rangle}+{\langle\psi|}A^{v}_{b}\otimes\tilde{P}^{u,v}_{[(a,b)\mapsto
b|b]}{|\psi\rangle}\Big{)}$ $\displaystyle\geq\,1-\delta\;,$

where the expectation is over a uniformly random subcube
$H=H_{x_{m-j+2},\ldots,x_{m}}$ (sampled by choosing a random $j\sim[m]$ and
random $x_{m-j+2},\ldots,x_{m}\sim[n]$) and uniformly random points $u,v\sim
H$.

  3. 3.

_(Synchronicity:)_

$\frac{1}{3}\Big{(}\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\sum_{a\in\Sigma}\,{\langle\psi|}A^{u}_{a}\otimes\tilde{A}^{u}_{a}{|\psi\rangle}+\operatorname*{\mathbb{E}}_{\ell\subset[n]^{m}}\sum_{f}{\langle\psi|}B^{\ell}_{f}\otimes\tilde{B}^{\ell}_{f}{|\psi\rangle}+\operatorname*{\mathbb{E}}_{\begin{subarray}{c}H\\\
u,v\sim
H\end{subarray}}\sum_{a,b\in\Sigma}{\langle\psi|}P^{u,v}_{a,b}\otimes\tilde{P}^{u,v}_{a,b}{|\psi\rangle}\Big{)}\,\geq\,1-\xi\;,$

where the expectations are uniform over a point $u$ and an axis-parallel line
$\ell$, and as in the previous item for $(H,u,v)$.

Finally, we say that a two-prover strategy _passes the (two-prover) tensor
code test with probability $1-\varepsilon$_ if the strategy is
$(\varepsilon^{\prime},\delta^{\prime},\xi^{\prime})$-good for some
$\varepsilon^{\prime},\delta^{\prime},\xi^{\prime}$ such that
$\frac{1}{3}(\varepsilon^{\prime}+\delta^{\prime}+\xi^{\prime})\leq\varepsilon$.

We can now state our two-prover extension of Theorem 4.1.

######  Theorem 4.7.

There exists a function

$\eta^{\prime}(m,t,k,\varepsilon,n^{-1})=\mathrm{poly}(m,t,k)\cdot\mathrm{poly}(\varepsilon,n^{-1},e^{-k/m^{2}})$

such that the following holds. Let
$\mathscr{S}=({|\psi\rangle},A,B,P,\tilde{A},\tilde{B},\tilde{P})$ be a two-
prover strategy that passes the two-prover tensor code test for
$\mathcal{C}^{\otimes m}$ with probability $1-\varepsilon$, where
${|\psi\rangle}\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, and $k\geq 12mt$.
Then there exists projective measurements
$\\{G_{c}\\}_{c\in\mathcal{C}^{\otimes m}}$ and
$\\{\tilde{G}_{c}\\}_{c\in\mathcal{C}^{\otimes m}}$ on $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$ respectively such that the following hold, on expectation
over a uniformly random $u\sim[n]^{m}$ and a uniformly random axis-parallel
line $\ell\subset[n]^{m}$:

$\displaystyle A^{u}_{a}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta^{\prime}}\mathbf{1}\otimes\tilde{G}_{[c\mapsto
c(u)\mid a]}\;,$ (23) $\displaystyle G_{[c\mapsto c|_{\ell}\mid
f]}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta^{\prime}}\mathbf{1}\otimes\tilde{B}^{\ell}_{f}\;,$
(24) $\displaystyle G_{c}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta^{\prime}}\mathbf{1}\otimes\tilde{G}_{c}\;,$ (25)

where $\eta^{\prime}=\eta^{\prime}(m,t,\varepsilon,n^{-1})$ with $t=n-d+1$.

###### Proof.

Let $\mathscr{S}=({|\psi\rangle},A,B,P,\tilde{A},\tilde{B},\tilde{P})$ be as
in the statement of the theorem. The proof proceeds in three steps. The first
and main step consists in applying [Vid21, Corollary 4.1] to Theorem 4.1 to
obtain the following.

######  Claim 4.8.

There exists measurements $\\{G_{c}\\}$ on $\mathcal{H}_{A}$ and
$\\{\tilde{G}_{c}\\}$ on $\mathcal{H}_{B}$ such that

$\displaystyle A^{u}_{a}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta_{1}}\mathbf{1}\otimes\tilde{G}_{[c\mapsto c(u)\mid
a]}\;,$ (26) $\displaystyle\mathbf{1}\otimes\tilde{A}^{u}_{a}$
$\displaystyle\simeq_{\eta_{1}}{G}_{[c\mapsto c(u)\mid
a]}\otimes\mathbf{1}\;,$ (27)

for some
$\eta_{1}=\eta_{1}(m,t,\varepsilon,n^{-1})=\mathrm{poly}(m,t)\cdot\mathrm{poly}(\varepsilon,n^{-1})$.

###### Proof.

To apply [Vid21, Corollary 4.1] we first need to construct a _symmetric_
strategy, which means that ${|\psi\rangle}$ can be written as

${|\psi\rangle}\,=\,\sum_{i}\sqrt{\lambda_{i}}{|u_{i}\rangle}\otimes{|u_{i}\rangle}\,\in\,\mathcal{H}\otimes\mathcal{H}\;,$
(28)

where the $\lambda_{i}$ are non-negative and $\\{{|u_{i}\rangle}\\}$
orthonormal in some Hilbert space $\mathcal{H}$, and the two provers’
measurement operators are identical up to a transpose:
$\tilde{A}^{u}_{a}=(A^{u}_{a})^{T}$ for all $u,a$, where the transpose is
taken with respect to the basis $\\{{|u_{i}\rangle}\\}$, and similarly for the
$B$ and $P$ measurement operators. The idea to achieve this is standard. First
assume without loss of generality that
$\mathcal{H}_{A}\simeq\mathcal{H}_{B}\simeq\mathcal{H}^{\prime}$ for some
Hilbert space $\mathcal{H}^{\prime}$. This can always be achieved by enlarging
$\mathcal{H}_{A}$ or $\mathcal{H}_{B}$ as needed. Next define

${|\psi^{\prime}\rangle}=\frac{1}{\sqrt{2}}\big{(}{|\psi\rangle}\otimes{|0\rangle}\otimes{|1\rangle}+(S{|\psi\rangle})\otimes{|1\rangle}\otimes{|0\rangle}\big{)}\in\mathcal{H}^{\prime}\otimes\mathcal{H}^{\prime}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}\;,$

where $S$ is the “SWAP” operator $S=(2P-I)$ with $P$ the projection on the
symmetric subspace
Span$\\{{|u\rangle}\otimes{|u\rangle}:\,{|u\rangle}\in\mathcal{H}^{\prime\prime}\\}$.
Let $\mathcal{H}=\mathcal{H}^{\prime}\otimes\mathbb{C}^{2}$. For any $u,a$
define $(A^{\prime})^{u}_{a}=A^{u}_{a}\otimes{|0\rangle}\\!{\langle
0|}+(\tilde{A}^{u}_{a})^{T}\otimes{|1\rangle}\\!{\langle 1|}$ and similarly
$B^{\prime}$ and $P^{\prime}$. Then (reordering the subsystems of
${|\psi^{\prime}\rangle}$ in the obvious way so that
${|\psi^{\prime}\rangle}\in\mathcal{H}\otimes\mathcal{H}$) for any
$X^{\prime},Y^{\prime}$ among the newly defined measurement operators we have
that

$\displaystyle{\langle\psi^{\prime}|}X^{\prime}\otimes(Y^{\prime})^{T}{|\psi^{\prime}\rangle}$
$\displaystyle=\frac{1}{2}\big{(}{\langle\psi|}X\otimes\tilde{Y}{|\psi\rangle}+{\langle\psi|}S^{\dagger}(\tilde{X}^{T}\otimes
Y^{T})S{|\psi\rangle}\big{)}$
$\displaystyle={\langle\psi|}X\otimes\tilde{Y}{|\psi\rangle}\;.$

As a consequence, the symmetric strategy $\mathscr{S}^{\prime}$ also passes
the tensor code test with probability at least $1-\varepsilon$.

Next we introduce some notation associated to the application of the
corollary. Let $\mathcal{X}=[n]^{m}\cup([n]^{m-1}\times[m])\cup([n]^{m})^{2}$
be the set of all questions that can be asked to the first prover in the two-
prover tensor code test, $\mathcal{Y}=\\{\bot\\}$ a singleton, and
$\mathcal{B}=\mathcal{C}^{\otimes m}$. Let $p$ be the uniform distribution on
$[n]^{m}\subset\mathcal{X}$, and for $u$ in the support of $p$, let
$g_{u}:\Sigma\to 2^{\mathcal{C}^{\otimes m}}$ map $a\in\Sigma$ to the set of
all $c\in\mathcal{C}^{\otimes m}$ such that $c(u)=a$. Finally let
$\kappa:[0,1]\to[0,1]$ be the function
$\kappa(\omega)=1-\eta^{\prime}(\omega)$, where $\eta^{\prime}$ is defined as
follows. Let $\eta(m,t,\varepsilon,n^{-1})$ be the function from Theorem 4.1.
Let $m,t$ and $n$ be the parameters of the two-prover tensor code test, which
we consider to be fixed. If $\eta$ is a concave function of $\varepsilon$ we
can let $\eta^{\prime}(\omega)=\eta(m,t,\omega,n^{-1})$, with $m,t$ and $n$
fixed by the parameters for If $\eta$ is not concave we proceed as follows.
Since $\eta$ has polynomial dependence on $\varepsilon$ we can write it as a
finite sum $\eta(\varepsilon)=\sum_{i=1}^{M}\alpha_{i}\varepsilon^{c_{i}}$
where $\alpha_{i}=\alpha_{i}(m,t,n^{-1})\in\mathbb{R}$ and
$c_{i}\in\mathbb{R}$ are an increasing sequence of positive constants
depending on the form of $\eta$ only. Moreover, since
$\eta(m,t,\varepsilon,n^{-1})=\mathrm{poly}(m,t)\cdot\mathrm{poly}(\varepsilon,n^{-1})$
then for all $i$, $|\alpha_{i}|=\mathrm{poly}(m,t)\cdot\mathrm{poly}(n^{-1})$.
Now for $\varepsilon\in[0,1]$ we have that
$\eta(\varepsilon)\leq\eta^{\prime\prime}(\varepsilon)=\alpha\varepsilon^{c_{1}}$
where $\alpha=\sum_{i}|\alpha_{i}|$ and so
$\alpha=\mathrm{poly}(m,t)\cdot\mathrm{poly}(n^{-1})$. We then define
$\kappa=1-\eta^{\prime\prime}$.

With this setting, Theorem 4.1 shows that the assumptions of [Vid21, Corollary
4.1] are satisfied, for the game
$\mathfrak{G}=(\mathcal{X},\mathcal{A},\nu,D)$ which is specified by the two-
prover tensor code test. This is because (using terminology from [Vid21]) for
any symmetric PME strategy $({|\psi\rangle},A)$ there is a tracial strategy
$(\tau,A)$ for $\mathfrak{G}$ that reproduces exactly the same distribution on
answers in the game; for this it suffices to define the trace as
$\tau(X)=\frac{1}{d}\mbox{\rm tr}(X)$ for any operator $X$ on the
$d$-dimensional space $\mathcal{H}$ that underlies the strategy $A$.

We apply the conclusion of [Vid21, Corollary 4.1] to the symmetric projective
strategy $\mathscr{S}^{\prime}$. Since $\mathscr{S}$ and hence
$\mathscr{S}^{\prime}$ must be
$(3\varepsilon,\frac{3}{2}\varepsilon,3\varepsilon)$-good according to
Definition 4.6, we deduce that in the terminology from [Vid21],
$\delta_{sync}(\mathscr{S}^{\prime};\nu)\leq 3\varepsilon$. As a consequence
we obtain the existence of a measurement $\\{G^{\prime}_{c}\\}$ on
$\mathcal{H}$ such that

$\operatorname*{\mathbb{E}}_{u\sim[n]^{m}}\sum_{c\in\mathcal{C}^{\otimes
m}}{\langle\psi^{\prime}|}(A^{\prime})^{u}_{c(u)}\otimes
G^{\prime}_{c}{|\psi^{\prime}\rangle}\,\geq\,1-\eta^{\prime\prime}(m,t,\mathrm{poly}(\varepsilon),n^{-1})\;,$
(29)

where

$\eta^{\prime\prime}(m,t,\mathrm{poly}(\varepsilon),n^{-1})=\eta^{\prime}(m,t,\varepsilon+\mathrm{poly}(\varepsilon),n^{-1})+\mathrm{poly}(\varepsilon)=\mathrm{poly}(m,t)\cdot\mathrm{poly}(\varepsilon,n^{-1})\;.$

It remains to derive (26) and (27). Let $G_{c}=(I_{A}\otimes{\langle
0|})G^{\prime}_{c}(I_{A}\otimes{|0\rangle})$ and
$\tilde{G}_{c}=(I_{B}\otimes{\langle
1|})G^{\prime}_{c}(I_{B}\otimes{|1\rangle})$, where $I_{A}$ (resp. $I_{B}$)
denotes the projection on $\mathcal{H}_{A}\subseteq\mathcal{H}^{\prime}$
(resp. $\mathcal{H}_{B}\subset\mathcal{H}^{\prime}$). Then $\\{G_{c}\\}$ and
$\\{\tilde{G}_{c}\\}$ are measurements on $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$ respectively, and (26) and (27) follow directly from (29),
with $\eta_{1}=2\eta^{\prime\prime}$, by expanding ${|\psi^{\prime}\rangle}$
and $(A^{\prime})^{u}_{c(u)}$ on the left-hand side using their definition. ∎

Claim 4.9 almost establishes (23), except that $\\{\tilde{G}_{c}\\}$ is not
necessarily a projective measurement. So in the second step we turn
$\\{G_{c}\\}$ and $\\{G^{\prime}_{c}\\}$ into projective measurements.

######  Claim 4.9.

There exists a projective measurement $\\{G^{\prime}_{c}\\}$ on
$\mathcal{H}_{A}$ (resp. $\\{\tilde{G}^{\prime}_{c}\\}$ on $\mathcal{H}_{B}$)
such that

$\displaystyle A^{u}_{a}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta_{2}}\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\;,$ (30) $\displaystyle\mathbf{1}\otimes\tilde{A}^{u}_{a}$
$\displaystyle\simeq_{\eta_{2}}{G}^{\prime}_{[c\mapsto c(u)\mid
a]}\otimes\mathbf{1}\;,$ (31)

for some
$\eta_{2}=\eta_{2}(m,t,\varepsilon,n^{-1})=\mathrm{poly}(m,t)\cdot\mathrm{poly}(\varepsilon,n^{-1})$.

###### Proof.

We do the proof for $\\{G_{c}\\}$, as the proof for $\\{\tilde{G}_{c}\\}$ is
entirely analogous. Write the Schmidt decomposition
${|\psi\rangle}=\sum_{i}\sqrt{\lambda_{i}}{|u_{i}\rangle}{|v_{i}\rangle}$,
where the $\lambda_{i}$ are non-negative reals and $\\{{|u_{i}\rangle}\\}$
(resp. $\\{{|v_{i}\rangle}\\}$) an orthonormal basis of $\mathcal{H}_{A}$
(resp. $\mathcal{H}_{B}$). Let
$K=\sum_{i}\sqrt{\lambda_{i}}{|u_{i}\rangle}{\langle v_{i}|}$. Let
$G^{u}_{a}=\sum_{c:\,c(u)=a}G_{c}$. Then

$\displaystyle 1-\eta_{1}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{u}\sum_{c}{\langle\psi|}G_{c}\otimes\tilde{A}^{u}_{c(u)}{|\psi\rangle}$
$\displaystyle=\sum_{a}{\langle\psi|}G^{u}_{a}\otimes\tilde{A}^{u}_{a}{|\psi\rangle}$
$\displaystyle=\sum_{a}\mbox{\rm
tr}\big{(}G^{u}_{a}K\tilde{A}^{u}_{a}K^{T}\big{)}$
$\displaystyle\leq\Big{(}\sum_{a}\mbox{\rm
tr}\big{(}G^{u}_{a}\rho_{A}^{1/2}G^{u}_{a}\rho_{A}^{1/2}\big{)}\Big{)}^{1/2}\Big{(}\sum_{a}\mbox{\rm
tr}\big{(}\tilde{A}^{u}_{a}\rho_{B}^{1/2}\tilde{A}^{u}_{a}\rho_{B}^{1/2}\big{)}\Big{)}^{1/2}\;,$
(32)

where the first inequality is (26) and the last inequality follows by Cauchy-
Schwarz, and $\rho_{A}=KK^{\dagger}$ and $\rho_{B}=K^{\dagger}K$. It follows
that

$\displaystyle\sum_{c}\mbox{\rm
tr}\big{(}G_{c}\rho_{A}^{1/2}G_{c}\rho_{A}^{1/2}\big{)}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{a}\mbox{\rm
tr}\big{(}G^{u}_{a}\rho_{A}^{1/2}G^{u}_{a}\rho_{A}^{1/2}\big{)}-\sum_{c\neq
c^{\prime}}\operatorname*{\mathbb{E}}_{u}\sum_{a}1_{c(u)=c^{\prime}(u)=a}\mbox{\rm
tr}\big{(}G_{c}\rho_{A}^{1/2}G_{c^{\prime}}\rho_{A}^{1/2}\big{)}$
$\displaystyle\geq(1-\eta_{1})^{2}-\gamma_{m}\,\sum_{c\neq
c^{\prime}}\mbox{\rm
tr}\big{(}G_{c}\rho_{A}^{1/2}G_{c^{\prime}}\rho_{A}^{1/2}\big{)}$
$\displaystyle\geq 1-2\eta_{1}-\gamma_{m}\;,$ (33)

where the second line follows from (32) for the first term and Proposition
2.18 and $\mbox{\rm tr}(G_{c}\rho_{A}^{1/2}G_{c^{\prime}}\rho_{A}^{1/2})\geq
0$ for all $c,c^{\prime}$ for the second. Using the Cauchy-Schwarz inequality,

$1-2\eta_{1}-\gamma_{m}\,\leq\,\sum_{c}\mbox{\rm
tr}\big{(}G_{c}\rho_{A}^{1/2}G_{c}\rho_{A}^{1/2}\big{)}\,\leq\,\sum_{c}\mbox{\rm
tr}\big{(}G_{c}^{2}\rho_{A}\big{)}\;.$

We apply Lemma 5.1 to the measurement $\\{G_{c}\\}$, with $\tau$ defined by
$\tau(X)=\mbox{\rm tr}(X\rho_{A})$. From the lemma it follows that there
exists a projective measurement $\\{G^{\prime}_{c}\\}$ such that

$\sum_{c}\mbox{\rm
tr}\big{(}(G_{c}-G^{\prime}_{c})^{2}\rho_{A}\big{)}\,=\,O\big{(}2\eta_{1}+\gamma_{m}\big{)}\;.$
(34)

Then

$\displaystyle\operatorname*{\mathbb{E}}_{u}$
$\displaystyle\sum_{c}{\langle\psi|}G^{\prime}_{c}\otimes\tilde{A}^{u}_{c(u)}{|\psi\rangle}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{c}{\langle\psi|}G_{c}\otimes\tilde{A}^{u}_{c(u)}{|\psi\rangle}+\operatorname*{\mathbb{E}}_{u}\sum_{c}{\langle\psi|}(G^{\prime}_{c}-G_{c})\otimes\tilde{A}^{u}_{c(u)}{|\psi\rangle}$
$\displaystyle\geq
1-\eta_{1}-\Big{(}\operatorname*{\mathbb{E}}_{u}\sum_{a}\mbox{\rm
tr}\big{(}((G^{\prime})^{u}_{a}-G^{u}_{a})\rho_{A}^{1/2}((G^{\prime})^{u}_{a}-G^{u}_{a})\rho_{A}^{1/2}\big{)}\Big{)}^{1/2}\Big{(}\operatorname*{\mathbb{E}}_{u}\sum_{a}\mbox{\rm
tr}\big{(}\tilde{A}^{u}_{a}\rho_{B}^{1/2}\tilde{A}^{u}_{a}\rho_{B}^{1/2}\big{)}\Big{)}^{1/2}$
$\displaystyle\geq 1-\eta_{1}-O\big{(}\eta_{1}+\gamma_{m}\big{)}^{1/4}\;,$

where the first inequality uses (27) for the first term and Cauchy-Schwarz for
the second, and the last is justified by the following:

$\displaystyle\operatorname*{\mathbb{E}}_{u}\sum_{a}$ $\displaystyle\mbox{\rm
tr}\big{(}((G^{\prime})^{u}_{a}-G^{u}_{a})\rho_{A}^{1/2}((G^{\prime})^{u}_{a}-G^{u}_{a})\rho_{A}^{1/2}\big{)}$
$\displaystyle\leq 2-2\operatorname*{\mathbb{E}}_{u}\sum_{a}\mbox{\rm
tr}\big{(}(G^{\prime})^{u}_{a}\rho_{A}^{1/2}G^{u}_{a}\rho_{A}^{1/2}\big{)}$
$\displaystyle\leq 2-2\sum_{c}\mbox{\rm
tr}\big{(}G^{\prime}_{c}\rho_{A}^{1/2}G_{c}\rho_{A}^{1/2}\big{)}+\gamma_{m}$
$\displaystyle=2-2\sum_{c}\mbox{\rm
tr}\big{(}(G^{\prime}_{c}-G_{c})\rho_{A}^{1/2}G_{c}\rho_{A}^{1/2}\big{)}+\sum_{c}\mbox{\rm
tr}\big{(}G_{c}\rho_{A}^{1/2}G_{c}\rho_{A}^{1/2}\big{)}+\gamma_{m}$
$\displaystyle\leq 4\eta_{1}+3\gamma_{m}+\Big{(}\sum_{c}\mbox{\rm
tr}\big{(}(G^{\prime}_{c}-G_{c})^{2}\rho_{A}\big{)}\Big{)}^{1/2}\Big{(}\sum_{c}\mbox{\rm
tr}\big{(}G_{c}^{2}\rho_{A}\big{)}\Big{)}^{1/2}$ $\displaystyle\leq
4\eta_{1}+3\gamma_{m}+O\big{(}\sqrt{2\eta_{1}+\gamma_{m}}\big{)}\;,$

where the second inequality uses that $\mbox{\rm
tr}\big{(}G^{\prime}_{c}\rho_{A}^{1/2}G_{c^{\prime}}\rho_{A}^{1/2}\big{)}\geq
0$ for all $c,c^{\prime}$ and Proposition 2.18, the fourth line uses (33), and
the last uses (34). The claimed bound on $\eta_{2}$ follows from the same
bound on $\eta_{1}$ and the bound on $\gamma_{m}$ provided in Proposition
2.18. ∎

With (30) we have established (30). In the last step we obtain (24) and (25).

######  Claim 4.10.

Let $\\{G^{\prime}_{c}\\}$ and $\\{\tilde{G}^{\prime}_{c}\\}$ be projective
measurements that satisfy (30) and (31) respectively. Then

$\displaystyle G^{\prime}_{[c\mapsto c|_{\ell}\mid f]}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta_{3}}\mathbf{1}\otimes B^{\ell}_{f}\;,$ (35)
$\displaystyle G^{\prime}_{c}\otimes\mathbf{1}$
$\displaystyle\simeq_{\eta_{3}}\mathbf{1}\otimes\tilde{G}^{\prime}_{c}\;,$
(36)

for some $\eta_{3}=\mathrm{poly}(\eta_{2},(mt)/n,\varepsilon)$.

###### Proof.

We start with (36). Write

$\displaystyle\sum_{c}G^{\prime}_{c}\otimes\tilde{G}_{c}$
$\displaystyle\simeq_{\gamma_{m}}\operatorname*{\mathbb{E}}_{u}\sum_{a}{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\otimes\tilde{G}^{\prime}_{[c\mapsto c(u)\mid a]}$ (37)
$\displaystyle\simeq_{\eta^{\prime}_{3}}\operatorname*{\mathbb{E}}_{u}\sum_{a}A^{u}_{a}\otimes\tilde{A}^{u}_{a}$
(38) $\displaystyle\simeq_{3\xi}\mathbf{1}\otimes\mathbf{1}\;,$ (39)

where $\eta^{\prime}_{3}=2\sqrt{2\eta_{2}}$ and recall that
$\xi=3\varepsilon$. Each of the three approximations above is justified as
follows. For (37), form the difference

$\displaystyle\sum_{c,c^{\prime}}\operatorname*{\mathbb{E}}_{u}1_{c(u)=c^{\prime}(u)}G^{\prime}_{c}\otimes\tilde{G}_{c^{\prime}}$
$\displaystyle\leq\gamma_{m}\mathbf{1}\otimes\mathbf{1}\;,$

using Proposition 2.18. For (38), write

$\displaystyle\operatorname*{\mathbb{E}}_{u}$
$\displaystyle\sum_{a}{G}^{\prime}_{[c\mapsto c(u)\mid
a]}\otimes\tilde{G}^{\prime}_{[c\mapsto c(u)\mid
a]}-\operatorname*{\mathbb{E}}_{u}\sum_{a}A^{u}_{a}\otimes\tilde{A}^{u}_{a}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u}\sum_{a}\big{(}{G}^{\prime}_{[c\mapsto
c(u)\mid
a]}\otimes\mathbf{1}-\mathbf{1}\otimes\tilde{A}^{u}_{a}\big{)}\big{(}\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid
a]}\big{)}+\operatorname*{\mathbb{E}}_{u}\sum_{a}\big{(}\mathbf{1}\otimes\tilde{A}^{u}_{a}\big{)}\big{(}\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}-{A}^{u}_{a}\otimes\mathbf{1}\big{)}\;.$

Each of the two terms above is bounded in the same way. We do it for the
first:

$\displaystyle\operatorname*{\mathbb{E}}_{u}$
$\displaystyle\sum_{a}{\langle\psi|}\big{(}{G}^{\prime}_{[c\mapsto c(u)\mid
a]}\otimes\mathbf{1}-\mathbf{1}\otimes\tilde{A}^{u}_{a}\big{)}\big{(}\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\big{)}{|\psi\rangle}$
$\displaystyle\leq\Big{(}\operatorname*{\mathbb{E}}_{u}\sum_{a}{\langle\psi|}\big{(}{G}^{\prime}_{[c\mapsto
c(u)\mid
a]}\otimes\mathbf{1}-\mathbf{1}\otimes\tilde{A}^{u}_{a}\big{)}^{2}{|\psi\rangle}\Big{)}^{1/2}\Big{(}\operatorname*{\mathbb{E}}_{u}\sum_{a}{\langle\psi|}\big{(}\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\big{)}^{2}{|\psi\rangle}\Big{)}^{1/2}$
$\displaystyle\leq\sqrt{2\eta_{2}}\;,$

by (31) and the fact that $\\{G^{\prime}\\}$ and $\\{\tilde{A}\\}$ are
families of projective measurements. Finally, (39) follows directly from the
synchronicity condition.

To conclude we show (35).

$\displaystyle\operatorname*{\mathbb{E}}_{\ell}\sum_{f}{G}^{\prime}_{[c\mapsto
c|_{\ell}\mid f]}\otimes\tilde{B}^{\ell}_{f}$
$\displaystyle\simeq_{\gamma_{m}}\operatorname*{\mathbb{E}}_{\ell}\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a}{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\otimes\tilde{B}^{\ell}_{f\mapsto f(u)\mid a}$ (40)
$\displaystyle\simeq_{\eta^{\prime\prime}_{3}}\operatorname*{\mathbb{E}}_{\ell}\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a}A^{u}_{a}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}$ (41)
$\displaystyle\simeq_{\eta_{2}}\mathbf{1}\otimes\mathbf{1}\;,$ (42)

where $\eta^{\prime\prime}_{3}=\sqrt{2\eta^{\prime}_{3}}+\sqrt{4\varepsilon}$.
We justify each of these three approximations as follows. For (40), form the
difference

$\operatorname*{\mathbb{E}}_{\ell}\sum_{f,f^{\prime}}\operatorname*{\mathbb{E}}_{u\in\ell}1_{f(u)=f^{\prime}(u)}G^{\prime}_{[c\mapsto
c|_{\ell}\mid f^{\prime}]}\otimes
B^{\ell}_{f}\,\leq\,\gamma_{1}\,\mathbf{1}\otimes\mathbf{1}\,\leq\,\gamma_{m}\,\mathbf{1}\otimes\mathbf{1}\;,$

by Proposition 2.18. For (41), write

$\displaystyle\operatorname*{\mathbb{E}}_{\ell}$
$\displaystyle\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a}{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\otimes\tilde{B}^{\ell}_{f\mapsto f(u)\mid
a}-\operatorname*{\mathbb{E}}_{\ell}\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a}A^{u}_{a}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\ell}\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a}{\langle\psi|}\big{(}{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\otimes\mathbf{1}-\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\big{)}\big{(}\mathbf{1}\otimes\tilde{B}^{\ell}_{f\mapsto f(u)\mid
a}\big{)}{|\psi\rangle}$
$\displaystyle\qquad+\operatorname*{\mathbb{E}}_{\ell}\operatorname*{\mathbb{E}}_{u\in\ell}\sum_{a}{\langle\psi|}\big{(}\mathbf{1}\otimes\tilde{G}^{\prime}_{[c\mapsto
c(u)\mid a]}\big{)}\big{(}\mathbf{1}\otimes\tilde{B}^{\ell}_{f\mapsto f(u)\mid
a}-A^{u}_{a}\otimes\mathbf{1}\big{)}{|\psi\rangle}\;.$

Each of the two terms above is bounded as previously, using (37) for the first
and the consistency condition between points and lines for the second. This
gives
$\eta^{\prime\prime}_{3}=\sqrt{2(\gamma_{m}+\eta^{\prime}_{3}+3\xi)}+\sqrt{4\varepsilon}$.
Finally, (42) is by (30). The claimed bound on $\eta_{3}$ follows from
Proposition 2.18 to bound $\gamma_{m}$ and $\xi\leq 3\varepsilon$. ∎

The theorem follows using the bound on $\eta_{2}$ given in Claim 4.9. ∎

##  5 Self-improvement

In this section we prove Lemma 4.2. The proof of the lemma relies on three
main ingredients.

##### Orthogonalization.

The first is a lemma that allows us to round a submeasurement that is self-
consistent to a projective measurement. The lemma first appears in [KV11] for