# Constant-sized correlations are sufficient to robustly self-test maximally
entangled states with unbounded dimension

Honghao Fu 111Email<EMAIL_ADDRESS>Joint Center for Quantum Information and
Computer Science, Institute for Advanced Computer Studies and Department of
Computer Science,University of Maryland, College Park, MD 20742, USA

###### Abstract

We show that for any prime odd integer $d$, there exists a correlation of size
$\Theta(r)$ that can robustly self-test a maximally entangled state of
dimension $4d-4$, where $r$ is the smallest multiplicative generator of
$\mathbb{Z}_{d}^{\times}$. The construction of the correlation uses the
embedding procedure proposed by Slofstra (Forum of Mathematics, Pi. Vol. $7$,
($2019$)). Since there are infinitely many prime numbers whose smallest
multiplicative generator is at most $5$ (M. Murty The Mathematical
Intelligencer $10.4$ ($1988$)), our result implies that constant-sized
correlations are sufficient for robust self-testing of maximally entangled
states with unbounded local dimension.

##  1 Introduction

The certification of a quantum device is an important building block for many
quantum information processing tasks, especially when the devices are provided
by some untrusted vendor. We would like such certification to be done based
solely on the observed measurement statistics and with the only assumption
that any local device cannot communicate their own inputs to the other local
devices. The measurement statistics are referred to as correlations.

It has been shown that certain quantum correlations require the distant
parties to share a particular entangled state up to some local isometry. This
phenomenon is referred to as self-testing. If we can further prove that, when
the observed correlation deviates from the ideal one to some extent, the
shared state is still close to the ideal state up to some local isometry, then
we say the self-test is robust.

The fact that the verifier only interacts classically with the unknown device
makes self-testing a powerful tool for applications in quantum cryptography
and computational complexity theory. It allows a classical party to delegate
quantum computations to some untrusted service provider and verify that the
computations are performed honestly and correctly [RUV13, CGJV19]. Self-
testing also becomes a critical component of the security proofs of device-
independent quantum cryptographic protocols [MY98, FM18]. Since the setting of
multi-prover interactive proof systems is similar to a self-test, self-testing
arguments also help to prove lower bounds of the computational power of
entanglement-assisted multiprover interactive proof systems [FJVY19, NW19].

The case of robust self-testing of the EPR pair,

$\displaystyle|EPR\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),$

is fully understood. The techniques for this case are first introduced in
[MYS12], then improved in [BP15]. Robust self-testing of partially entangled
qubits is proved later in [YN13], the authors of which also propose an
generalized swap-isometry that can be used to robustly self-test large
dimensional maximally entangled states. Robust self-testings of tensor product
of maximally and partially entangled qubits are proved in [Col16, NV17, NV18],
with the last one being the one with the smallest input and output alphabets.
Self-testing of all pure bipartite entangled states is proved in [CGS17]. The
authors of [CGS17] construct a family of correlations such that an entangled
state of any local dimension has a self-testing correlation in this family. To
generate a correlation in the family, Alice and Bob use constant-sized input
alphabets but size-$d$ output alphabets, where $d$ is the local dimension of
the entangled state. The robustness of this family of correlations is proved
in [CS17b].

Our work aims at minimizing the sizes of the input and output alphabets of a
correlation that can self-test a maximally entangled states with large local
dimension. For comparisons, all the correlations used in the results listed
above have either input or output alphabets with sizes dependent on the local
dimension of the entangled state. Our progress is summarized in the following
theorem.

######  Theorem 1.1 (Informal).

There exists an infinite-sized set $D$ of odd prime numbers such that, for any
$d\in D$, the maximally entangled state of local dimension $4(d-1)$ can be
robustly self-tested with constant-sized input and output alphabets.

The formal statement of this theorem is given in Theorem 6.17 and Theorem
6.18.

The set $D$ is, specifically, the set of all odd prime numbers whose smallest
primitive root is either $2$, $3$, or $5$, We say that $r$ is a primitive root
of $d$ if $r$ is the multiplicative generator of the group
$\mathbb{Z}_{d}^{\times}$. It has been shown that $D$ has infinitely many
elements [Mur88].

###  1.1 Proof overview

To prove Theorem 1.1, we construct a correlation with $\Theta(r)$-sized input
and constant-sized output alphabets for each odd prime number $d$ whose
smallest primitive root is $r$. This correlation is denoted by
$\mathfrak{C}(d,r)$. Note that the size of neither the input nor the output
alphabet of $\mathfrak{C}(d,r)$ depends on $d$. Once we prove
$\mathfrak{C}(d,r)$ can robustly self-test a maximally entangled state of
dimension $4(d-1)$, we apply it to all $d\in D$ and prove Theorem 1.1.

The correlation $\mathfrak{C}(d,r)$ contains a winning correlation of a
specially-designed binary linear system game. In a general linear system game,
Alice is given a random equation from a linear system and she should give an
assignment to each variable of the equation. Bob is asked to assign a value to
a random variable of the chosen equation. They win the game if Alice’s
assignment satisfies the equation and Bob’s assignment to the variable matches
Alice’s assignment. A widely-used and thoroughly-studied example of a linear
system game is the Magic Square game [Ara04]. In this game, the linear system
is

$\displaystyle x_{1}+x_{2}+x_{3}=0$ $\displaystyle x_{4}+x_{5}+x_{6}=0$
$\displaystyle x_{7}+x_{8}+x_{9}=0$ $\displaystyle x_{1}+x_{4}+x_{7}=0$
$\displaystyle x_{2}+x_{5}+x_{8}=1$ $\displaystyle x_{3}+x_{6}+x_{9}=0.$

Using two copies of $|EPR\rangle$, the Magic square game can be won with
certainty. It has been shown that if a strategy can win this game almost
perfectly, the shared state must be close to $|EPR\rangle^{\otimes 2}$ up to
some local isometry [WBMS16]. So we say that the Magic Square game can
robustly self-test $|EPR\rangle^{\otimes 2}$. The key observation that leads
to the self-testing proof is that a winning strategy must contain binary
observables $X$ and $Z$ that satisfy the anti-commutation relation

$\displaystyle XZ=-ZX.$

Intuitively, we can think of the Magic Square game as a way to enforce the
anti-commutation relation [CS17a].

Our linear system game, $LS(r)$, is designed to enforce the relation

$\displaystyle UOU^{\dagger}=O^{r},$ (1)

for unitaries $U$ and $O$, and some integer $r$. The inspiration comes from
Slofstra’s seminal work [Slo19], where he proves that there exists a binary
linear system game that cannot be won by any finite-dimensional quantum
strategy but a limit of finite-dimensional strategies can win it perfectly. It
implies that the set of quantum correlations generated by finite-dimensional
strategies is not closed. In the proof, he proposes and validates a new way to
design binary linear system games to enforce conjugacy relations of the form
$XYX^{\dagger}=Z$ for unitaries $X,Y$ and $Z$.

Following Slofstra’s design, the sizes of the input alphabets for Alice and
Bob are of order $\Theta(r)$, and the answer sets are of size $\Theta(1)$ in
$LS(r)$.

The reason that we choose eq. 1 to be the relation enforced by $LS(r)$ is the
following. Winning $LS(r)$ guarantees that the winning strategy contains
binary observables $M_{1},M_{2},M_{3},M_{4}$ on Alice’s side and
$N_{1},N_{2},N_{3},N_{4}$ on Bob’s side such that

$\displaystyle U=M_{3}M_{4}=N_{3}N_{4}$ $\displaystyle
O=M_{1}M_{2}=N_{1}N_{2}$

with $U$ and $O$ satisfying eq. 1. Moreover, if we can certify that the
unitary $O$ has the eigenvalue $\omega_{d}:=e^{i2\pi/d}$ where $r$ is a
primitive root of $d$, eq. 1 automatically guarantees that the spectrum of $O$
contains $\\{\omega_{d}^{j}\\}_{j=1}^{d-1}$. It also guarantees that the
eigenspace of each distinct eigenvalue has the same dimension.

The strong guarantee of eq. 1 is built on the assumption of an eigenvalue of
the unitary $O$, so the next problem is how to certify that $O$ has eigenvalue
$\omega_{d}$. In order to solve it, we design $\mathfrak{C}(d,r)$ to contain
an extension of the optimal correlation that achieves the maximal violation of
the weighted CHSH inequality. The $\alpha$-weighted CHSH inequality is defined
by

$\displaystyle\mathcal{I}_{\alpha}=\alpha\langle
M_{1}N_{1}\rangle+\alpha\langle M_{1}N_{2}\rangle+\langle
M_{2}N_{1}\rangle-\langle M_{2}N_{2}\rangle\leq 2|\alpha|,$

where $M_{x}$ and $N_{y}$ for $x,y\in\\{1,2\\}$ are some binary observables.
Define $\mu=\arctan(1/\alpha)$,

$\displaystyle\sigma_{z}=|0\rangle\langle 0|-|1\rangle\langle 1|$
$\displaystyle\sigma_{x}=|0\rangle\langle 1|+|1\rangle\langle 0|,$

which are the Pauli-Z and Pauli-X operators. This inequality is maximally
violated when the shared state is $|EPR\rangle$, Alice’s binary observables
are

$\displaystyle\tilde{M}_{1}=\sigma_{z}$
$\displaystyle\tilde{M}_{2}=\sigma_{x},$

and Bob’s binary observables are

$\displaystyle\tilde{N}_{1}=\cos(\mu)\sigma_{z}+\sin(\mu)\sigma_{x}$
$\displaystyle\tilde{N}_{2}=\cos(\mu)\sigma_{z}-\sin(\mu)\sigma_{x}?$

We first prove that the maximal violation of $\mathcal{I}_{\alpha}$ can
robustly self-test the shared state $|\psi\rangle$ and the observables
$\tilde{M}_{1},\tilde{M}_{2}$ and $\tilde{N}_{1},\tilde{N}_{2}$ in Section 4.
Then we notice that

$\displaystyle\tilde{N}_{1}\tilde{N}_{2}=\cos(2\mu)\mathbb{1}-\sin(2\mu)\sigma_{z}\sigma_{x}$

has eigenvalues $e^{i2\mu}$ and $e^{-i2\mu}$.

Therefore, in the extended correlation, we set $\alpha=\cot(-\pi/d)$ for some
odd prime $d$ whose primitive root is $r$, and ask Alice and Bob to reuse the
observables $M_{1},M_{2}$ and $N_{1},N_{2}$ from a winning strategy of
$LS(r)$. Then we can certify that the unitary $O=M_{1}M_{2}=N_{1}N_{2}$ has
eigenvalues $\omega_{d}$ and $\omega_{d}^{-1}$. Combining this observation
with the fact that $O$ satisfy the relation eq. 1, we can conclude that all
the eigenvalues of $O$ contains $\\{\omega_{d}^{j}\\}_{j=1}^{d-1}$, and the
eigenspaces of all such eigenvalues have the same dimension.

The full correlation $\mathfrak{C}(d,r)$ is produced by an ideal strategy that
can win $LS(r)$ perfectly and can reproduce the aforementioned extended
correlation perfectly. Combining the implications of a quantum strategy to win
$LS(r)$ and reproduce the extended correlation, we can prove that the
correlation $\mathfrak{C}(d,r)$ can robustly self-test the state
$|\tilde{\psi}\rangle$ defined by

$\displaystyle|\tilde{\psi}\rangle=\frac{1}{\sqrt{d-1}}\left(\sum_{j=1}^{d-1}|j\rangle|d-j\rangle\right)\otimes|EPR\rangle^{\otimes
2}.$

More precisely, we prove that if some quantum strategy using the shared state
$|\psi\rangle$ can produce a correlation that is within trace distance
$\epsilon$ to $\mathfrak{C}(d,r)$, then there exist an local isometry
$\Phi_{A}\otimes\Phi_{B}$ and a state $|junk\rangle$ such that

$\displaystyle\lVert\Phi_{A}\otimes\Phi_{B}(|\psi\rangle)-|junk\rangle\otimes|\tilde{\psi}\rangle\rVert=O(d^{5/2}r^{d}\epsilon^{1/8}).$
(2)

Note that the isometry $\Phi_{A}\otimes\Phi_{B}$ only involves local
operations on Alice’s and Bob’s side. The isometry $\Phi_{A}\otimes\Phi_{B}$
captures the essence of the generalized swap-isometry proposed in [YN13], but
it is constructed in a different way.

As mentioned at the start of this subsection, the last step of proving Theorem
1.1 is to apply the general self-testing result of $\mathfrak{C}(d,r)$ to the
prime numbers with a primitive root $2$, $3$ or $5$. The theorem follows
naturally from the fact that there are infinitely many such prime numbers
[Mur88].

###  1.2 Structure of the paper

We start with notations and background information in Section 2. Since the
correlation we designed can win a special linear system game and satisfy an
extended weighted CHSH test, we introduce the linear system game in Section 3
and the extended weighted CHSH test in Section 4. Then we give the correlation
$\mathfrak{C}(d,r)$ and the ideal strategy to generate it in Section 5.
Section 6 is devoted to the robust self-testing proof. We end this paper with
conclusions in Section 7.

##  2 Preliminaries and notations

###  2.1 Notations and mathematical background

The EPR pair is denoted by

$\displaystyle|EPR\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),$ (3)

and the Pauli operators are denoted by

$\displaystyle\sigma_{x}=|0\rangle\langle 1|+|1\rangle\langle 0|$
$\displaystyle\sigma_{z}=|0\rangle\langle 0|-|1\rangle\langle 1|.$ (4)

The $d$-th root of unity is denoted by $\omega_{d}:=e^{2\pi i/d}$. Note that
we only work with finite Hilbert spaces in our work.

For quantum states and operators on different Hilbert spaces, we use
subscripts to label them. For example, $O_{A}$ is an operator on Alice’s side
and $|0\rangle_{B}$ is a state on Bob’s side. The only exception is when we
label projectors used in a quantum strategy defined below. In this case, the
subscript is the input and the superscript is the output. For example,
$M_{x}^{a}$ is Alice’s projector for input $x$ and output $a$. Operators
defined by the projectors follow the same convention, for example,
$M_{x}:=M_{x}^{0}-M_{x}^{1}$ is a binary observable. If we add tilde to an
operator, then this operator is fully characterized and belongs to some ideal
strategy. Otherwise, the operator is general and the only assumption is that
it is finite-dimensional.

We use the following notation for the closeness between quantum states.

$\displaystyle|u\rangle\simeq_{\epsilon}|v\rangle\iff\lVert|u\rangle-|v\rangle\rVert\leq\epsilon.$
(5)

Similarly, for numbers $a,b\in\mathbb{C}$, the closeness is denoted by
$a\simeq_{\epsilon}b\iff\lvert a-b\rvert\leq\epsilon$.

We use some basic number theory in our work.

######  Definition 2.1.

A primitive root of a prime number $d$ is an integer $r$ such that $r$ has
multiplicative order $d-1$ in the ring of integers modulo $d$,
$\mathbb{Z}_{d}$.

In other words, $r$ is a multiplicative generator of
$\mathbb{Z}_{d}^{\times}$.

We also need some basic notions of group presentation and group
representation, so We introduce them below. For more contexts, please refer to
[DF04].

Let $S$ be a set of letters. We denote by $\mathcal{F}(S)$ the _free group
generated by $S$_, which consists of all finite words made from
$\\{s,s^{?1}|s\in S\\}$ such that no $ss^{?1}$ or $s^{?1}s$ appears as a
substring for any $s$, where $s^{-1}$ denotes the inverse of $s$. The group
law is given by concatenation and cancellation. For a more formal treatment,
we refer to Section $6.3$ of [DF04].

######  Definition 2.2 (Group presentation).

Given a set $S$, let $\mathcal{F}(S)$ be the free group generated by $S$ and
$R$ be a subset of $\mathcal{F}(S)$. Then $\langle S:R\rangle$ denotes the
quotient of $\mathcal{F}(S)$ by the normal subgroup generated by $R$. If the
group $G$ is isomorphic to $\langle S:R\rangle$, then we say $G$ has a
presentation $\langle S:R\rangle$.

If both sets $S$ and $R$ are finite, then we say the group $G=\langle
S:R\rangle$ is _finitely-presentable_. The elements of $S$ are the
_generators_ and the elements of $R$ are the _relations_. When we refer to an
equation of the form $a=b$ with $a,b\in\mathcal{F}(S)$ as a “relation,” it is
understood that we mean the element $ab^{-1}\in R$. There are two types of
relations that we will be working with. Considering a subset of generators
$\\{s_{j}\\}_{j=1}^{n}\subset S$ such that $s_{j_{1}}\neq s_{j_{2}}$ if
$j_{1}\neq j_{2}$, the relations of the form $\Pi_{j=1}^{n}s_{j}=e$, where $e$
is the identity element, are called _linear relations_ ; and the relations of
the form $s_{i}s_{j}s_{i}^{-1}=s_{k}$ for some $i\neq j$ are called _conjugacy
relations_.

There are two special types of groups that we will work with in Section 3. We
give the definitions below.

######  Definition 2.3.

Suppose $C\subset[n]\times[n]\times[n]$, where $[n]=\\{1,2\dots n\\}$. Let

$\displaystyle\Gamma=\langle\\{s_{i}\\}_{i\in[n]}:\\{s_{i}^{2}=e\\}_{i\in[n]}\cup\\{s_{i}s_{j}s_{i}=s_{k}\\}_{(i,j,k)\in
C}\rangle.$

We say a group is a conjugacy group if it has a presentation of this form.

A conjugacy group is a special case of what Slofstra defined as a linear-plus-
conjugacy group (Definition $26$ of [Slo19]). The difference is that a
conjugacy group does not have linear relations. The next definition follows
the definition of a nice linear-plus-conjugacy group (Definition $28$ of
[Slo19]).

######  Definition 2.4.

Suppose $C\subset[n]\times[n]\times[n]$, where $[n]=\\{1,2\dots n\\}$. Let

$\displaystyle\Gamma=\langle\\{s_{i}\\}_{i\in[n]}\cup\\{s_{jk}\\}_{(i,j,k)\in
C}:\\{s_{i}^{2}=e\\}_{i\in[n]}\cup\\{s_{jk}^{2}=e,s_{i}s_{j}s_{i}=s_{k},s_{jk}s_{j}s_{k}=e\\}_{(i,j,k)\in
C}\rangle.$

We say a group is a nice conjugacy group if it has a presentation of this
form.

The relation $s_{jk}s_{j}s_{k}=e$ implies that $s_{j}$ commutes with $s_{k}$
because

$\displaystyle[s_{j},s_{k}]=s_{j}s_{k}s_{j}s_{k}=s_{jk}^{2}=e.$

Next we give the definition of a group representation.

######  Definition 2.5.

A representation of a group $G$ on the finite Hilbert space $\mathcal{H}$ is a
homomorphism from $G$ to the group of invertible linear operators on
$\mathcal{H}$.

The last concept of group theory that we need is a group embedding.

######  Definition 2.6 (Group embedding).

An embedding of $G$ into $K$ is an injective group homomorphism:
$\phi:G\rightarrow K$.

###  2.2 Nonlocal games

In a nonlocal game, there are two players, Alice and Bob and each of them is
requested to give an answer for a randomly chosen question. We denote Alice’s
question set by $\mathcal{X}$ and her family of answer sets by
$\\{\mathcal{A}_{x}\\}_{x}$ for each $x\in\mathcal{X}$. Similarly, Bob’s
question set is denoted by $\mathcal{Y}$ and his family of answer sets is
denoted by $\\{\mathcal{B}_{y}\\}_{y}$ for each $y\in\mathcal{Y}$. Note that
when $\mathcal{A}_{x}=\mathcal{A}$ for each $x\in\mathcal{X}$, we simply say
the output alphabet is $\mathcal{A}$, and we follow this convention on Bob’s
side too. The probability distribution over the questions of a nonlocal game
is given by a functions $\pi:\mathcal{X}\times\mathcal{Y}\rightarrow[0,1]$, A
nonlocal game also comes with a family of functions
$\\{V_{(x,y)}:\mathcal{A}_{x}\times\mathcal{B}_{y}\rightarrow\mathbb{R}\\}_{x,y}$
for each $(x,y)\in\mathcal{X}\times\mathcal{Y}$, which is the family of
scoring functions. Note that when $\mathcal{A}_{x}=\mathcal{A}$ for all $x$
and $\mathcal{B}_{y}=\mathcal{B}$ for all $y$, we write the scoring function
as
$V:\mathcal{A}\times\mathcal{B}\times\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$.

We also define a nonlocal test to be a tuple
$(\mathcal{X},\mathcal{Y},\\{\mathcal{A}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{B}_{y}\\}_{y\in\mathcal{Y}},\pi)$,
where
$\mathcal{X},\mathcal{Y},\\{\mathcal{A}_{x}\\}_{x},\\{\mathcal{B}_{y}\\}_{y}$
and $\pi$ are as defined for a nonlocal game. Hence, a nonlocal test does not
have scoring functions.

A quantum strategy of a nonlocal game or a nonlocal test presented in terms of
projective measurements consists of projective measurements
$\\{\\{M_{x}^{a}\\}_{a\in\mathcal{A}_{x}}\\}_{x\in\mathcal{X}}$ on Alice’s
side, $\\{\\{N_{y}^{b}\\}_{b\in\mathcal{B}_{y}}\\}_{y\in\mathcal{Y}}$ on Bob’s
side, and a shared state $|\psi\rangle$. By projective measurements, we mean
that $(M_{x}^{a})^{2}=M_{x}^{a}=(M_{x}^{a})^{\dagger}$ and
$(N_{y}^{b})^{2}=N_{y}^{b}=(N_{y}^{b})^{\dagger}$. Then Alice and Bob’s
quantum strategy produces the conditional probability distribution

$\displaystyle P(a,b|x,y)=\langle\psi|M_{x}^{a}\otimes N_{y}^{b}|\psi\rangle,$
(6)

for each $(x,y)\in\mathcal{X}\times\mathcal{Y}$ and
$(a,b)\in\mathcal{A}_{x}\times\mathcal{B}_{y}$. Note that the tensor product
structure indicates that the two parties cannot communicate with each other,
which is the reason why we say such task is nonlocal. For simplicity we omit
the tensor product symbol between operators acting on different Hilbert spaces
in the rest of the work. If
$M_{x}^{a}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A}$ and
$N_{y}^{b}:\mathcal{H}_{B}\rightarrow\mathcal{H}_{B}$, then
$M_{x}^{a}N_{y}^{b}:\mathcal{H}_{A}\otimes\mathcal{H}_{B}\rightarrow\mathcal{H}_{A}\otimes\mathcal{H}_{B}$.

######  Definition 2.7.

Given input alphabets: $\mathcal{X}$ and $\mathcal{Y}$, and families of output
alphabets: $\\{\mathcal{A}_{x}\\}_{x\in\mathcal{X}}$ and
$\\{\mathcal{B}_{y}\\}_{y\in\mathcal{Y}}$, a correlation is a family of
conditional probability distributions
$\\{P(a,b|x,y):a\in\mathcal{A}_{x},b\in\mathcal{B}_{y}\\}_{x\in\mathcal{X},y\in\mathcal{Y}}$.

The size of a correlation is the sum of the sizes of the conditional
probability distributions in the correlation.

A particular type of nonlocal games that we are interested in is called binary
linear system games.

######  Definition 2.8 (Binary linear system game).

Let $Hx=c$ be an $m\times n$ system of linear equations over
$\mathbb{Z}_{2}=\\{0,1\\}$ (meaning that $H$ is an $m$-by-$n$ matrix with
entries in $\mathbb{Z}_{2}$ and $c$ is a length-$n$ vector with entries in
$\mathbb{Z}_{2}$). The associated linear system game involves two players
Alice and Bob. The input and output alphabets are

$\displaystyle\mathcal{X}=\\{I_{i}\\}_{i=1}^{m}$
$\displaystyle\mathcal{Y}=\\{1\dots n\\}$
$\displaystyle\mathcal{A}_{I_{i}}=(\mathbb{Z}_{2})^{I_{i}}$
$\displaystyle\mathcal{B}=\mathbb{Z}_{2},$

where $I_{i}=\\{j:H(i,j)=1\\}$. When Alice and Bob answer with
$\boldsymbol{a}$ and $b$ for questions $I_{i}$ and $j$ respectively, the
scoring functions are defined by

$\displaystyle V_{(I_{i},j)}(\boldsymbol{a},b)=\begin{cases}1,\quad\text{if
}\sum_{k\in I_{i}}H(i,k)a(k)\equiv c(i)\pmod{2}\text{ and }a(j)=b\\\
0,\quad\text{otherwise.}\end{cases}$ (7)

A widely-used example of a linear system game is the Magic Square game
introduced in [Ara04], which have equations

$\displaystyle x_{1}+x_{2}+x_{3}=0$ $\displaystyle x_{4}+x_{5}+x_{6}=0$
$\displaystyle x_{7}+x_{8}+x_{9}=0$ $\displaystyle x_{1}+x_{4}+x_{7}=0$
$\displaystyle x_{2}+x_{5}+x_{8}=1$ $\displaystyle x_{3}+x_{6}+x_{9}=0.$

Note that the equations above are taken modulo $2$. We follow this convention
in the rest of our work. For the formulation of a general linear system games
over $\mathbb{Z}_{d}$, we refer to Section $3.1$ of [CS17a].

######  Definition 2.9 (Binary observable strategy of a linear system game).

A quantum strategy presented in terms of binary observables for the binary
linear system game $Hx=c$ consists of

  1. 1.

a pair of finite-dimensional Hilbert spaces $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$;

  2. 2.

a collection of binary observables $N_{j}$, $1\leq j\leq n$, on
$\mathcal{H}_{B}$ such that $N_{j}^{2}=\mathbb{1}$ for every $1\leq j\leq n$;

  3. 3.

a collection of binary observables $M_{ij}$, $1\leq i\leq m$, $1\leq j\leq n$
on $\mathcal{H}_{A}$ such that

    1. (a)

$M_{ij}^{2}=\mathbb{1}$ for every $i,j$, and

    2. (b)

$M_{il}M_{ik}=M_{ik}M_{il}$ for every $i,l,k$ such that $H(i,l)=H(i,k)=1$;

and

  4. 4.

a quantum state $|\psi\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$.

Note that a measurement strategy of a binary linear system game can be
converted to a binary observable strategy. Let a measurement strategy be
$(\\{\\{M_{i}^{\boldsymbol{a}}\\}_{\boldsymbol{a}\in
X_{i}}\\}_{i=1}^{m},\\{\\{N_{j}^{b}\\}_{b=0}^{1}\\}_{j=1}^{n},|\psi\rangle)$,
where $X_{i}$ is the answer set of equation $i$. The corresponding binary
observable strategy consists of, $|\psi\rangle$, $N_{j}:=N_{j}^{0}-N_{j}^{1}$
and

$\displaystyle
M_{ij}:=\sum_{\boldsymbol{a}:a(j)=0}M_{i}^{\boldsymbol{a}}-\sum_{\boldsymbol{a}:a(j)=1}M_{i}^{\boldsymbol{a}}$

for $1\leq i\leq m$ and $1\leq j\leq n$. Hence, in the rest of the work, we
focus on binary observable strategies of linear system games. Specifically, we
assume that Alice has a binary observable for each variable in each equation,
so when she is asked the assignment of a particular variable, she simply
measures according to the corresponding observable of that variable.

A perfect binary observable strategy for the linear system game associated
with $Hx=c$ can be constructed from a finite-dimensional representation of a
finitely presentable group over $\mathbb{Z}_{2}$, called the solution group.

######  Definition 2.10 (Solution group of a linear system game).

Let $Hx=c$ be an $m\times n$ linear system. The solution group of this system
is the group

$\displaystyle\Gamma(H,c):=\langle x_{1},\dots x_{n},J:$ $\displaystyle
J^{2}=x_{i}^{2}=e,Jx_{i}=x_{i}J\text{ for all }1\leq i\leq n,$
$\displaystyle\Pi_{j=1}^{n}x_{j}^{H(i,j)}=J^{c(i)}\text{ for all }1\leq i\leq
m,\text{ and }$ $\displaystyle x_{l}x_{k}=x_{k}x_{l}\text{ if
}H(i,k)=H(i,l)=1\text{ for some }i\rangle.$

The relation $J^{2}=x_{i}^{2}=e$ means that all the generators are of order
$2$. Let $\Psi$ be a finite-dimensional representation of $\Gamma(H,c)$ such
that $\Psi(J)=-\mathbb{1}$ on the carrier space $\mathbb{C}^{d}$. Then a
perfect strategy for the linear system game ($Hx=c$) has

  1. 1.

$M_{ij}=\Psi(x_{j})$ for all $1\leq i\leq m$ and $1\leq j\leq n$,

  2. 2.

$N_{j}=\Psi(x_{j})^{\intercal}$ for all $1\leq j\leq n$,

  3. 3.

the maximally entangled state
$|\psi\rangle=\frac{1}{\sqrt{d}}\sum_{k=1}^{d}|k\rangle|k\rangle$.

###  2.3 The weighted CHSH inequality [AMP12].

The weighted CHSH inequality a variation of the CHSH inequality [CHSH69]. We
formulate it as a nonlocal game. The input alphabets and output alphabets of
Alice and Bob are $\mathcal{X}=\mathcal{Y}=\\{1,2\\}$ and
$\mathcal{A}=\mathcal{B}=\mathbb{Z}_{2}$. The scoring function for the
$\alpha$-weighted CHSH test, when $|\alpha|\geq 1$, is defined by

$\displaystyle V(a,b,x,y)_{\alpha-
CHSH}=\begin{cases}\alpha(-1)^{a+b},&\text{if }x=1,\\\ (-1)^{a+b},&\text{if
}x=2,\;y=1,\\\ (-1)^{1+a+b},&\text{if }x=y=2.\end{cases}$ (8)

The input distribution is $\pi(x,y)=1/4$ for all
$(x,y)\in\mathcal{X}\times\mathcal{Y}$.

Let Alice and Bob’s quantum strategy in terms of projectors be
$(\\{\\{M_{x}^{a}\\}_{a}\\}_{x},\\{\\{N_{y}^{b}\\}_{b}\\}_{y},|\psi\rangle)$.
We define binary observables $M_{x}:=M_{x}^{0}-M_{x}^{1}$ and
$N_{y}:=N_{y}^{0}-N_{y}^{1}$ from Alice and Bob’s projectors. The weighted
CHSH inequality states that

$\displaystyle\mathcal{I}_{\alpha}=\alpha\langle
M_{1}N_{1}\rangle+\alpha\langle M_{1}N_{2}\rangle+\langle
M_{2}N_{1}\rangle-\langle M_{2}N_{2}\rangle\leq 2|\alpha|,$ (9)

where $\langle M_{x}N_{y}\rangle:=\langle\psi|M_{x}N_{y}|\psi\rangle$ is the
expectation value of the observables. The weighted CHSH inequality is true if
Alice and Bob share some product state
$|\phi\rangle=|\phi_{A}\rangle\otimes|\phi_{B}\rangle$. However, if they share
an entangled state $|\psi\rangle$, the value of $\mathcal{I}_{\alpha}$ can be
as large as $\mathcal{I}_{\alpha}^{\max}=2\sqrt{1+\alpha^{2}}$ [AMP12].

######  Definition 2.11 (Ideal strategy to achieve
$\mathcal{I}_{\alpha}^{\max}$ [AMP12]).

Define $\mu:=\arctan(1/\alpha)$. The ideal strategy for weighted CHSH with
parameter $\alpha$, which achieves the value $\mathcal{I}_{\alpha}^{\max}$,
consists of the joint state $|EPR\rangle$ and observables
$\tilde{M}_{1}=\sigma_{z}$, $\tilde{M}_{2}=\sigma_{x}$,
$\tilde{N}_{1}=\cos(\mu)\sigma_{z}+\sin(\mu)\sigma_{x}$ and
$\tilde{N}_{2}=\cos(\mu)\sigma_{z}-\sin(\mu)\sigma_{x}$.

An interesting observation of the weighted CHSH inequality is that it admits
robust self-testing of the ideal strategy given above. We give the formal
statement of this robust self-testing property of $\mathcal{I}_{\alpha}$ in
Section 4.1. In Section 5 we design a nonlocal test called the extended
weighted CHSH test based on the ideal correlation that maximally violates the
weighted CHSH inequality.

###  2.4 Approximation tools

In the rest of the paper, we use the following approximation results
implicitly and explicitly.

######  Proposition 2.12.

Let $|v\rangle$ and $|v^{\prime}\rangle$ be vectors such that the relation
$|v\rangle\simeq_{\epsilon}|v^{\prime}\rangle$ holds. Then for any unit vector
$|u\rangle$,

$\displaystyle\langle v|u\rangle\simeq_{\epsilon}\langle v^{\prime}|u\rangle.$

###### Proof.

We can write $|v^{\prime}\rangle=|v\rangle+|v^{\prime\prime}\rangle$, where
$\lVert|v^{\prime\prime}\rangle\rVert\leq\epsilon$, then

$\displaystyle\lVert\langle v|u\rangle-\langle
v^{\prime}|u\rangle\rVert=\lVert\langle
v^{\prime\prime}|u\rangle\rVert\leq\lVert|u\rangle\rVert\lVert|v^{\prime\prime}\rangle\rVert\leq\epsilon.$

∎

######  Proposition 2.13.

Let $|u_{i}\rangle$ and $|v_{i}\rangle$ for $i=1,2$ be vectors with norm less
than equal to $1$ such that $|u_{1}\rangle\simeq_{\epsilon_{1}}|v_{1}\rangle$
and $|u_{2}\rangle\simeq_{\epsilon_{2}}|v_{2}\rangle$. Then,

$\displaystyle\langle
u_{1}|u_{2}\rangle\simeq_{\epsilon_{1}+\epsilon_{2}}\langle
v_{1}|v_{2}\rangle.$

###### Proof.

By direct calculation we have

$\displaystyle\lVert\langle u_{1}|u_{2}\rangle-\langle
v_{1}|v_{2}\rangle\rVert\leq$ $\displaystyle\lVert\langle
u_{1}|u_{2}\rangle-\langle v_{1}|u_{2}\rangle\rVert+\lVert\langle
v_{1}|u_{2}\rangle-\langle v_{1}|v_{2}\rangle\rVert$ $\displaystyle\leq$
$\displaystyle\epsilon_{1}+\epsilon_{2},$

where we used Proposition 2.12. ∎

######  Proposition 2.14.

Let $U$ be a unitary matrix and $|u\rangle$ and $|v\rangle$ be two vectors
such that

$\displaystyle U|u\rangle\simeq_{\epsilon_{1}}a|u\rangle$ $\displaystyle
U|v\rangle\simeq_{\epsilon_{2}}b|v\rangle,$

for some $a\neq b\in\mathbb{C}$ and $\lVert a\rVert=\lVert b\rVert=1$. Then,

$\displaystyle\lVert\langle
u|v\rangle\rVert\leq\max(\lVert|u\rangle\rVert,\lVert|v\rangle\rVert)\frac{\epsilon_{1}+\epsilon_{2}}{\lVert
1-a^{-1}b\rVert}+\frac{\epsilon_{1}\epsilon_{2}}{\lVert 1-a^{-1}b\rVert}.$

###### Proof.

We write $U|u\rangle=a|u\rangle+|u^{\prime}\rangle$ such that
$\lVert|u^{\prime}\rangle\rVert\leq\epsilon_{1}$. Similarly, we write
$U|v\rangle=b|v\rangle+|v^{\prime}\rangle$ such that
$\lVert|v^{\prime}\rangle\rVert\leq\epsilon_{2}$. Then,

$\displaystyle\langle u|v\rangle=$ $\displaystyle\langle Uu|Uv\rangle$
$\displaystyle=$ $\displaystyle(a^{-1}\langle u|+\langle
u^{\prime}|)(b|v\rangle+|v^{\prime}\rangle)$ $\displaystyle=$ $\displaystyle
a^{-1}b\langle u|v\rangle+a^{-1}\langle u|v^{\prime}\rangle+b\langle
u^{\prime}|v\rangle+\langle u^{\prime}|v^{\prime}\rangle,$

which implies that

$\displaystyle\lVert\langle v|u\rangle\rVert$ $\displaystyle=\frac{\lVert
a^{-1}\langle u|v^{\prime}\rangle+b\langle u^{\prime}|v\rangle+\langle
u^{\prime}|v^{\prime}\rangle\rVert}{\lVert 1-a^{-1}b\rVert}$
$\displaystyle\leq\frac{\lVert
a\rVert\lVert|v\rangle\rVert\lVert|u^{\prime}\rangle\rVert+\lVert
b\rVert\lVert|u\rangle\rVert\lVert|v^{\prime}\rangle\rVert+\lVert|u^{\prime}\rangle\rVert\lVert|v^{\prime}\rangle\rVert}{\lVert
1-a^{-1}b\rVert}$
$\displaystyle\leq\max(\lVert|u\rangle\rVert,\lVert|v\rangle\rVert)\frac{\epsilon_{1}+\epsilon_{2}}{\lVert
1-a^{-1}b\rVert}+\frac{\epsilon_{1}\epsilon_{2}}{\lVert 1-a^{-1}b\rVert}.$

∎

######  Proposition 2.15.

Let $|u\rangle$ and $|v\rangle$ be two vectors such that
$\lVert|u\rangle\rVert\simeq_{\epsilon_{1}}1$,
$\lVert|v\rangle\rVert\simeq_{\epsilon_{2}}1$, and $\langle
u|v\rangle\simeq_{\epsilon_{3}}1$. Then

$\displaystyle|u\rangle\simeq_{O(\sqrt{\epsilon_{1}+\epsilon_{2}+\epsilon_{3}})}|v\rangle.$

###### Proof.

Direct calculation gives us that

$\displaystyle\lVert|u\rangle-|v\rangle\rVert^{2}$
$\displaystyle=\lVert|u\rangle\rVert^{2}+\lVert|v\rangle\rVert^{2}-2\langle
u|v\rangle$
$\displaystyle\leq(1+\epsilon_{1})^{2}+(1+\epsilon_{2})^{2}-2(1-\epsilon_{3})$
$\displaystyle=2(\epsilon_{1}+\epsilon_{2}+\epsilon_{3})+\epsilon_{1}^{2}+\epsilon_{2}^{2}$
$\displaystyle=O(\epsilon_{1}+\epsilon_{2}+\epsilon_{3}).$

∎

######  Proposition 2.16.

Let $|u\rangle$ be a vector with norm less than or equal to $1$ such that for
a unitary $U$,

$\displaystyle U|u\rangle\simeq_{\epsilon}a|u\rangle,$

for $a\in\mathbb{C}$ and $\lVert a\rVert=1$. Then,

$\displaystyle U^{n}|u\rangle\simeq_{n\epsilon}a^{n}|u\rangle$

for all $n\geq 1$.

###### Proof.

We can prove it by induction. The $k=1$ case follows the given condition.
Assume it holds for $k=n-1$ and consider $k=n$, then we have

$\displaystyle\lVert U^{n}|u\rangle-a^{n}|u\rangle\rVert$ $\displaystyle\leq$
$\displaystyle\lVert U\rVert\lVert
U^{n-1}|\psi\rangle-a^{n-1}|\psi\rangle\rVert+\lVert a^{n-1}\rVert\lVert
U|\psi\rangle-a|\psi\rangle\rVert$ $\displaystyle\leq$
$\displaystyle(n-1)\epsilon+\epsilon=n\epsilon,$

where we used the fact that $\lVert U\rVert=1$. ∎

######  Lemma 2.17 (Substitution Lemma).

Let $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ be two Hilbert spaces, and
$|\psi\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Suppose there exist
unitaries $\\{V\\}\cup\\{V_{i}\\}_{i=1}^{k}\cup\\{M_{i}\\}_{i=1}^{n}$ on
$\mathcal{H}_{A})$ and $\\{N_{i}\\}_{i=1}^{n}$ on $\mathcal{H}_{B}$ such that

$\displaystyle M_{i}|\psi\rangle\simeq_{\epsilon_{1}}N_{i}|\psi\rangle$

for $1\leq i\leq n$, and

$\displaystyle
V|\psi\rangle\simeq_{\epsilon_{2}}\Pi_{i=1}^{k}V_{i}|\psi\rangle.$

Then,

$\displaystyle
V\Pi_{i=1}^{n}M_{i}|\psi\rangle\simeq_{2n\epsilon_{1}+\epsilon_{2}}\left(\Pi_{i=1}^{k}V_{i}\right)\left(\Pi_{i=1}^{n}M_{i}\right)|\psi\rangle.$

###### Proof.

We prove this lemma by induction on $n$. The $n=0$ case follows the condition
that $V|\psi\rangle\simeq_{\epsilon_{2}}\Pi_{i=1}^{k}V_{i}|\psi\rangle$.

Assume the conclusion holds for $n=m$. Consider the case $n=m+1$, then

$\displaystyle V\Pi_{i=1}^{m+1}M_{i}|\psi\rangle$
$\displaystyle=V\left(\Pi_{i=1}^{m}M_{i}\right)M_{m+1}|\psi\rangle$
$\displaystyle\simeq_{\epsilon_{1}}V\left(\Pi_{i=1}^{m}M_{i}\right)N_{m+1}|\psi\rangle$
$\displaystyle=N_{m+1}V\left(\Pi_{i=1}^{m}M_{i}\right)|\psi\rangle$
$\displaystyle\simeq_{2m\epsilon_{1}+\epsilon_{2}}N_{m+1}\left(\Pi_{i=1}^{k}V_{i}\right)\left(\Pi_{i=1}^{m}M_{i}\right)|\psi\rangle$
$\displaystyle=\left(\Pi_{i=1}^{k}V_{i}\right)\left(\Pi_{i=1}^{m}M_{i}\right)N_{m+1}|\psi\rangle$
$\displaystyle\simeq_{\epsilon_{1}}\left(\Pi_{i=1}^{k}V_{i}\right)\left(\Pi_{i=1}^{m+1}M_{i}\right)|\psi\rangle.$

Adding the error terms in the derivation above together gives us that

$\displaystyle
V\Pi_{i=1}^{m+1}M_{i}|\psi\rangle\simeq_{(2m+2)\epsilon_{1}+\epsilon_{2}}\left(\Pi_{i=1}^{k}V_{i}\right)\left(\Pi_{i=1}^{m+1}M_{i}\right)|\psi\rangle.$

By the principle of inductive proof, the proof is complete. ∎

##  3 The binary linear system game $LS(r)$

In this section, we introduce a binary linear system game that is a component
of the full test. This game is designed to enforce relations that should be
satisfied by Alice and Bob’s observables.

The inspiration comes from Slofstra’s seminal work [Slo19], in which he embeds
a group with generators $x$ and $y$ satisfying the relation $xyx^{-1}=y^{2}$
into the solution group of a binary linear system game. We generalize the
relation $xyx^{-1}=y^{2}$ and embed the following group

$\displaystyle\mathcal{P}=\langle u,o:uou^{-1}=o^{r}\rangle,$ (10)

for some $r\in\mathbb{N}$, into the solution group, $\Gamma$, of a binary
linear system game, $LS(r)$. The steps to embed $\mathcal{P}$ into $\Gamma$
follows the procedure detailed in the proofs of Proposition $33$, Lemma $29$
and Proposition $27$ of [Slo19], so the group $\mathcal{P}$ (eq. 10) is first
embedded into $\mathcal{P}_{0}$ (Definition 3.1), then $\mathcal{P}_{1}$
(Definition 3.3), and finally into the group $\Gamma$ (Definition 3.5), and we
obtain a chain of embeddings:

$\displaystyle\mathcal{P}\hookrightarrow\mathcal{P}_{0}\hookrightarrow\mathcal{P}_{1}\hookrightarrow\Gamma.$
(11)

This section is structured as follows. In Section 3.1, we define the group
$\mathcal{P}_{0}$ and prove that $\mathcal{P}$ is embedded in
$\mathcal{P}_{0}$. In Section 3.2, we define the group $\mathcal{P}_{1}$ and
prove that $\mathcal{P}_{0}$ is embedded in $\mathcal{P}_{1}$. Section 3.3
contains the definition of the group $\Gamma$ and the proof that
$\mathcal{P}_{1}$ is embedded in $\Gamma$. The purposes of introducing each
intermediate group are explained along the definitions. In Section 3.4, we
construct $LS(r)$ from $\Gamma$ and give the formal definition of $LS(r)$.

Note that, we defer the full definitions of the representations of
$\mathcal{P}_{0}$, $\mathcal{P}_{1}$ and $\Gamma$ until Appendix B. Instead,
We only highlight a few operators from a finite-dimensional representation of
$\Gamma$. The representation of $\Gamma$ will be used later to build the ideal
strategy of the full test.

###  3.1 The group $\mathcal{P}_{0}$

The group $\mathcal{P}_{0}$ is a conjugacy group (Definition 2.3), and is
defined below. The purpose of this step is to embed $\mathcal{P}$ into a group
where all the generators are of order-$2$, because it is impossible to find a
homomorphism from $\mathcal{P}$ to a solution group that maps $u$ or $o$,
which can have arbitrary order, to a single binary generator. On the other
hand, a homomorphism from $\mathcal{P}_{0}$ to a solution group can be easier
to find because all the generators of $\mathcal{P}_{0}$ are binary.

######  Definition 3.1.

Let the set $S_{0}$ be

$\displaystyle S_{0}=\\{o_{i}\\}_{i=1}^{r}\cup\\{u_{i}\\}_{i=1}^{5},$

and the set $R_{0}$ be the union of

$\displaystyle R_{base}=\\{s^{2}=e|s\in S\\},$ $\displaystyle
R_{u}=\\{u_{3}=u_{2}o_{1}u_{2},\quad u_{4}=u_{2}o_{2}u_{2},\quad
u_{5}=u_{1}u_{3}u_{1},\quad o_{2}=u_{1}u_{4}u_{1},\quad
u_{5}=o_{1}o_{r}o_{1}\\},$

and

$\displaystyle
R_{o}=\begin{cases}\bigcup_{j=1}^{r/2-1}\\{o_{1+2j}=o_{1}o_{2j}o_{1},\quad
o_{2+2j}=o_{2}o_{1+2j}o_{2}\\}&\text{ if $r$ is even },\\\
\\{o_{3}=o_{2}o_{1}o_{2}\\}\cup\bigcup_{j=1}^{(r-3)/2}\\{o_{2+2j}=o_{1}o_{1+2j}o_{1},\quad
o_{3+2j}=o_{2}o_{2j+2}o_{2}\\}&\text{ if $r$ is odd }.\end{cases}$

The group $\mathcal{P}_{0}$ is a group with presentation $\langle
R_{0}:S_{0}\rangle$.

The special generators of $\mathcal{P}_{0}$ are $o_{1},o_{2},u_{1}$ and
$u_{2}$ because the product $o_{1}o_{2}$ behaves similarly as $o$, and the
product $u_{1}u_{2}$ behaves similarly as $u$. Moreover, the conjugacy
relations in $R_{0}$ can be combined to recover the relation $uou^{-1}=o^{r}$,
as proved in the next proposition.

######  Proposition 3.2.

The group $\mathcal{P}$ is embedded in $\mathcal{P}_{0}$. Furthermore, the
generators of $\mathcal{P}_{0}$ satisfy the relations

$\displaystyle(u_{1}u_{2})o_{2}(u_{2}u_{1})=o_{2}$ (12)
$\displaystyle(u_{1}u_{2})^{j}o_{1}o_{2}(u_{2}u_{1})^{j}=(o_{1}o_{2})^{r^{j}},$
(13)

for any $j\in\mathbb{N}$.

###### Proof.

We prove eq. 12 first. It is easy to see that

$\displaystyle u_{1}(u_{2}o_{2}u_{2})u_{1}=u_{1}u_{4}u_{1}=o_{2}.$ (14)

Next, The proof that $\mathcal{P}$ is embedded in $\mathcal{P}_{0}$ is based
on the $j=1$ case of eq. 13. Once it is proved, we can use the recipe given in
the proof of Proposition $33$ of [Slo19] to construct a finite-dimensional
representation of $\mathcal{P}_{0}$ from a finite-dimensional representation
of $\mathcal{P}$. Then Lemma $15$ of [Slo19] proves that a homomorphism
$\phi:\mathcal{P}\rightarrow\mathcal{P}_{0}$ such that $\phi(u)=u_{1}u_{2}$
and $\phi(o)=o_{1}o_{2}$ is injective.

We prove eq. 13 by induction. The base case follows the direct calculation
given below

$\displaystyle u_{1}u_{2}o_{1}o_{2}u_{2}u_{1}=$ $\displaystyle
u_{1}(u_{2}o_{1}u_{2})(u_{2}o_{2}u_{2})u_{1}$ $\displaystyle=$
$\displaystyle(u_{1}u_{3}u_{1})(u_{1}u_{4}u_{1})$ $\displaystyle=$
$\displaystyle u_{5}o_{2}$ $\displaystyle=$ $\displaystyle
o_{1}o_{r}o_{1}o_{2}.$

Then we substitute the definitions of $o_{k}$ for $k=r\dots 3$ into the
equation above, which proves the $j=1$ case.

Assume the statement is true for $j=n$, then for $j=n+1$

$\displaystyle(u_{1}u_{2})^{n+1}o_{1}o_{2}(u_{2}u_{1})^{n+1}=$ $\displaystyle
u_{1}u_{2}(o_{1}o_{2})^{r^{n}}u_{2}u_{1}$ $\displaystyle=$
$\displaystyle(u_{1}u_{2}o_{1}o_{2}u_{2}u_{1})^{r^{n}}$ $\displaystyle=$
$\displaystyle(o_{1}o_{2})^{r^{n+1}},$

where from the first line to the second line, we insert
$(u_{2}u_{1})(u_{1}u_{2})$ between every pair of $o_{1}o_{2}$, and from the
second line to the third line, we apply the $j=1$ case $r^{n}$ times. Hence,
the statement is true. ∎

Note that our representation $\Psi_{0}$ of $\mathcal{P}_{0}$ is different from
the representation constructed in the proof of Proposition $33$ of [Slo19]. We
give the formal definition of $\Psi_{0}$ (Definition B.1) in Appendix B.

To better characterize all the conjugacy relations of $\mathcal{P}_{0}$ and
simplify the presentation of $\mathcal{P}_{0}$, we relabel $u_{i}$ and
$o_{i}$’s as $a_{i}$’s in such a way that

$\displaystyle a_{j}:=\begin{cases}o_{j}&\text{ for }j=1,2\\\ u_{j-2}&\text{
for }j=3\dots 7\\\ o_{j-5}&\text{ for }j=8\dots r+5.\end{cases}$ (15)

Then we define the set $C(r)$ of tuples $(i,j,k)$ such that

$\displaystyle C(r)=\\{(i,j,k)|(a_{i}a_{j}a_{i}=a_{k})\in R_{0}\\}.$ (16)

The size of $C(r)$ is $r+3$. Hence, another presentation of the group
$\mathcal{P}_{0}$ is

$\displaystyle\mathcal{P}_{0}=\langle\\{a_{i}\\}_{i=1}^{r+5}:\\{a_{i}^{2}=e\\}_{i=1}^{r+5}\cup\\{a_{i}a_{j}a_{i}=a_{k}|(i,j,k)\in
C(r)\\}\rangle,$

and we will construct $\mathcal{P}_{1}$ based on this presentation of
$\mathcal{P}_{0}$.

###  3.2 The group $\mathcal{P}_{1}$

The group $\mathcal{P}_{1}$ is a nice conjugacy group (Definition 2.4). We
embed $\mathcal{P}_{0}$ into $\mathcal{P}_{1}$ to make the construction of a
finite-dimension representation of $\Gamma$ from a finite-dimension
representation of $\mathcal{P}_{1}$ easier.

######  Definition 3.3.

Define the set $S_{1}$ to be

$\displaystyle
S_{1}=\\{a_{i},b_{i},c_{i},d_{i}\\}_{i=1}^{r+5}\cup\\{f_{0}\\}\cup\\{h_{jk}\\}_{(i,j,k)\in
C(r)},$

and the set $R_{1}$ to be

$\displaystyle R_{1}=$ $\displaystyle\\{s^{2}=e|s\in S_{1}\\}$
$\displaystyle\cup\\{a_{i}=b_{i}c_{i}=f_{0}d_{i},\quad
f_{0}b_{i}f_{0}=c_{i}\\}_{i=1}^{r+5}$
$\displaystyle\cup\\{h_{jk}b_{j}c_{k}=e,\quad
d_{i}b_{j}d_{i}=c_{k}\\}_{(i,j,k)\in C(r)}.$

The group $\mathcal{P}_{1}$ is a group with the presentation $\langle
S_{1}:R_{1}\rangle$.

Note that the group $\mathcal{P}_{1}$ is the same as the group $K$ used in the
proof of Lemma $29$ of [Slo19]. For each $1\leq i\leq r+5$, the relation
$a_{i}=b_{i}c_{i}$ guarantees that $b_{i}$ commutes with $c_{i}$. For each
$(i,j,k)\in C(r)$, the linear relation $h_{jk}b_{j}c_{k}=e$ guarantees that
$b_{j}$ commutes with $c_{k}$.

The relation between $\mathcal{P}_{0}$ and $\mathcal{P}_{1}$ is summarized in
the propositions below.

######  Proposition 3.4.

The group $\mathcal{P}_{0}$ is embedded in $\mathcal{P}_{1}$.

###### Proof.

We prove this proposition by showing that generators $a_{i}$’s in $S_{1}$
satisfy the relation $a_{i}a_{j}a_{i}=a_{k}$ for all $(i,j,k)\in C(r)$. This
means the homomorphism $\phi:\mathcal{P}_{0}\rightarrow\mathcal{P}_{1}$ that
maps $a_{i}$ to $a_{i}$ is homomorphism from $\mathcal{P}_{0}$ to
$\mathcal{P}_{1}$.

We first show that $d_{i}c_{j}d_{i}=b_{k}$, which is because

$\displaystyle
d_{i}c_{j}d_{i}=d_{i}(f_{0}b_{j}f_{0})d_{i}=f_{0}(d_{i}b_{j}d_{i})f_{0}=f_{0}c_{k}f_{0}=b_{k}.$

Then, we can prove that

$\displaystyle
a_{i}a_{j}a_{i}=f_{0}d_{i}b_{j}c_{j}f_{0}d_{i}=(f_{0}d_{i}b_{j}d_{i}f_{0})(f_{0}d_{i}c_{j}d_{i}f_{0})=(f_{0}c_{k}f_{0})(f_{0}b_{k}f_{0})=b_{k}c_{k}=a_{k},$

where we use the fact that $f_{0}$ commutes with $d_{i}$.

A representation of $\mathcal{P}_{1}$ can also be built upon a representation
of $\mathcal{P}_{0}$. Suppose $\Psi_{0}$ is a representation of
$\mathcal{P}_{0}$ on some Hilbert space $\mathcal{H}$, then a representation
of $\mathcal{P}_{1}$, $\Psi_{1}$, on the Hilbert space
$\mathbb{C}^{2}\otimes\mathcal{H}$ can be constructed such that

$\displaystyle\Psi_{1}(a_{i})=\mathbb{1}_{\mathbb{C}^{2}}\otimes\Psi_{0}(a_{i})$

as proved in Lemma $29$ of [Slo19]. Then, the injectivity of $\phi$ follows
Lemma $15$ of [Slo19]. ∎

The consequence of this proposition is that $\mathcal{P}$ is embedded in
$\mathcal{P}_{1}$. We give the formal definition of the representation
$\Psi_{1}$ of $\mathcal{P}_{1}$ (Definition B.2) in Appendix B.

###  3.3 The group $\Gamma$

The group $\Gamma$ is a solution group, so all the generators of $\Gamma$ are
of order-$2$ and all the relations are linear relations. Moreover, the linear
relations can be combined to recover the conjugacy relations in $R_{1}$.

######  Definition 3.5.

Define the set $S$ to be

$\displaystyle
S=\\{a_{i},b_{i},c_{i},d_{i},\\{p_{i,j}\\}_{j=1}^{5}\\}_{i=1}^{r+5}\cup\\{f_{i},g_{i},m_{i}\\}_{i=0}^{2}\cup\\{h_{jk}\\}_{(i,j,k)\in
C(r)}\cup\\{\\{q_{\boldsymbol{c},j}\\}_{j=1}^{6}\\}_{\boldsymbol{c}\in C(r)},$

and the set $R$ to be the union of the following sets of linear relations:

  * •

for each $i=1\dots r+5$:

$\displaystyle R_{i}=\\{$ $\displaystyle a_{i}=b_{i}c_{i}=f_{0}d_{i},\quad
f_{0}f_{1}f_{2}=e,\quad b_{i}f_{2}p_{i,1}=e,\quad p_{i,1}p_{i,2}p_{i,3}=e,$
$\displaystyle f_{0}p_{i,3}p_{i,4}=e,\quad c_{i}p_{i,4}p_{i,5}=e,\quad
f_{1}p_{i,2}p_{i,5}=e\\},$

  * •

for each $\boldsymbol{c}=(i,j,k)\in C(r)$:

$\displaystyle R_{\boldsymbol{c}}=\\{$ $\displaystyle h_{jk}b_{j}c_{k}=e,\quad
d_{i}q_{\boldsymbol{c},1}f_{2}=e,\quad b_{j}f_{2}q_{\boldsymbol{c},2}=e,\quad
q_{\boldsymbol{c},2}q_{\boldsymbol{c},3}q_{\boldsymbol{c},4}=e,$
$\displaystyle d_{i}q_{\boldsymbol{c},4}q_{\boldsymbol{c},5}=e,\quad
c_{k}q_{\boldsymbol{c},5}q_{\boldsymbol{c},6}=e,\quad
q_{\boldsymbol{c},1}q_{\boldsymbol{c},3}q_{\boldsymbol{c},6}=e\\},$

  * •

$R_{MS}=\\{f_{0}f_{1}f_{2}=e,\quad g_{0}g_{1}g_{2}=e,\quad
m_{0}m_{1}m_{2}=e,\quad f_{0}g_{2}m_{0}=e,\\\ \indent f_{2}g_{0}m_{1}=e,\quad
f_{1}g_{1}m_{2}=J\\},$

  * •

$R_{J}=\\{JsJs=e|s\in S\\}\cup\\{J^{2}=e\\}$,

  * •

$R_{base}=\\{s^{2}=e|s\in S\\}$.

The group $\Gamma$ is a group with the presentation $\langle
S\cup\\{J\\}:R\rangle$.

In the next proposition, we prove that the group $\mathcal{P}_{1}$ is embedded
in $\Gamma$.

######  Proposition 3.6.

The group $\mathcal{P}_{1}$ is embedded in $\Gamma$. The generators of
$\Gamma$ also satisfy the relations:

$\displaystyle f_{0}g_{0}f_{0}g_{0}=J,$ (17) $\displaystyle
f_{2}g_{2}f_{2}g_{2}=J.$ (18)

###### Proof.

To prove the first claim, we show that the generators $b_{i}$, $c_{i}$,
$d_{i}$ satisfy the relations $d_{i}b_{j}d_{i}=c_{k}$ for each
$\boldsymbol{c}=(i,j,k)\in C(r)$.

$\displaystyle d_{i}b_{j}d_{i}=$
$\displaystyle(k_{\boldsymbol{c}1}f_{2})(f_{2}k_{\boldsymbol{c}2})(k_{\boldsymbol{c}4}k_{\boldsymbol{c}5})$
$\displaystyle=$ $\displaystyle
k_{\boldsymbol{c}1}(k_{\boldsymbol{c}2}k_{\boldsymbol{c}4})k_{\boldsymbol{c}5}$
$\displaystyle=$
$\displaystyle(k_{\boldsymbol{c}1}k_{\boldsymbol{c}3})k_{\boldsymbol{c}5}$
$\displaystyle=$ $\displaystyle k_{\boldsymbol{c}6}k_{\boldsymbol{c}5}$
$\displaystyle=$ $\displaystyle c_{k}.$

The derivation of $f_{0}b_{i}f_{0}=c_{i}$ is similar for $1\leq i\leq r+5$, so
we omit it here. Hence, a map $\phi:\mathcal{P}_{1}\rightarrow\Gamma$ that
maps $s$ to $s$ for each $s\in S_{1}$ is a homomorphism between
$\mathcal{P}_{1}$ and $\Gamma$. A representation of $\Gamma$ can be
constructed from a representation of $\mathcal{P}_{1}$ as shown in the proof
of Proposition $27$ of [Slo19], so the injectivity of homomorphism $\phi$
follows Lemma $15$ of [Slo19].

Equation 17 can be proved by

$\displaystyle f_{0}g_{0}f_{0}g_{0}$ $\displaystyle=$
$\displaystyle(f_{1}f_{2})(f_{2}m_{1})(f_{1}f_{2})(f_{2}m_{1})$
$\displaystyle=$ $\displaystyle f_{1}m_{1}f_{1}m_{1}$ $\displaystyle=$
$\displaystyle f_{1}(g_{0}f_{2})f_{1}(m_{0}m_{2})$ $\displaystyle=$
$\displaystyle f_{1}g_{0}(f_{2}f_{1})(f_{0}g_{2})m_{2}$ $\displaystyle=$
$\displaystyle f_{1}g_{0}g_{2}m_{2}$ $\displaystyle=$ $\displaystyle
f_{1}g_{1}m_{2}$ $\displaystyle=$ $\displaystyle J.$

Equation 18 can be proved analogously. ∎

Since $\mathcal{P}$ is embedded in $\mathcal{P}_{1}$, we can conclude that
$\mathcal{P}$ is embedded in $\Gamma$ as well.

The formal definition of a representation of $\Gamma$ is given in Definition
B.3. We highlight a few important operators here. The representation $\Psi$ of
$\Gamma$ is defined on the Hilbert space $W_{2}\otimes W_{2}\otimes W_{d-1}$,
where $W_{k}$ denotes a Hilbert space of dimension $k$,

$\displaystyle W_{k}=\operatorname{span}\\{|x_{j}\rangle\\}_{j=1}^{k}.$ (19)

We denote the standard basis of $W_{k}$ by $\\{|x_{j}\rangle\\}_{j=1}^{k}$. We
denote the identity operator for the subspace $W_{k}$ by $\mathbb{1}_{W_{k}}$.

We define an operator $\tilde{O}$ on $W_{d-1}$ as

$\displaystyle\tilde{O}=\sum_{j=1}^{d-1}\omega_{d}^{j}|x_{j}\rangle\langle
x_{j}|.$

Note that another form of the basis of $W_{d-1}$ is
$\\{|x_{r^{j}}\rangle\\}_{j=0}^{d-2}$, where the subscript $r^{j}$ is taken
modulo $d$ implicitly, because another form of $\tilde{O}$ is

$\displaystyle\tilde{O}=\sum_{j=0}^{d-2}\omega_{d}^{r^{j}}|x_{r^{j}}\rangle\langle
x_{r^{j}}|.$ (20)

We use the second form of the basis when it is convenient. The other basis of
$W_{d-1}$ that we use is $\\{|u_{j}\rangle\\}_{j=0}^{d-2}$ defined by

$\displaystyle|u_{k}\rangle=\frac{1}{\sqrt{d-1}}\sum_{j=0}^{d-2}\omega_{d-1}^{jk}|x_{r^{j}}\rangle.$

The basis $\\{|u_{j}\rangle\\}$ is the eigen-basis of operator $\tilde{U}$
defined by

$\displaystyle\tilde{U}=\sum_{j=0}^{d-2}\omega_{d-1}^{j}|u_{j}\rangle\langle
u_{j}|.$

Note that in the standard basis,

$\displaystyle\tilde{U}=\sum_{j=0}^{d-2}|x_{r^{j-1}}\rangle\langle
x_{r^{j}}|.$ (21)

The unitaries $\tilde{U}$ and $\tilde{O}$ are special because they satisfy the
relation $\tilde{U}\tilde{O}\tilde{U}^{\dagger}=\tilde{O}^{r}$.

Here we only present what $a_{1},a_{2},a_{3}$ and $a_{4}$ are mapped to by the
representation $\Psi$, since they are the key generators of $\Gamma$.

$\displaystyle\Psi(a_{1})$
$\displaystyle=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\left(\sum_{j=1}^{(d-1)/2}\omega_{d}^{j}|x_{j}\rangle\langle
x_{d-j}|+\omega_{d}^{-j}|x_{d-j}\rangle\langle x_{j}|\right)$ (22)
$\displaystyle\Psi(a_{2})$
$\displaystyle=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\left(\sum_{j=1}^{d-1}|x_{j}\rangle\langle
x_{d-j}|\right).$ (23) $\displaystyle\Psi(a_{3})$
$\displaystyle=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\Big{[}|u_{0}\rangle\langle
u_{0}|+\omega_{d-1}^{(d-1)/2}|u_{(d-1)/2}\rangle\langle u_{(d-1)/2}|$ (24)
$\displaystyle+\sum_{k=1}^{(d-3)/2}\left(\omega_{d-1}^{k}|u_{k}\rangle\langle
u_{d-1-k}|+\omega_{d-1}^{-k}|u_{d-1-k}\rangle\langle u_{k}|\right)\Big{]}$
$\displaystyle\Psi(a_{4})$
$\displaystyle=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\Big{[}|u_{0}\rangle\langle
u_{0}|+|u_{(d-1)/2}\rangle\langle u_{(d-1)/2}|$ (25)
$\displaystyle+\sum_{k=1}^{(d-3)/2}\left(|u_{d-1-k}\rangle\langle
u_{k}|+|u_{k}\rangle\langle u_{d-1-k}|\right)\Big{]}.$

The tensor structure of the representations come from the construction of
$\Psi$. These operators are important because
$\Psi(a_{1}a_{2})=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\tilde{O}$
and
$\Psi(a_{3}a_{4})=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\tilde{U}$
where $\tilde{O}$ is defined in eq. 20 and $\tilde{U}$ is defined in eq. 21.
The unitaries $\Psi(a_{1}a_{2})$ and $\Psi(a_{3}a_{4})$ satisfy the following
equation

$\displaystyle\Psi(a_{3}a_{4})\Psi(a_{1}a_{2})\Psi(a_{4}a_{3})=\Psi(a_{1}a_{2})^{r},$

as $\tilde{U}\tilde{O}\tilde{U}^{\dagger}=\tilde{O}^{r}$.

###  3.4 The game $LS(r)$

From the group $\Gamma$ we can construct the binary linear system game
$LS(r)$. Basically, we associate a variable $x(s)$ to each generator $s\in S$.
Then each linear relation in $R$ can be translated to a linear equation. For
example, the linear relation $f_{0}f_{1}f_{2}=e$ is translated to the equation
$x(f_{0})+x(f_{1})+x(f_{2})=0$, and the relation $f_{1}g_{1}m_{2}=J$ is
translated to the equation $x(f_{1})+x(g_{1})+x(m_{2})=1$. The complete list
of the equations is given in Definition A.1. The construction of $LS(r)$
proves the following theorem. The definition of $LS(r)$ follows this theorem.

######  Theorem 3.7.

The group $\mathcal{P}$ can be embedded in the solution group of a binary
linear system game which has $n(r):=16r+75$ variables and $m(r):=14r+62$
equations, where each equation has $3$ variables.

######  Definition 3.8.

The linear system game $LS(r)$ consists of

$\displaystyle\mathcal{X}^{LS}=\\{I_{i}\\}_{i=1}^{m(r)},$
$\displaystyle\mathcal{Y}^{LS}=\\{x(s):s\in S\\},$

where $I_{i}=\\{s:H(i,s)=1\\}$ is the set of all the nonzero coefficient of
equation $i$ and $m(r):=14r+62$ is the number of equations. Details of $I_{i}$
for $1\leq i\leq m(r)$ can be found in Definition A.1. Alice’s answer sets are

$\displaystyle\mathcal{A}^{LS}_{I_{i}}=(\mathbb{Z}_{2})^{I_{i}}$

for $1\leq i\leq m(r)$. Bob’s answer set is

$\displaystyle\mathcal{B}^{LS}=\mathbb{Z}_{2}.$

The probability distribution is uniform over all the pairs $(I_{i},x(s))$ such
that $s\in I_{i}$, so

$\displaystyle\pi^{LS}(I_{i},x(s))=\begin{cases}1/N(r)&\text{ if }s\in
I_{i}\\\ 0&\text{otherwise,}\end{cases}$

where $N(r):=157r+685$ is the total number of valid question pairs. We define

$\displaystyle X_{i}:=\\{\boldsymbol{a}\in(\mathbb{Z}_{2})^{I_{i}}:\sum_{s\in
I_{i}}a(s)=c(i)\\},$

which is the set of all the valid answers of equation $i$. Given an answer
$(\boldsymbol{a},b)$ for question $(I_{i},x(s))$, the score function is

$\displaystyle V^{LS}_{I_{i},x(s)}(\boldsymbol{a},b)=\begin{cases}1\text{, if
}\boldsymbol{a}\in X_{i}\text{ and }a(s)=b\\\ 0\text{, otherwise}.\end{cases}$

As indicated above, the total number of question pairs is
$N(r)=157r+685=\Theta(r)$.

The ideal strategy of $LS(r)$ is based on the representation $\Psi$ of
$\Gamma$ defined in Definition B.3. We discuss the ideal strategy of $LS(r)$
in Section 5.1 when we introduce the ideal strategy of the full test.

##  4 Extending the weighted CHSH inequality $\mathcal{I}_{\alpha}$ into a
nonlocal test

In this section, we introduce the extended weighted CHSH test, which is going
to be a component of the full test introduced in Section 5. The ideal
correlation for this test contains the ideal correlation that achieves
$\mathcal{I}_{-\cot(\pi/d)}^{\max}$. To ease the study of the implication of a
strategy that realize the ideal correlation of the extended weighted CHSH
test, we fill in the background of the robust self-testing property of the
general weighted CHSH inequality, $\mathcal{I}_{\alpha}$, first.

###  4.1 Robust self-testing of $|EPR\rangle$ via $\mathcal{I}_{\alpha}$

In this section, we discuss how the weighted CHSH inequality can be used to
robustly self-test $|EPR\rangle$ and Pauli operators defined in Definition
2.11.

The formal statement is given in the theorem below. Since the proof uses the
same techniques as in [BP15], we defer the proof till Appendix C, and we only
list the key relations that will be reused in Section 6 here.

######  Theorem 4.1.

Define $\mu:=\arctan(1/\alpha)$. If a quantum strategy
$(|\psi\rangle,\\{M_{x}:=M_{x}^{0}-M_{x}^{1}\\}_{x=1,2},\\{N_{y}:=N_{y}^{0}-N_{y}^{1}\\}_{y=1,2})$
achieves that $\mathcal{I}_{\alpha}\geq\mathcal{I}_{\alpha}^{\max}-\epsilon$
for some $\epsilon>0$, then there exists a local isometry
$\Phi=\Phi_{A}\otimes\Phi_{B}$ and an auxiliary state $|junk\rangle$ such that

$\displaystyle\|\Phi(M_{x}\otimes
N_{y}|\psi\rangle)-|junk\rangle\otimes(\tilde{M}_{x}\otimes\tilde{N}_{y})|EPR\rangle\|=O(\frac{1}{\cos^{2}(\mu)\sin^{1/2}(\mu)}+\frac{1}{\sin(\mu)^{3/2}}))\sqrt{\epsilon}$

for $x,y\in\\{0,1,2\\}$ where the subscript $0$ refers to the identity
operator and $\tilde{M}_{x},\tilde{N}_{y}$ are defined in Definition 2.11.

We follow the convention used in [BP15], which defines

$\displaystyle Z_{A}:=M_{1}$ $\displaystyle X_{A}:=M_{2}$ $\displaystyle
Z_{B}:=\frac{N_{1}+N_{2}}{2\cos{\mu}}$ $\displaystyle
X_{B}:=\frac{N_{1}-N_{2}}{2\sin{\mu}}.$

The key relations that will be reused are

$\displaystyle
Z_{A}|\psi\rangle\simeq_{\frac{\sqrt{s\epsilon}}{c}}Z_{B}|\psi\rangle,$ (26)
$\displaystyle
X_{A}|\psi\rangle\simeq_{\frac{\sqrt{\epsilon}}{\sqrt{s}}}X_{B}|\psi\rangle,$
(27) $\displaystyle
X_{A}(\mathbb{1}+Z_{B})|\psi\rangle\simeq_{\frac{c+1}{c\sqrt{s}}\sqrt{\epsilon}}X_{B}(\mathbb{1}-Z_{A})|\psi\rangle,$
(28) $\displaystyle
Z_{A}(\mathbb{1}+X_{B})|\psi\rangle\simeq_{\frac{s+1}{c\sqrt{s}}\sqrt{\epsilon}}Z_{B}(\mathbb{1}-X_{A})|\psi\rangle,$
(29) $\displaystyle
Z_{A}X_{A}|\psi\rangle\simeq_{\frac{1+c+s}{c\sqrt{s}}\sqrt{\epsilon}}-X_{A}Z_{A}|\psi\rangle,$
(30) $\displaystyle
X_{A}Z_{A}|\psi\rangle\simeq_{\frac{2s^{2}+cs+c+s}{cs\sqrt{s}}\sqrt{\epsilon}}-X_{B}Z_{B}|\psi\rangle.$
(31)

We keep the exact error terms for the substitution steps in Section 6.

###  4.2 The extended weighted CHSH test

In this subsection, we first give the definition of the extended weighted CHSH
test, then we discuss the ideal strategy of it. We defer the ideal correlation
of this test til Section 5.3 as it will be presented as a part of the ideal
correlation of the full test.

######  Definition 4.2.

In the extended weighted CHSH test, the input alphabets and output alphabets
for Alice and Bob are

$\displaystyle\mathcal{X}^{EXT}=\mathcal{Y}^{EXT}=\\{0,1,2,n(r)+1,n(r)+2\\},$
$\displaystyle\mathcal{A}_{z}^{EXT}=\mathcal{B}_{z}^{EXT}=\begin{cases}\\{0,2\\}&\text{
if }z=0,\\\ \\{0,1\\}&\text{ if }z\in\\{1,2\\}\\\ \\{0,1,2\\}&\text{ if
}z\in\\{n(r)+1,n(r)+2\\}.\end{cases}$

The probability distribution over all the question pairs
$(x,y)\in\mathcal{X}^{EXT}\times\mathcal{Y}^{EXT}$ is uniform.

The reason why this test is called the extended weighted CHSH test will be
clear after we introduce the ideal strategy. The superscript $EXT$ stresses
the fact the labeled object is for the extended weighted CHSH test.

Recall the Hilbert space $W_{d-1}$ defined in eq. 19. To better characterize
the shared state and the observables of the ideal strategy, we need to
decompose $W_{d-1}$ into $2$-dimensional orthogonal subspaces. In order to do
it, we introduce the third basis of $W_{d-1}$: $\\{|j\rangle\\}_{j=1}^{d-1}$
defined by

$\displaystyle|j\rangle=-\frac{1}{\sqrt{2}}(|x_{j}\rangle+e^{-ij\pi/d}|x_{d-j}\rangle)$
(32)
$\displaystyle|d-j\rangle=\frac{i}{\sqrt{2}}(|x_{j}\rangle-e^{-ij\pi/d}|x_{d-j}\rangle)$
(33)

for $1\leq j\leq\frac{d-1}{2}$. Then the $2$-dimensional subspaces are

$\displaystyle V_{j}=\operatorname{span}(|j\rangle,|d-j\rangle)$ (34)

for $1\leq j\leq\frac{d-1}{2}$. The projector onto $V_{j}$ is denoted by
$\Pi_{V_{j}}$. On each subspace $V_{j}$, we define states

$\displaystyle|j_{\times}\rangle=\frac{1}{\sqrt{2}}(|j\rangle+|d-j\rangle)$
$\displaystyle|(d-j)_{\times}\rangle=\frac{1}{\sqrt{2}}(|j\rangle-|d-j\rangle)$
(35)

and

$\displaystyle|j_{+}\rangle=\cos(-\frac{j\pi}{2d})|j\rangle+\sin(-\frac{j\pi}{2d})|d-j\rangle$
$\displaystyle|(d-j)_{+}\rangle=\sin(-\frac{j\pi}{2d})|j\rangle-\cos(-\frac{j\pi}{2d})|d-j\rangle$
(36)
$\displaystyle|j_{-}\rangle=\cos(-\frac{j\pi}{2d})|j\rangle-\sin(-\frac{j\pi}{2d})|d-j\rangle$
$\displaystyle|(d-j)_{-}\rangle=\sin(-\frac{j\pi}{2d})|j\rangle+\cos(-\frac{j\pi}{2d})|d-j\rangle.$
(37)

Note that $\\{|j_{\times}\rangle,|(d-j)_{\times}\rangle\\}$,
$\\{|j_{+}\rangle,|(d-j)\rangle_{+}\\}$ and
$\\{|j_{-}\rangle,|(d-j)_{-}\rangle\\}$ are three sets of basis states of
$V_{j}$. These are the states that the ideal strategy measures.

The shared state of the ideal strategy is

$\displaystyle|\tilde{\psi}\rangle^{EXT}=$
$\displaystyle\frac{1}{\sqrt{d-1}}\sum_{j=1}^{(d-1)/2}e^{ij\pi/d}(|j\rangle|j\rangle+|d-j\rangle|d-j\rangle).$
(38)

Note that in the standard basis of $W_{d-1}$,

$\displaystyle|\tilde{\psi}\rangle^{EXT}=\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{j}\rangle|x_{d-j}\rangle.$

First of all, the ideal strategy ensures that when Alice and Bob get the same
question from the set $\\{0,n(r)+1,n(r)+2\\}$, they always give the same
answer. Alice’s and Bob’s measurements for questions $0,n(r)+1$ and $n(r)+2$
are

$\displaystyle\tilde{P}_{0}^{0}=\tilde{Q}_{0}^{0}=\Pi_{V_{1}}$
$\displaystyle\tilde{P}_{0}^{2}=\tilde{Q}_{0}^{2}=\Pi_{V_{1}}^{\perp}$
$\displaystyle\tilde{P}_{n(r)+1}^{0}=\tilde{Q}_{n(r)+1}^{0}=|1\rangle\langle
1|$
$\displaystyle\tilde{P}_{n(r)+1}^{1}=\tilde{Q}_{n(r)+1}^{1}=|d-1\rangle\langle
d-1|$
$\displaystyle\tilde{P}_{n(r)+2}^{0}=\tilde{Q}_{n(r)+2}^{0}=|1_{\times}\rangle\langle
1_{\times}|$
$\displaystyle\tilde{P}_{n(r)+2}^{1}=\tilde{Q}_{n(r)+2}^{1}=|(d-1)_{\times}\rangle\langle(d-1)_{\times}|$
$\displaystyle\tilde{P}_{n(r)+1}^{2}=\tilde{Q}_{n(r)+1}^{2}=\Pi_{V_{1}}^{\perp}$
$\displaystyle\tilde{P}_{n(r)+2}^{2}=\tilde{Q}_{n(r)+2}^{2}=\Pi_{V_{1}}^{\perp},$

where

$\displaystyle\Pi_{V_{1}}^{\perp}=\mathbb{1}-\Pi_{V_{1}}.$

Intuitively, these questions force Alice and Bob to agree on the subspace
$V_{1}$ and on the basis of $V_{1}$ that they measure.

The ideal strategy also ensures that when Alice gets $x\in\\{1,2\\}$ and Bob
gets $y\in\\{n(r)+1,n(r)+2\\}$, their answers $a,b\in\\{0,1\\}$ should
maximize $\mathcal{I}_{\cot(-\pi/d)}$ with Alice and Bob’s roles flipped; and
when Alice gets $x\in\\{n(r)+1,n(r)+2\\}$ and Bob gets $y\in\\{1,2\\}$, their
answers $a,b\in\\{0,1\\}$ should maximize $\mathcal{I}_{\cot(-\pi/d)}$. This
is the reason behind naming this test the extended weighted CHSH test. It is
also the reason behind having Alice and Bob agreeing on the subspace $V_{1}$.

When Alice and Bob gets question $1$ or $2$, what they measure are

$\displaystyle\tilde{P}_{1}^{0}=\tilde{Q}_{1}^{0}=\sum_{j=1}^{(d-1)/2}|j_{+}\rangle\langle
j_{+}|$
$\displaystyle\tilde{P}_{1}^{1}=\tilde{Q}_{1}^{1}=\sum_{j=1}^{(d-1)/2}|(d-j)_{+}\rangle\langle(d-j)_{+}|$
$\displaystyle\tilde{P}_{2}^{0}=\tilde{Q}_{2}^{0}=\sum_{j=1}^{(d-1)/2}|j_{-}\rangle\langle
j_{-}|$
$\displaystyle\tilde{P}_{1}^{1}=\tilde{Q}_{1}^{1}=\sum_{j=1}^{(d-1)/2}|(d-j)_{-}\rangle\langle(d-j)_{-}|.$

In particular, their measurements on $V_{1}$ for question $1$ and $2$, follow
the measurements to achieve $\mathcal{I}_{\cot(-\pi/d)}^{\max}$. What they
measure on the complementary of $V_{1}$ in $W_{d-1}$ is irrelevant for this
test, but important for the full test introduced in the next section.

##  5 The full test

The full test consists of the linear system game $LS(r)$, the extended
weighted CHSH test and a commutation game. We explain how the games and test
are conducted and introduce the ideal strategy for each of them in Section
5.1. Then we explain how they are combined in the full test and present the
ideal strategy for the full test in Section 5.2. The full correlation, denoted
by $\mathfrak{C}(r,d)$, is generated by the ideal strategy and presented in
Section 5.3.

###  5.1 The components of the full test

The first component of the full test is $LS(r)$ (Definition 3.8). The ideal
strategy of $LS(r)$ follows the representation $\Psi$ of $\Gamma$ (Definition
B.3). Recall the two Hilbert spaces $W_{d-1}$ and $W_{2}$ defined in eq. 19.
In the ideal strategy Alice and Bob share the state

$\displaystyle|\tilde{\psi}\rangle^{LS}=\frac{1}{2}(|x_{1}\rangle|x_{1}\rangle+|x_{2}\rangle|x_{2}\rangle)^{\otimes
2}\otimes\left(\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{j}\rangle|x_{d-j}\rangle\right).$
(39)

Alice and Bob’s observables for each variable $x(s)$ are defined by

$\displaystyle\tilde{M}(s)=\tilde{N}(s)=\Psi(s)$

for each $s\in S$.

The second component is the extended weighted CHSH test, introduced in Section
4.2.

The third component is a commutation game. Our commutation game is based on
the commutation test used in [CGJV19]. The goal of the commutation game is to
make sure that some of Alice’s binary observables for $LS(r)$ commute with her
observable for the extended weighted CHSH test, when acting on the shared
state. So we reuse questions and answers from the two other components of the
full test.

Bob’s input set consists of eight question pairs

$\displaystyle\mathcal{Y}^{COMM}=\\{(n(r)+1,x(s)),(n(r)+2,x(s)):s=f_{0},f_{2},g_{0},g_{2}\\},$

and Alice’s input set is

$\displaystyle\mathcal{X}^{COMM}=\\{n(r)+1,n(r)+2,x(f_{0}),x(f_{2}),x(g_{0}),x(g_{2})\\}.$

The answer sets are

$\displaystyle\mathcal{A}^{COMM}_{x}=\begin{cases}\mathbb{Z}_{3}&\text{ if
}x\in\\{n(r)+1,n(r)+2\\}\\\ \mathbb{Z}_{2}&\text{otherwise.}\end{cases}$
$\displaystyle\mathcal{B}^{COMM}=\mathbb{Z}_{3}\times\mathbb{Z}_{2}.$

The probability distribution is

$\displaystyle\pi^{COMM}(x,(y_{1},y_{2}))=\begin{cases}1/16&\text{ if
}x=y_{1}\text{ or }x=y_{2}\\\ 0&\text{ otherwise}.\end{cases}$

The scoring function is

$\displaystyle V^{COMM}(a,(b_{1},b_{2}),x,(y_{1},y_{2}))=\begin{cases}1&\text{
if }x=y_{1}\text{ and }a=b_{1}\\\ 1&\text{ if }x=y_{2}\text{ and }a=b_{2}\\\
0&\text{ otherwise}.\end{cases}$

The probability distribution makes sure that Alice gets one of the two
questions that Bob gets. To win this game, Alice and Bob should agree on the
answer to the common question.

We defer the ideal strategy for this test till the next subsection because the
ideal strategy for the other two tests above can win this game as well.

###  5.2 The full test and the ideal strategy

######  Definition 5.1 (The full test).

Define

$\displaystyle\mathcal{X}^{EXT^{\prime}}=\mathcal{Y}^{EXT^{\prime}}=\\{0,x(a_{1}),x(a_{2}),n(r)+1,n(r)+2\\}.$

The question sets of the full test are

$\displaystyle\mathcal{X}=\mathcal{X}^{LS}\cup\mathcal{X}^{EXT^{\prime}}\cup\mathcal{X}^{COMM},$
$\displaystyle\mathcal{Y}=\mathcal{Y}^{LS}\cup\mathcal{Y}^{EXT^{\prime}}\cup\mathcal{Y}^{COMM}.$

Define answer sets $\mathcal{A}_{x}^{EXT^{\prime}}$ for each
$x\in\mathcal{X}^{EXT^{\prime}}$ by

$\displaystyle\mathcal{A}_{x(a_{1})}^{EXT^{\prime}}=\mathcal{A}_{1}^{EXT}$
$\displaystyle\mathcal{A}_{x(a_{2})}^{EXT^{\prime}}=\mathcal{A}_{2}^{EXT}$
$\displaystyle\mathcal{A}_{x}^{EXT^{\prime}}=\mathcal{A}_{x}^{EXT}\quad\text{
for }x\neq x(a_{1}),x(a_{2})$

The answer sets $\mathcal{B}_{y}^{EXT^{\prime}}$ are defined analogously. The
answer sets of the full test are

$\displaystyle\mathcal{A}_{x}=\begin{cases}\mathcal{A}_{x}^{LS}&\text{ if
}x\in\mathcal{X}^{LS}\\\ \mathcal{A}_{x}^{EXT^{\prime}}&\text{ if
}x\in\mathcal{X}^{EXT^{\prime}}\\\ \mathcal{A}_{x}^{COMM}&\text{ if
}x\in\mathcal{X}^{COMM},\end{cases}$
$\displaystyle\mathcal{B}_{y}=\begin{cases}\mathbb{Z}_{2}&\text{ if
}y\in\mathcal{Y}^{LS}\\\ \mathcal{B}_{y}^{EXT^{\prime}}&\text{ if
}y\in\mathcal{Y}^{EXT^{\prime}}\\\ \mathcal{B}_{y}^{COMM}&\text{ if
}y\in\mathcal{Y}^{COMM}.\end{cases}$

Define

$\displaystyle N:=N(r)+25+16=157r+726.$

The question distribution of the full test,
$\pi:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ is defined by

$\displaystyle\pi(x,y)=\begin{cases}\frac{1}{N}&\text{ if
}(x,y)\in\mathcal{X}^{LS}\times\mathcal{Y}^{LS}\text{ and }\pi^{LS}(x,y)>0\\\
\frac{1}{N}&\text{ if
}(x,y)\in\mathcal{X}^{EXT^{\prime}}\times\mathcal{Y}^{EXT^{\prime}}\\\
\frac{1}{N}&\text{ if
}(x,y)\in\mathcal{X}^{COMM}\times\mathcal{Y}^{COMM}\text{ and
}\pi^{COMM}(x,y)>0\\\ 0&\text{ otherwise}.\end{cases}$

Note that $\mathcal{X}^{EXT^{\prime}}$ is obtained from $\mathcal{X}^{EXT}$ by
replacing $1$ by $x(a_{1})$ and $2$ by $x(a_{2})$, and similarly for
$\mathcal{Y}^{EXT^{\prime}}$. The answer sets $\mathcal{A}_{x}^{EXT^{\prime}}$
are constructed from $\mathcal{A}_{x}^{EXT}$ in a similar way.

The ideal strategy for the full test is an extension of the ideal strategy of
$LS(r)$ to make it generate the ideal correlation of the extended weighted
CHSH test. Recall the subspace $W_{d-1}$ and $W_{2}$ defined in eq. 19. The
shared state of the ideal strategy is

$\displaystyle|\tilde{\psi}\rangle=|\tilde{\psi}\rangle^{LS}=\frac{1}{2}(|x_{1}\rangle|x_{1}\rangle+|x_{2}\rangle|x_{2}\rangle)^{\otimes
2}\otimes|\tilde{\psi}\rangle^{EXT}.$ (40)

Alice and Bob’s observables for each variable in the linear system of $LS(r)$
are

$\displaystyle\tilde{M}(s)=\tilde{N}(s)=\Psi(s)$

for each $s\in S$ and $\Psi$ is defined in Definition B.3. When Alice get
$I_{i}\in\mathcal{X}^{LS}$, she measures her half of the shared state
according to $\tilde{M}(s)$ for each $s\in I_{i}$.

Alice’s and Bob’s observables for question $x(a_{1})$ and $x(a_{2})$ of
$\mathcal{X}^{EXT^{\prime}}$ and $\mathcal{Y}^{EXT^{\prime}}$ are

$\displaystyle\tilde{M}(a_{j})=\tilde{N}(a_{j})=\Psi(a_{j})$

for $j=1,2$. They can reproduce the ideal correlation because

$\displaystyle\tilde{M}(a_{j})=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes(\tilde{P}_{j}^{0}-\tilde{P}_{j}^{1})$
$\displaystyle\tilde{N}(a_{j})=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes(\tilde{Q}_{j}^{0}-\tilde{Q}_{j}^{1}),$

for $j=1,2$, which can be checked using eqs. 32, 33, 36 and 37. In particular,
the observables $\tilde{M}(a_{j})$ and $\tilde{N}(a_{j})$ are measuring the
same state on the subspace $V_{1}$ as $\tilde{P}_{j}$ and $\tilde{Q}_{j}$ for
$j=1,2$.

Recall the ideal projectors $\tilde{P}_{x}^{a}$ and $\tilde{Q}_{y}^{b}$ for
the extended weighted CHSH test defined in Section 4.2. Alice’s projectors for
the question $x\in\\{0,n(r)+1,n(r)+2\\}$ of $\mathcal{X}^{EXT^{\prime}}$ are

$\displaystyle\tilde{M}_{x}^{a}=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\tilde{P}_{x}^{a}$

for each $a\in\mathcal{A}^{EXT^{\prime}}_{x}$. Bob’s projectors for the
question $y\in\\{0,n(r)+1,n(r)+2\\}$ of $\mathcal{Y}^{EXT^{\prime}}$ are

$\displaystyle\tilde{N}_{y}^{b}=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\tilde{Q}_{y}^{b}$

for each $b\in\mathcal{B}^{EXT^{\prime}}_{y}$.

Alice’s measurements for $x\in\mathcal{X}^{COMM}$ is the same as her
measurements for the other two tests. When Bob gets question
$(y_{1},y_{2})\in\mathcal{Y}^{COMM}$, he measures according to
$\tilde{N}_{y_{1}}^{b}$ first and then $\tilde{N}(y_{2})$ because
$\tilde{N}_{y_{1}}^{b}$ commutes with $\tilde{N}(y_{2})$ for all $b$ by
construction. This ensures that the ideal strategy can win the commutation
game.

An important property of the ideal strategy for it to win $LS(r)$ is
summarized in the following proposition.

######  Proposition 5.2.

The observables $\tilde{M}(s)$, $\tilde{N}(s)$ and the shared state
$|\tilde{\psi}\rangle$ defined above satisfy the relations

$\displaystyle\tilde{M}(s)\tilde{N}(s)|\tilde{\psi}\rangle=|\tilde{\psi}\rangle,$
(41)

for each $s\in S$.

###### Proof.

Define
$S^{\prime}=\\{f_{0},f_{1},f_{2},g_{0},g_{1},g_{2},m_{0},m_{1},m_{2}\\}\subset
S$. Notice that for each $s\in S^{\prime}$, both $\tilde{M}(s)$ and
$\tilde{N}(s)$ act trivially on $W_{d-1}$, so we omit the verification about
$\tilde{M}(s)\tilde{N}(s)|\tilde{\psi}\rangle=|\tilde{\psi}\rangle$ for each
$s\in S^{\prime}$

Next, we notice that each $s\in S$ can be expressed as the product of a
sequence of generators in $S^{\prime}$ and $a_{1},a_{2},a_{3},a_{4}$ following
the relations in $R$, so to prove eq. 41, it suffices to prove that it holds
true for $s=a_{1},a_{2},a_{3},a_{4}$. Recall that
$\tilde{M}(a_{j})=\tilde{N}(a_{j})=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes
Psi_{0}(a_{j})$ in Definition B.3, where $\Psi_{0}$ is defined in Definition
B.1, and
$|\tilde{\psi}\rangle=\frac{1}{2}(|x_{1}\rangle|x_{1}\rangle+|x_{2}\rangle|x_{2}\rangle)^{\otimes
2}\otimes|\tilde{\psi}\rangle^{EXT}$. Hence, the problem is further reduced to
proving

$\displaystyle\Psi_{0}(a_{j})\otimes\Psi_{0}(a_{j})|\tilde{\psi}\rangle^{EXT}=|\tilde{\psi}\rangle^{EXT}.$

for $1\leq j\leq 4$.

Using eqs. 22 and 23, it is straightforward to see that
$\Psi_{0}(a_{j})\otimes\Psi_{0}(a_{j})|\tilde{\psi}\rangle^{EXT}=|\tilde{\psi}\rangle^{EXT}$
for $j=1,2$. Before checking the two cases $j=3$ and $j=4$, we can use eqs. 24
and 25 to derive that

$\displaystyle\Psi_{0}(a_{3}a_{4})\otimes\Psi_{0}(a_{3}a_{4})|\tilde{\psi}\rangle^{EXT}=|\tilde{\psi}\rangle^{EXT}.$

The eigenvectors of $\Psi_{0}(a_{3}a_{4})$ are $|u_{k}\rangle$, for $0\leq
k\leq d-2$, and $|u_{k}\rangle$ are defined by

$\displaystyle|u_{k}\rangle=\frac{1}{\sqrt{d-1}}\sum_{j=0}^{d-2}\omega_{d-1}^{jk}|x_{r^{j}}\rangle.$

Hence we can express $|x_{r^{j}}\rangle$ in terms of $|u_{k}\rangle$ as

$\displaystyle|x_{r^{j}}\rangle=\frac{1}{\sqrt{d-1}}\sum_{k=0}^{d-2}\omega_{d-1}^{-jk}|u_{k}\rangle.$

Then using the expression of $\Psi_{0}(a_{4})$ from Definition B.1, we can
deduce that

$\displaystyle\Psi_{0}(a_{4})|x_{r^{j}}\rangle=$
$\displaystyle\frac{1}{\sqrt{d-1}}\Psi_{0}(a_{4})\left(|u_{0}\rangle+\omega_{d-1}^{-j(d-1)/2}|u_{(d-1)/2}\rangle+\sum_{k=1}^{(d-3)/2}(\omega_{d-1}^{-jk}|u_{k}\rangle+\omega_{d-1}^{jk}|u_{d-1-k}\rangle)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{d-1}}\left(|u_{0}\rangle+(-1)^{j}|u_{(d-1)/2}\rangle+\sum_{k=1}^{(d-3)/2}(\omega_{d-1}^{-jk}|u_{d-1-k}\rangle+\omega_{d-1}^{jk}|u_{k}\rangle)\right)$
$\displaystyle=$ $\displaystyle|x_{r^{d-1-j}}\rangle.$

Note that the expression of $\Psi_{0}(a_{4})$ can also be found in eq. 25, as
$\Psi(a_{4})=\mathbb{1}_{W_{2}}\otimes\mathbb{1}_{W_{2}}\otimes\Psi_{0}(a_{4})$.
Consequently, we can show that
$\Psi_{0}(a_{4})\otimes\Psi_{0}(a_{4})|\tilde{\psi}\rangle^{EXT}=|\tilde{\psi}\rangle^{EXT}$
because

$\displaystyle\Psi_{0}(a_{4})\otimes\Psi_{0}(a_{4})|\tilde{\psi}\rangle^{EXT}$
$\displaystyle=\frac{1}{\sqrt{d-1}}\sum_{j=0}^{d-2}\Psi_{0}(a_{4})\otimes\Psi_{0}(a_{4})|x_{r^{j}}\rangle|x_{r^{d-1-j}}\rangle$
$\displaystyle=\frac{1}{\sqrt{d-1}}\sum_{j=0}^{d-2}|x_{r^{d-1-j}}\rangle|x_{r^{j}}\rangle$
$\displaystyle=|\tilde{\psi}\rangle^{EXT},$

Combining it with the fact that
$\Psi_{0}(a_{3}a_{4})\otimes\Psi_{0}(a_{3}a_{4})|\tilde{\psi}\rangle^{EXT}=|\tilde{\psi}\rangle^{EXT}$,
we can conclude that
$\Psi_{0}(a_{3})\otimes\Psi_{0}(a_{3})|\tilde{\psi}\rangle^{EXT}=|\tilde{\psi}\rangle^{EXT}$.
∎

###  5.3 The correlation $\mathfrak{C}(d,r)$

The full correlation is generated by the ideal strategy presented in the
previous subsection. We denote the full correlation by
$\mathfrak{C}(d,r)=\\{(\tilde{P}(a,b|x,y))_{a,b}\\}_{x,y}$. To help readers to
understand the proofs in Section 6 better, parts of the full correlation are
given in the tables below.

| $x=n(r)+1$ | $x=n(r)+2$
---|---|---
| $a=0$ | $a=1$ | $a=0$ | $a=1$
$y=1$ | $b=0$ | $\frac{\cos^{2}(\pi/2d)}{d-1}$ | $\frac{\sin^{2}(\pi/2d)}{d-1}$ | $\frac{1-\sin(\pi/d)}{2(d-1)}$ | $\frac{1+\sin(\pi/d)}{2(d-1)}$
$b=1$ | $\frac{\sin^{2}(\pi/2d)}{d-1}$ | $\frac{\cos^{2}(\pi/2d)}{d-1}$ | $\frac{1+\sin(\pi/d)}{2(d-1)}$ | $\frac{1-\sin(\pi/d)}{2(d-1)}$
$y=2$ | $b=0$ | $\frac{\cos^{2}(\pi/2d)}{d-1}$ | $\frac{\sin^{2}(\pi/2d)}{d-1}$ | $\frac{1+\sin(\pi/d)}{2(d-1)}$ | $\frac{1-\sin(\pi/d)}{2(d-1)}$
$b=1$ | $\frac{\sin^{2}(\pi/2d)}{d-1}$ | $\frac{\cos^{2}(\pi/2d)}{d-1}$ | $\frac{1-\sin(\pi/d)}{2(d-1)}$ | $\frac{1+\sin(\pi/d)}{2(d-1)}$
Table 1: The correlation for $x\in\\{n(r)+1,n(r)+2\\}$ and $y\in\\{1,2\\}$.

We don’t explicitly calculate the conditional probabilities of the form
$P(2,0|x,y)$ when $x\in\\{n(r)+1,n(r)+2\\}$ and $y\in\\{1,2\\}$ because they
are irrelevant. Note that when $x\in\\{1,2\\}$ and $y\in\\{n(r)+1,n(r)+2\\}$,
the correlation table is very similar to Table 1, so we omit it here.

| $x=n(r)+1$ | $x=n(r)+2$ | $x=0$
---|---|---|---
| $a=0$ | $a=1$ | $a=2$ | $a=0$ | $a=1$ | $a=2$ | $a=0$ | $a=2$
$y=n(r)+1$ | $b=0$ | $\frac{1}{d-1}$ | $0$ | 0 | $\frac{1}{2d-2}$ | $\frac{1}{2d-2}$ | 0 | $\frac{1}{d-1}$ | 0
$b=1$ | 0 | $\frac{1}{d-1}$ | $0$ | $\frac{1}{2d-2}$ | $\frac{1}{2d-2}$ | 0 | $\frac{1}{d-1}$ | 0
$b=2$ | 0 | 0 | $\frac{d-3}{d-1}$ | 0 | 0 | $\frac{d-3}{d-1}$ | 0 | $\frac{d-3}{d-1}$
$y=n(r)+2$ | $b=0$ | $\frac{1}{2d-2}$ | $\frac{1}{2d-2}$ | 0 | $\frac{1}{d-1}$ | $0$ | 0 | $\frac{1}{d-1}$ | 0
$b=1$ | $\frac{1}{2d-2}$ | $\frac{1}{2d-2}$ | $0$ | 0 | $\frac{1}{d-1}$ | $0$ | $\frac{1}{d-1}$ | 0
$b=2$ | 0 | 0 | $\frac{d-3}{d-1}$ | 0 | 0 | $\frac{d-3}{d-1}$ | 0 | $\frac{d-3}{d-1}$
$y=0$ | $b=0$ | $\frac{1}{d-1}$ | $\frac{1}{d-1}$ | 0 | $\frac{1}{d-1}$ | $\frac{1}{d-1}$ | 0 | $\frac{2}{d-1}$ | 0
$b=2$ | 0 | 0 | $\frac{d-3}{d-1}$ | 0 | 0 | $\frac{d-3}{d-1}$ | 0 | $\frac{d-3}{d-1}$
Table 2: The correlation for $x,y\in\\{0,n(r)+1,n(r)+2\\}$. | $y=(n(r)+1,f_{0})$
---|---
| $b=(0,0)$ | $b=(0,1)$ | $b=(1,0)$ | $b=(1,1)$ | $b=(2,0)$ | $b=(2,1)$
$x=n(r)+1$ | $a=0$ | $\frac{1}{2d-2}$ | $\frac{1}{2d-2}$ | $0$ | $0$ | $0$ | $0$
$a=1$ | $0$ | $0$ | $\frac{1}{2d-2}$ | $\frac{1}{2d-2}$ | $0$ | $0$
$a=2$ | 0 | 0 | $0$ | 0 | $\frac{d-3}{2d-2}$ | $\frac{d-3}{2d-2}$
$x=f_{0}$ | $a=0$ | $\frac{1}{2d-2}$ | $0$ | $\frac{1}{2d-2}$ | $0$ | $\frac{d-3}{2d-2}$ | 0
$a=1$ | $0$ | $\frac{1}{2d-2}$ | $0$ | $\frac{1}{2d-2}$ | $0$ | $\frac{d-3}{2d-2}$
Table 3: The correlation for the commutation test for questions $x(f_{0})$ and
$n(r)+1$.

The correlation tables for the other seven pairs of questions of the
commutation game are similar.

##  6 Robust self-testing with $\mathfrak{C}(d,r)$

In this section, we examine the properties of a strategy $\mathbbmtt{S}$ that
can reproduce the correlation $\mathfrak{C}(d,r)$ approximately and prove that
the shared state of $\mathbbmtt{S}$ must be close to the state
$|\tilde{\psi}\rangle$ up to some local isometry.

We first give the definition of an approximate strategy of a fixed
correlation.

######  Definition 6.1.

Let $\mathcal{X},\mathcal{Y}$ be input alphabets,
$\\{\mathcal{A}_{x}\\}_{x\in\mathcal{X}},\\{\mathcal{B}_{y}\\}_{y\in\mathcal{Y}}$
be families of output alphabets. For a correlation
$\tilde{C}=(\tilde{P}(a,b|x,y))$ with
$(a,b)\in\mathcal{A}_{x}\times\mathcal{B}_{y}$ and
$(x,y)\in\mathcal{X}\times\mathcal{Y}$, and a distribution $\pi$ over all the
$(x,y)\in\mathcal{X}\times\mathcal{Y}$, we say a quantum strategy
$\mathbbmtt{S}=(|\psi\rangle,\\{M_{x}^{a}\\},\\{N_{y}^{b}\\})$ is an
$\epsilon$-approximate quantum strategy of $\tilde{C}$ with respect to the
distribution $\pi$, if it produces the correlation
$(P(a,b|x,y)=\langle\psi|M_{x}^{a}N_{y}^{b}|\psi\rangle)$ such that

$\displaystyle\operatorname*{\mathbb{E}}_{(x,y)\sim\pi}\left[\sum_{ab}\lvert
P(a,b|x,y)-\tilde{P}(a,b|x,y)\rvert\right]\leq\epsilon.$ (42)

In our full test, the probability distribution over question pairs is $\pi$
given in Definition 5.1. In the rest of this section, when we say some
strategy can approximate $\mathfrak{C}(d,r)$, we mean that the approximation
is with respect to this distribution $\pi$.

The number of all the possible question pairs is $N=\Theta(r)$. Considering
that the number of possible output pairs is constant for each question pair
$(x,y)$, the approximate condition in eq. 42 directly implies that, if
$\mathbbmtt{S}$ is an $\epsilon$-approximate strategy of $\mathfrak{C}(d,r)$,
then

$\displaystyle P(a,b|x,y)\simeq_{O(r\epsilon)}\tilde{P}(a,b|x,y),$

for all valid $(a,b,x,y)$ of the full test.

In the next three subsections, we analyze the implication of an approximate
strategy for the correlations of the three components introduced in Section
5.1.

###  6.1 Implication of approximately winning $LS(r)$

In this subsection, we study the implications of a strategy that can win
$LS(r)$ with probability close to $1$. We prove a series of propositions,
which lead us to Lemma 6.7. Lemma 6.7 is a key step of the self-testing proof
in Section 6.4.

Recall that in $LS(r)$ the question pair is denoted by $(I_{i},x(s))$ where
$I_{i}$ labels an equation and $x(s)$ is a variable for some $s\in I_{i}$. We
denote Alice’s observable for variable $x(s)$ in equation $i$ by $M_{i}(s)$
and Bob’s observable for variable $x(s)$ by $N(s)$.

The first implication of an approximate winning strategy is given in the
proposition below.

######  Proposition 6.2.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Define $M(s):=M_{i}(s)$ where $i$ is the smallest among
all $i$’s such that $x(s)\in I_{i}$. Then,

$\displaystyle
M(s)N(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|\psi\rangle$ (43)
$\displaystyle\Pi_{s\in
I_{i}}M(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(-1)^{c(i)}|\psi\rangle,$
(44)

for all $s\in S$.

###### Proof.

The condition that $(\tilde{P}(\boldsymbol{a},b|I_{i},s))$ of
$\mathfrak{C}(d,r)$ wins the linear system game optimally is equivalent to

$\displaystyle\sum_{\boldsymbol{a},b:\boldsymbol{a}\in
X_{i},a(j)=b}\tilde{P}(\boldsymbol{a},b|I_{i},s)=1$

for all $i=1\dots m(r)$. We also know that the shared state $|\psi\rangle$ and
observables $M_{i}(s)$ and $N(s)$ of $\mathbbmtt{S}$ satisfy the relation

$\displaystyle\langle\psi|M_{i}(s)N(s)|\psi\rangle$
$\displaystyle=2\sum_{\boldsymbol{a},b:\boldsymbol{a}\in
X_{i},a(s)=b}P(\boldsymbol{a},b|I_{i},s)-1,$

as proved in [Slo19]. Using the fact that $\mathbbmtt{S}$ approximates the
winning correlation of $LS(r)$, we can further see that

$\displaystyle\langle\psi|M_{i}(s)N(s)|\psi\rangle\simeq_{O(r\epsilon)}2\sum_{\boldsymbol{a},b:\boldsymbol{a}\in
X_{i},a(j)=b}\tilde{P}(\boldsymbol{a},b|I_{i},s)-1=1.$

Since $M_{i}(s)$ and $N(s)$ are binary observables, the equation above implies
that

$\displaystyle\lVert
M_{i}(s)|\psi\rangle-N(s)|\psi\rangle\rVert^{2}=2-2\langle\psi|M_{i}(s)N(s)|\psi\rangle\leq
2-2(1-O(r\epsilon))=O(r\epsilon),$

or equivalently,

$\displaystyle
M_{i}(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N(s)|\psi\rangle,$

for each $1\leq i\leq m(r)$ and generator $s$ of $\Gamma$. Recall that
$M(s):=M_{i}(s)$ for the smallest $i$ such that $s\in I_{i}$. Therefore,

$\displaystyle M(s)N(s)|\psi\rangle$ $\displaystyle=M_{i}(s)N(s)|\psi\rangle$
$\displaystyle=N(s)M_{i}(s)|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N(s)^{2}|\psi\rangle$
$\displaystyle=|\psi\rangle$

for all $s\in S$.

The fact that $\mathbbmtt{S}$ is an $\epsilon$-approximate strategy also tells
us that Alice gives satisfying assignment for each equation with probability
$1-O(r\epsilon)$, or equivalently,

$\displaystyle\Pi_{s\in
I_{i}}M_{i}(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(-1)^{c(i)}|\psi\rangle$

for $1\leq i\leq m(r)$. If we replace each $M_{i}(s)$ with $M(s)$ in the
equation above, we demonstrate the effect on a general case that
$I_{i}=\\{s_{1},s_{2},s_{3}\\}$,

$\displaystyle\lVert
M_{i}(s_{1})M_{i}(s_{2})M_{i}(s_{3})|\psi\rangle-M(s_{1})M(s_{2})M(s_{3})|\psi\rangle\rVert$
$\displaystyle\leq$ $\displaystyle\lVert
M_{i}(s_{1})M_{i}(s_{2})M_{i}(s_{3})|\psi\rangle-M(s_{1})M_{i}(s_{2})M_{i}(s_{3})|\psi\rangle\rVert$
$\displaystyle+\lVert
M(s_{1})M_{i}(s_{2})M_{i}(s_{3})|\psi\rangle-M(s_{1})M(s_{2})M_{i}(s_{3})|\psi\rangle\rVert$
$\displaystyle+\lVert
M(s_{1})M(s_{2})M_{i}(s_{3})|\psi\rangle-M(s_{1})M(s_{2})M(s_{3})|\psi\rangle\rVert$
$\displaystyle\leq$ $\displaystyle
3O(\sqrt{r}\sqrt{\epsilon})=O(\sqrt{r}\sqrt{\epsilon}),$

where we bound each term in line $2,3$ and $4$ by Lemma 2.17. Hence we can
conclude that

$\displaystyle\Pi_{s\in
I_{i}}M(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(-1)^{c(i)}|\psi\rangle$

for $1\leq i\leq m(r)$. Note that with the same technique, we can prove that

$\displaystyle\Pi_{s\in
I_{i}}N(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(-1)^{c(i)}|\psi\rangle$

for $1\leq i\leq m(r)$. ∎

To make the following derivations easier to understand, we introduce a new
terminology.

######  Definition 6.3.

Let $S$ be a set of generators, and $\\{s_{i}\\}_{i=1}^{n}$ and
$\\{s^{\prime}_{j}\\}_{j=1}^{m}$ be two sequences of $S$. Define a relation
$r$, whose equation form is $\Pi_{i=1}^{n}s_{i}=\Pi_{j=1}^{m}s^{\prime}_{j}$.
We say operators $\\{M(s):s\in S\\}$ $\epsilon$-approximately satisfy the
relation $r$ on the state $|\psi\rangle$ if

$\displaystyle\Pi_{i=1}^{n}M(s_{i})|\psi\rangle\simeq_{\epsilon}\Pi_{j=1}^{m}M(s^{\prime}_{j})|\psi\rangle.$

Using the new terminology, Proposition 6.2 can be rephrased as the following
proposition.

######  Proposition 6.4.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then the observables $\\{M(s)\\}_{s\in S}$ and
$\\{N(s)\\}_{s\in S}$ defined in Proposition 6.2,
$O(\sqrt{r}\sqrt{\epsilon})$-approximately satisfy each relation $t\in R$ on
the shared state $|\psi\rangle$, where $S$ is the generator set of $\Gamma$
and and $R$ is the relation set of $\Gamma$.

Recall that the group $\mathcal{P}_{1}$ (Definition 3.3) is embedded in
$\Gamma$, as proved in Proposition 3.6. Following the embedding procedure, we
can prove the next proposition.

######  Proposition 6.5.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then the observables $\\{M(s)\\}_{s\in S_{1}}$ and
$\\{N(s)\\}_{s\in S_{1}}$, defined in Proposition 6.4,
$O(\sqrt{r}\sqrt{\epsilon})$-approximately satisfy each relation $t\in R_{1}$
on $|\psi\rangle$, where $S_{1}$ is the generator set of $\mathcal{P}_{1}$ and
$R_{1}$ is the relation set of $\mathcal{P}_{1}$.

###### Proof.

We prove

$\displaystyle
M(f_{0})M(b_{1})M(f_{0})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(c_{1})|\psi\rangle$
(45)

to demonstrate the techniques. From the fact that Alice’s observables
$O(\sqrt{r}\sqrt{\epsilon})$-approximately satisfy the linear relations of
$\Gamma$, we can get that

$\displaystyle
M(f_{0})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{1})M(f_{2})|\psi\rangle$
$\displaystyle
M(b_{1})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{2})M(p_{1,1})|\psi\rangle$
$\displaystyle
M(f_{0})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(p_{1,3})M(p_{1,4})|\psi\rangle$

Then we expand $M(f_{0})M(b_{1})M(f_{0})|\psi\rangle$ using the three
equations above and Lemma 2.17,

$\displaystyle M(f_{0})M(b_{1})M(f_{0})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{1})M(f_{2})M(b_{1})M(f_{0})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{1})M(f_{2})M(f_{2})M(p_{1,1})M(f_{0})|\psi\rangle$
$\displaystyle=M(f_{1})M(p_{1,1})M(f_{0})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{1})M(p_{1,1})M(p_{1,3})M(p_{1,4})|\psi\rangle.$

In the rest of the proof, we skip steps of applying Lemma 2.17. Next, we can
simplify $M(f_{0})M(b_{1})M(f_{0})|\psi\rangle$ as

$\displaystyle M(f_{0})M(b_{1})M(f_{0})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{1})M(p_{1,1})M(p_{1,3})M(p_{1,4})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{1})M(p_{1,2})M(p_{1,4})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(p_{1,5})M(p_{1,4})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(c_{1})|\psi\rangle,$

where from the second line to the third line, we used the relation
$M(p_{1,1})M(p_{1,2})M(p_{1,3})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|\psi\rangle$,
and from the third line to the fourth line, we used the relation
$M(c_{1})M(p_{1,4})M(p_{1,5})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|\psi\rangle$.

The derivation of other relations in $R_{1}$ from relations in $R$ involves
the same number of substitutions and uses similar techniques, so we omit it
here. ∎

Essentially the proof above follows the proof of Proposition 3.6, so we can
follow the proof of Proposition 3.4 to prove the next proposition.

######  Proposition 6.6.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then the observables $\\{M(s)\\}_{s\in S_{0}}$ and
$\\{N(s)\\}_{s\in S_{0}}$, defined in Proposition 6.4,
$O(\sqrt{r}\sqrt{\epsilon})$-approximately satisfy each relation $t\in R_{0}$
on the shared state $|\psi\rangle$, where $S_{0}$ is the generator set of
$\mathcal{P}_{0}$ and $R_{0}$ is the relation set of $\mathcal{P}_{0}$.

Following the steps of the embedding of
$(a_{3}a_{4})^{l}a_{1}a_{2}(a_{4}a_{3})^{l}=(a_{1}a_{2})^{r^{l}}$ into
$\Gamma$ presented in the proof of Proposition 3.2, we can prove the next
lemma.

######  Lemma 6.7.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$ and $\\{M(s),N(s)\\}_{s\in S}$ be the observables defined
in Proposition 6.4. Then,

$\displaystyle
M(a_{1})M(a_{2})(M(a_{4})M(a_{3}))^{l}|\psi\rangle\simeq_{O(r^{l+1/2}\sqrt{\epsilon})}(M(a_{4})M(a_{3}))^{l}(M(a_{1})M(a_{2}))^{r^{l}}|\psi\rangle,$
(46) $\displaystyle
N(a_{1})N(a_{2})(N(a_{4})N(a_{3}))^{l}|\psi\rangle\simeq_{O(r^{l+1/2}\sqrt{\epsilon})}(N(a_{4})N(a_{3}))^{l}(N(a_{1})N(a_{2}))^{r^{l}}|\psi\rangle,$
(47)

for all $l\geq 1$.

###### Proof.

Proving the $l=1$ case is essentially proving that observables
$\\{M(a_{i})\\}_{i=1}^{4}$ and $\\{N(a_{i})\\}_{i=1}^{4}$
$O(r^{3/2}\sqrt{\epsilon})$-approximately satisfy the relation

$\displaystyle(a_{3}a_{4})(a_{1}a_{2})(a_{4}a_{3})=(a_{1}a_{2})^{r}$ (48)

on the shared state $|\psi\rangle$. The derivation follows the proof of
Proposition 3.2. The $O(r^{3/2}\sqrt{\epsilon})$ approximation error comes
from the fact that the derivation of eq. 48 has $\Theta(r)$ substitution
steps, where each substitutes uses a different relation of $R_{0}$. So we have

$\displaystyle
M(a_{1})M(a_{2})(M(a_{4})M(a_{3}))|\psi\rangle\simeq_{O(r^{3/2}\sqrt{\epsilon})}(M(a_{4})M(a_{3}))(M(a_{1})M(a_{2}))^{r}|\psi\rangle.$
(49)

Assume the statement is true for $l=n$ and consider the case that $l=n+1$,

$\displaystyle M(a_{1})M(a_{2})(M(a_{4})M(a_{3}))^{n+1}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(N(a_{3})N(a_{4}))M(a_{1})M(a_{2})(M(a_{4})M(a_{3}))^{n}|\psi\rangle$
$\displaystyle\simeq_{O(r^{n+1/2}\sqrt{\epsilon})}(N(a_{3})N(a_{4}))(M(a_{4})M(a_{3}))^{n}(M(a_{1})M(a_{2}))^{r^{n}}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M(a_{4})M(a_{3}))^{n}(M(a_{1})M(a_{2}))^{r^{n}}(M(a_{4})M(a_{3}))|\psi\rangle$
$\displaystyle\simeq_{O(r^{n+3/2}\sqrt{\epsilon})}(M(a_{4})M(a_{3}))^{n+1}(M(a_{1})M(a_{2}))^{r^{n+1}}|\psi\rangle,$

where from the second last to the last line we repeat the process of applying
eq. 49 and the relation
$(M(a_{1})M(a_{2}))^{r}|\psi\rangle\simeq_{O(r^{3/2}\sqrt{\epsilon})}(N(a_{1})N(a_{2}))^{r}|\psi\rangle$,
$r^{n}$ times. In short, we have

$\displaystyle
M(a_{1})M(a_{2})(M(a_{4})M(a_{3}))^{n+1}|\psi\rangle\simeq_{O(r^{n+3/2}\sqrt{\epsilon})}(M(a_{4})M(a_{3})^{n+1}(M(a_{1})M(a_{2}))^{r^{n+1}}|\psi\rangle.$
(50)

By the principal of induction, the proof is complete. The proof for Bob’s
observables $\\{N(s)\\}_{s\in S}$ is analogous. ∎

We define

$\displaystyle O_{A}:=M(a_{1})M(a_{2})$ $\displaystyle
U_{A}:=M(a_{3})M(a_{4})$ (51) $\displaystyle O_{B}:=N(a_{1})N(a_{2})$
$\displaystyle U_{B}:=N(a_{3})N(a_{4}).$ (52)

The conclusion of Lemma 6.7 can be rewritten as

$\displaystyle
O_{A}(U_{A}^{\dagger})^{n}|\psi\rangle\simeq_{O(r^{n+1/2}\sqrt{\epsilon})}(U_{A}^{\dagger})^{n}O_{A}^{r^{n}}|\psi\rangle.$

On Bob’s side, the similar relation holds.

The other key relations that are embedded in $\Gamma$ are
$f_{0}g_{0}=Jg_{0}f_{0}$ and $f_{2}g_{2}=Jg_{2}f_{2}$. We summarize the
implications in the following proposition.

######  Proposition 6.8.

Let $\mathbbmtt{S}$, $\\{M(s),N(s)\\}_{s\in S}$ be the strategy and
observables defined in Proposition 6.4. Then,

$\displaystyle
M(f_{0})M(g_{0})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}-M(g_{0})M(f_{0})|\psi\rangle$
(53) $\displaystyle
M(f_{2})M(g_{2})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}-M(g_{2})M(f_{2})|\psi\rangle.$
(54)

Following the substitution steps to prove eq. 17 and eq. 18 in the proof of
Proposition 3.6, this proposition can be proved with the same techniques used
in the proof of Proposition 6.4.

###  6.2 Implication of the extended weighted CHSH test

In this subsection, we prove a series of propositions and lemmas derived from
the fact that some strategy can approximate the ideal correlation of the
extended weighted CHSH test, which lead to a key result that will be used in
the self-testing proof in Section 6.4.

We will work with a strategy $\mathbbmtt{S}$ that can approximate
$\mathfrak{C}(d,r)$, which contains the ideal correlation of the extended
weighted CHSH test. About the notation, for
$(x,y)\in\mathcal{X}^{EXT}\times\mathcal{Y}^{EXT}$ and
$(a,b)\in\mathcal{A}_{x}^{EXT}\times\mathcal{B}_{y}^{EXT}$, Alice and Bob’s
projectors are denoted by $M_{x}^{a}$ and $N_{y}^{b}$, as illustrated in
Section 2. Since the two answers for questions $1$ and $2$ are $0$ and $1$, we
denote Alice and Bob’s binary observables for these two questions by
$M_{1},M_{2}$ and $N_{1},N_{2}$ respectively. Note that the observables
$M_{1}\equiv M(a_{1})$ and $M_{2}\equiv M(a_{2})$, where $M(a_{1})$ and
$M(a_{2})$ are used in $LS(r)$, because questions $1$ and $2$ are equivalent
to questions $x(a_{1})$ and $x(a_{2})$ in the full test. Similarly, on Bob’s
side, we have $N_{1}\equiv N(a_{1})$ and $N_{2}\equiv N(a_{2})$. For
simplicity, in this subsection, we use $M_{1},M_{2}$ and $N_{1},N_{2}$ only.

######  Proposition 6.9.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate quantum strategy of
$\mathfrak{C}(d,r)$. Then the strategy $\mathbbmtt{S}$ satisfies the following
relations

$\displaystyle M_{0}^{0}N_{0}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{0}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+2}^{0}+M_{n(r)+2}^{1})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{0}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(N_{n(r)+1}^{0}+N_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(N_{n(r)+2}^{0}+N_{n(r)+2}^{1})|\psi\rangle$
$\displaystyle M_{0}^{2}N_{0}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{0}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{n(r)+1}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{n(r)+2}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{0}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+2}^{2}|\psi\rangle,$

and

$\displaystyle
M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle
M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{1}|\psi\rangle$
$\displaystyle
M_{n(r)+2}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+2}^{0}|\psi\rangle$
$\displaystyle
M_{n(r)+2}^{1}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+2}^{1}|\psi\rangle.$

###### Proof.

We prove
$(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{0}^{0}|\psi\rangle$
as an example. The rest of the relations follow the same line of argument.

Recall that the implication of $\mathbbmtt{S}$ being an $\epsilon$-approximate
strategy is that $P(a,b|x,y)\simeq_{O(r\epsilon)}\tilde{P}(a,b|x,y)$ for each
question pair $(x,y)$ and its associating answer pair $(a,b)$. From the
correlation, we can observe that

$\displaystyle\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})N_{0}^{0}|\psi\rangle$
$\displaystyle=$ $\displaystyle P(0,0|n(r)+1,0)+P(1,0|n(r)+1,0)$
$\displaystyle\geq$ $\displaystyle\frac{2}{d-1}-O(r\epsilon).$

On the other hand, the correlation also tells us that

$\displaystyle\langle\psi|N_{0}^{0}|\psi\rangle=P_{B}(0|0)\simeq_{O(r\epsilon)}\frac{2}{d-1}$
$\displaystyle\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle=P_{A}(0|n(r)+1)+P_{A}(1|n(r)+1)\simeq_{O(r\epsilon)}\frac{2}{d-1},$

The equations above imply that

$\displaystyle\lVert(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle-
N_{0}^{0}|\psi\rangle\rVert^{2}$ $\displaystyle=$
$\displaystyle\langle\psi|N_{0}^{0}|\psi\rangle+\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle-2\langle\psi|N_{0}^{0}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})N_{0}^{0}|\psi\rangle$
$\displaystyle=$ $\displaystyle O(r\epsilon),$

where we used the fact that
$(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})^{2}=M_{n(r)+1}^{0}+M_{n(r)+1}^{1}$. Hence we
can conclude that
$(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{0}^{0}|\psi\rangle$.
∎

######  Proposition 6.10.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. We define

$\displaystyle M_{n(r)+1}=M_{n(r)+1}^{0}-M_{n(r)+1}^{1}$ $\displaystyle
M_{n(r)+2}=M_{n(r)+2}^{0}-M_{n(r)+2}^{1},$ (55) $\displaystyle
N_{n(r)+1}=N_{n(r)+1}^{0}-N_{n(r)+1}^{1}$ $\displaystyle
N_{n(r)+2}=N_{n(r)+2}^{0}-N_{n(r)+2}^{1}.$ (56)

Then,

$\displaystyle\mathbbmtt{S}_{1}=\left(M_{n(r)+1},M_{n(r)+2},N_{1},N_{2},\frac{M_{0}^{0}|\psi\rangle}{\lVert
M_{0}^{0}|\psi\rangle\rVert}\right),$ (57)
$\displaystyle\mathbbmtt{S}_{2}=\left(N_{n(r)+1},N_{n(r)+2},M_{1},M_{2},\frac{M_{0}^{0}|\psi\rangle}{\lVert
M_{0}^{0}|\psi\rangle\rVert}\right).$ (58)

are two $O(d\sqrt{r}\sqrt{\epsilon})$-approximate strategies of the ideal
correlation that achieves $\mathcal{I}_{\cot(-\pi/d)}^{\max}$.

Note that here we only consider $\epsilon$ small enough such that $\lVert
M_{0}^{0}|\psi\rangle\rVert>0$.

###### Proof.

We first prove that $\mathbbmtt{S}_{1}$ is an
$O(d\sqrt{r}\sqrt{\epsilon})$-approximate strategies of
$\mathcal{I}_{\cot(-\pi/d)}^{\max}$. This step requires examining the terms of
the form $\langle\psi|M_{0}^{0}M_{x}^{a}N_{y}^{b}M_{0}^{0}|\psi\rangle$ for
$x=n(r)+1,n(r)+2$, $y=1,2$ and $a,b=0,1$. We find that these terms relate to
$\langle\psi|M_{x}^{a}N_{y}^{b}|\psi\rangle$ by

$\displaystyle\langle\psi|M_{x}^{a}N_{y}^{b}|\psi\rangle$ $\displaystyle=$
$\displaystyle\langle\psi|(M_{0}^{0}+M_{0}^{2})M_{x}^{a}N_{y}^{b}(M_{0}^{0}+M_{0}^{2})|\psi\rangle$
$\displaystyle=$
$\displaystyle\langle\psi|M_{0}^{0}M_{x}^{a}N_{y}^{b}M_{0}^{0}|\psi\rangle+\langle\psi|M_{0}^{0}M_{x}^{a}N_{y}^{b}M_{0}^{2}|\psi\rangle+\langle\psi|M_{0}^{2}M_{x}^{a}N_{y}^{b}M_{0}^{0}|\psi\rangle+\langle\psi|M_{0}^{2}M_{x}^{a}N_{y}^{b}M_{0}^{2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}$
$\displaystyle\langle\psi|M_{0}^{0}M_{x}^{a}N_{y}^{b}M_{0}^{0}|\psi\rangle+\langle\psi|M_{0}^{0}M_{x}^{a}N_{y}^{b}M_{x}^{2}|\psi\rangle+\langle\psi|M_{x}^{2}M_{x}^{a}N_{y}^{b}M_{0}^{0}|\psi\rangle+\langle\psi|M_{x}^{2}M_{x}^{a}N_{y}^{b}M_{x}^{2}|\psi\rangle$
$\displaystyle=$
$\displaystyle\langle\psi|M_{0}^{0}M_{x}^{a}N_{y}^{b}M_{0}^{0}|\psi\rangle,$

where we use the facts that
$M_{0}^{2}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{x}^{2}|\psi\rangle$
and that $M_{x}^{0}M_{x}^{2}=0$ for the relevant values of $(x,y,a,b)$.

To demonstrate the effect of this relation, we use an example. If Alice and
Bob share state $M_{0}^{0}|\psi\rangle/\lVert M_{0}^{0}|\psi\rangle\rVert$ and
apply $M_{n(r)+1}^{0}N_{1}^{0}$, then

$\displaystyle\frac{\langle\psi|M_{0}^{0}M_{n(r)+1}^{0}N_{1}^{0}M_{0}^{0}|\psi\rangle}{\langle\psi|M_{0}^{0}|\psi\rangle}\simeq_{O(d\sqrt{r}\sqrt{\epsilon})}\frac{\langle\psi|M_{n(r)+1}^{0}N_{1}^{0}|\psi\rangle}{\langle\psi|M_{0}^{0}|\psi\rangle}\simeq_{O(dr\epsilon)}\frac{\cos^{2}(-\pi/2d)}{2},$

where the first error term is derived from

$\displaystyle\frac{\lVert\langle\psi|M_{0}^{0}M_{n(r)+1}^{0}N_{1}^{0}M_{0}^{0}|\psi\rangle-\langle\psi|M_{n(r)+1}^{0}N_{1}^{0}|\psi\rangle\rVert}{\langle\psi|M_{0}^{0}|\psi\rangle}\leq\frac{O(\sqrt{r}\sqrt{\epsilon})}{\frac{2}{d-1}-O(r\epsilon)}=O(d\sqrt{r}\sqrt{\epsilon}).$

The rest of the conditional probabilities produced by $\mathbbmtt{S}_{1}$ can
be derived in the same way. Using the fact that $O(d\sqrt{r}\sqrt{\epsilon})$
dominates $O(dr\epsilon)$, we can prove that $\mathbbmtt{S}_{1}$ is an
$O(d\sqrt{r}\sqrt{\epsilon})$-approximate strategy of the ideal correlation
that achieves $\mathcal{I}_{\cot(-\pi/d)}^{\max}$. The proof for
$\mathbbmtt{S}_{2}$ is analogous so we omit it here. ∎

Based on Propositions 6.9 and 6.10, we identify a special sub-normalized state
$|\psi_{1}\rangle$,

$\displaystyle|\psi_{1}\rangle=1/2(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle.$
(59)

The special properties of $|\psi_{1}\rangle$ are summarized in the
propositions below. Based on the properties of $|\psi_{1}\rangle$, we will
prove that $|\psi_{1}\rangle$ can be used to approximate $|\psi\rangle$ in
Lemma 6.15.

######  Proposition 6.11.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$ and $|\psi_{1}\rangle$ be as defined in eq. 59. Then,

$\displaystyle\lVert|\psi_{1}\rangle\rVert^{2}\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{d-1}.$
(60)

###### Proof.

We start by expanding the inner product

$\displaystyle\langle\psi_{1}|\psi_{1}\rangle$ $\displaystyle=$ $\displaystyle
1/4\langle\psi|(M_{n(r)+1}^{0}-iM_{n(r)+1}^{1}M_{n(r)+2}+iM_{n(r)+1}^{0}M_{n(r)+2}+M_{n(r)+1}^{1})$
$\displaystyle(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle=$ $\displaystyle
1/2\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1}-iM_{n(r)+1}^{1}M_{n(r)+2}M_{n(r)+1}^{0}+iM_{n(r)+1}^{0}M_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle$

Here we apply the trick to flip $M_{n(r)+1}^{1}$ and $M_{n(r)+1}^{0}$ to Bob’s
side and get

$\displaystyle\langle\psi|M_{n(r)+1}^{1}M_{n(r)+2}M_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\langle\psi|N_{n(r)+1}^{1}M_{n(r)+2}N_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle=\langle\psi|N_{n(r)+1}^{1}N_{n(r)+1}^{0}M_{n(r)+2}|\psi\rangle=0.$

Similarly, we have
$\langle\psi|M_{n(r)+1}^{0}M_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}0$.
Hence, from the ideal correlation, we get

$\displaystyle\langle\psi_{1}|\psi_{1}\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}1/2\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r\epsilon)}\frac{1}{d-1}.$
(61)

∎

######  Proposition 6.12.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$ and $|\psi_{1}\rangle$ be as defined in eq. 59. Then,

$\displaystyle
N_{1}N_{2}|\psi_{1}\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}|\psi_{1}\rangle.$
(62)

The idea of this proof is to apply the general results in Section 4.1 to the
strategy $\mathbbmtt{S}_{1}$, so in the first half of the proof, we can derive
how $N_{1}$ and $N_{2}$ act on the state $M_{n(r)+1}^{0}|\psi\rangle$ and
$M_{n(r)+1}^{1}|\psi\rangle$. In the second half, we combine
$M_{n(r)+1}^{0}|\psi\rangle$ and $M_{n(r)+1}^{1}|\psi\rangle$ in a way and
show that it is an eigenvector of $N_{1}N_{2}$. It turns out that this
combination of $M_{n(r)+1}^{0}|\psi\rangle$ and $M_{n(r)+1}^{1}|\psi\rangle$
is closely related to $|\psi_{1}\rangle$. We show all the calculations to make
the proof easier to read.

###### Proof.

Following the convention in Section 4.1, we define

$\displaystyle c:=\cos(\frac{\pi}{d})$ $\displaystyle s:=\sin(\frac{\pi}{d})$
$\displaystyle Z_{A}:=M_{n(r)+1}$ $\displaystyle X_{A}:=M_{n(r)+2}$
$\displaystyle Z_{B}:=\frac{N_{1}+N_{2}}{2c}$ $\displaystyle
X_{B}:=\frac{N_{1}-N_{2}}{-2s}.$

In the first step, we will show how $(N_{1}+N_{2})/2c$, or $Z_{B}$, acts on
$M_{n(r)+1}^{0}|\psi\rangle$ and $M_{n(r)+1}^{1}|\psi\rangle$. Recall that
Theorem 4.1 applies to all approximating strategies pf
$\mathcal{I}_{-\cot(\pi/d)}^{\max}$, so we can substitute appropriate
operators and the shared state into eq. 26 to see that

$\displaystyle\lVert Z_{B}M_{0}^{0}|\psi\rangle-
Z_{A}M_{0}^{0}|\psi\rangle\rVert\leq\sqrt{s}\lVert M_{0}^{0}|\psi\rangle\rVert
O(\sqrt{d}r^{1/4}\epsilon^{1/4})=O(r^{1/4}\epsilon^{1/4}/\sqrt{d}).$

Since
$M_{0}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$,
the equation above can be rewritten as

$\displaystyle
Z_{B}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(M_{n(r)+1}^{0}-M_{n(r)+1}^{1})|\psi\rangle,$

where we use the fact that $Z_{A}=M_{n(r)+1}^{0}-M_{n(r)+1}^{1}$. Using the
fact $M_{n(r)+1}^{0}M_{n(r)+1}^{1}=0$, we can further deduce that

$\displaystyle O(\sqrt{r}\sqrt{\epsilon}/d)\geq$ $\displaystyle\lVert
Z_{B}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle-(M_{n(r)+1}^{0}-M_{n(r)+1}^{1})|\psi\rangle\rVert^{2}$
$\displaystyle=$ $\displaystyle\lVert Z_{B}M_{n(r)+1}^{0}|\psi\rangle-
M_{n(r)+1}^{0}|\psi\rangle\rVert^{2}+\lVert
Z_{B}M_{n(r)+1}^{1}|\psi\rangle+M_{n(r)+1}^{1}|\psi\rangle\rVert^{2},$

which immediately gives us that

$\displaystyle\frac{N_{1}+N_{2}}{2c}M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}M_{n(r)+1}^{0}|\psi\rangle,$
(63)
$\displaystyle\frac{N_{1}+N_{2}}{2c}M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-M_{n(r)+1}^{1}|\psi\rangle.$
(64)

Next, we study how $X_{B}=(N_{1}-N_{2})/(-2s)$ acts on
$M_{n(r)+1}^{0}|\psi\rangle$ and $M_{n(r)+1}^{1}|\psi\rangle$. Substituting
the appropriate operators and the shared state into eqs. 29 and 28, we get

$\displaystyle\frac{N_{1}-N_{2}}{-2s}M_{n(r)+1}^{0}M_{0}^{0}|\psi\rangle\simeq_{(\lVert
M_{0}^{0}|\psi\rangle\rVert/\sqrt{s})\;O(\sqrt{d}r^{1/4}\epsilon^{1/4})}M_{n(r)+2}M_{n(r)+1}^{1}M_{0}^{0}|\psi\rangle$
$\displaystyle\frac{N_{1}-N_{2}}{-2s}M_{n(r)+1}^{1}M_{0}^{0}|\psi\rangle\simeq_{(\lVert
M_{0}^{0}|\psi\rangle\rVert/\sqrt{s})\;O(\sqrt{d}r^{1/4}\epsilon^{1/4})}M_{n(r)+2}M_{n(r)+1}^{0}M_{0}^{0}|\psi\rangle.$

Using the facts that
$M_{0}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$
and $O(\sqrt{d}r^{1/4}\epsilon^{1/4})$ dominates $O(\sqrt{r}\sqrt{\epsilon})$,
we can simplify the equations above to get

$\displaystyle(N_{1}-N_{2})M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-2sM_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle,$
(65)
$\displaystyle(N_{1}-N_{2})M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-2sM_{n(r)+2}M_{n(r)+1}^{0}|\psi\rangle.$
(66)

In summary, we can rearrange terms in eqs. 63, 64, 65 and 66 to get

$\displaystyle
N_{1}M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}cM_{n(r)+1}^{0}|\psi\rangle-
sM_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle,$ $\displaystyle
N_{1}M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-cM_{n(r)+1}^{1}|\psi\rangle-
sM_{n(r)+2}M_{n(r)+1}^{0}|\psi\rangle,$ $\displaystyle
N_{2}M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}cM_{n(r)+1}^{0}|\psi\rangle+sM_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle,$
$\displaystyle
N_{2}M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-cM_{n(r)+1}^{1}|\psi\rangle+sM_{n(r)+2}M_{n(r)+1}^{0}|\psi\rangle.$

Then we can expand $N_{1}N_{2}M_{n(r)+1}^{0}|\psi\rangle$ by first substitute
in the approximate expression of $N_{2}M_{n(r)+1}^{0}|\psi\rangle$ and
repeatedly substitute in the four equations above to get that

$\displaystyle\quad N_{1}N_{2}M_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(cN_{1}M_{n(r)+1}^{0}+sM_{n(r)+2}N_{1}M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(c^{2}M_{n(r)+1}^{0}-csM_{n(r)+2}M_{n(r)+1}^{1}-csM_{n(r)+2}M_{n(r)+1}^{1}-s^{2}M_{n(r)+2}^{2}M_{n(r)+1}^{0})|\psi\rangle$
$\displaystyle=(\cos(\frac{2\pi}{d})M_{n(r)+1}^{0}-\sin(\frac{2\pi}{d})M_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle.$

Following similar steps, we can get that

$\displaystyle\quad N_{1}N_{2}M_{n(r)+1}^{1}|\psi\rangle$
$\displaystyle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(-cN_{1}M_{n(r)+1}^{1}+sM_{n(r)+2}N_{1}M_{n(r)+1}^{0})|\psi\rangle$
$\displaystyle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(c^{2}M_{n(r)+1}^{1}+csM_{n(r)+2}M_{n(r)+1}^{0}+csM_{n(r)+2}M_{n(r)+1}^{0}-s^{2}M_{n(r)+2}^{2}M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle=(\cos(\frac{2\pi}{d})M_{n(r)+1}^{1}+\sin(\frac{2\pi}{d})M_{n(r)+2}M_{n(r)+1}^{0})|\psi\rangle.$

Multiplying $M_{n(r)+2}$ to the approximate expression of
$N_{1}N_{2}M_{n(r)+1}^{1}|\psi\rangle$, we can get that

$\displaystyle
N_{1}N_{2}M_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\sin(\frac{2\pi}{d})M_{n(r)+1}^{0}|\psi\rangle+\cos(\frac{2\pi}{d})M_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle,$

where we use the fact that

$\displaystyle(M_{n(r)+2})^{2}M_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle=(M_{n(r)+2}^{0}+M_{n(r)+2}^{1})M_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{0}M_{0}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{0}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})M_{n(r)+1}^{0}|\psi\rangle$
$\displaystyle=M_{n(r)+1}^{0}|\psi\rangle.$

Combining the approximate expressions of
$N_{1}N_{2}M_{n(r)+1}^{0}|\psi\rangle$ and
$N_{1}N_{2}M_{n(r)+2}M_{n(r)+1}^{0}|\psi\rangle$ gives us that

$\displaystyle
N_{1}N_{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle.$
(67)

In the last step, we prove $|\psi_{1}\rangle$ can be approximated by

$\displaystyle|\psi_{1}\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}1/2(\mathbb{1}-iM_{n(r)+2})(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle.$

The central step of proving the approximation above is to prove
$(M_{n(r)+2})^{2}M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{n(r)+1}^{0}|\psi\rangle$,
which is proved in the previous paragraph. So we multiply eq. 67 on both sides
by $1/2(\mathbb{1}-iM_{n(r)+2})$ and get

$\displaystyle
N_{1}N_{2}|\psi_{1}\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}|\psi_{1}\rangle.$
(68)

∎

######  Proposition 6.13.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$ and $|\psi_{1}\rangle$ be as defined in eq. 59. Then,

$\displaystyle
M_{1}M_{2}|\psi_{1}\rangle\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}\omega_{d}^{-1}|\psi_{1}\rangle.$
(69)

This proof is similar to the proof of Proposition 6.12 but with one extra
step. We first prove that there exists a state $|\psi_{2}\rangle$ that is
close to $|\psi_{1}\rangle$, then we show $|\psi_{2}\rangle$ is close to an
eigenstate of $M_{1}M_{2}$. In the last step, we show that $|\psi_{1}\rangle$
is also close to an eigenstate of $M_{1}M_{2}$.

###### Proof.

In this proof, we still use the notation $c:=\cos(\pi/d)$ and
$s:=\sin(\pi/d)$. We first introduce an approximation of $|\psi_{1}\rangle$,

$\displaystyle|\psi_{2}\rangle=1/2(N_{n(r)+1}^{0}-iN_{n(r)+2}N_{n(r)+1}^{1}+iN_{n(r)+2}N_{n(r)+1}^{0}+N_{n(r)+1}^{1})|\psi\rangle,$
(70)

and we will show that

$\displaystyle|\psi_{1}\rangle\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}|\psi_{2}\rangle.$
(71)

To prove eq. 71, we compare each term of $|\psi_{1}\rangle$ with
$|\psi_{2}\rangle$. Recall that
$M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{0}|\psi\rangle$
and
$M_{n(r)+1}^{1}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}N_{n(r)+1}^{1}|\psi\rangle$
from Proposition 6.9, then

$\displaystyle|\psi_{2}\rangle-|\psi_{1}\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(-N_{n(r)+2}N_{n(r)+1}^{1}+N_{n(r)+2}N_{n(r)+1}^{0})|\psi\rangle-(M_{n(r)+2}M_{n(r)+1}^{1}-M_{n(r)+2}M_{n(r)+1}^{0})|\psi\rangle.$

Therefore, proving eq. 71 is reduced to proving
$(M_{n(r)+2}M_{n(r)+1}^{1}-M_{n(r)+2}M_{n(r)+1}^{0})|\psi\rangle$ is close to
$(-N_{n(r)+2}N_{n(r)+1}^{1}+N_{n(r)+2}N_{n(r)+1}^{0})|\psi\rangle$, At this
point, we can substitute appropriate operators and the shared state of
$\mathbbmtt{S}_{1}$ into the anti-commutation relation (eq. 30) and see that

$\displaystyle M_{n(r)+1}M_{n(r)+2}M_{0}^{0}|\psi\rangle\simeq_{\frac{\lVert
M_{0}^{0}|\psi\rangle\rVert}{c\sqrt{s}}O(\sqrt{d}r^{1/4}\epsilon^{1/4})}-M_{n(r)+1}M_{n(r)+2}M_{0}^{0}|\psi\rangle.$

Using the fact $c=1-\pi^{2}/(2d^{2})+O(1/d^{4})$ and $s=\pi/d+O(1/d^{3})$, the
error term above is of order $O(\sqrt{d}r^{1/4}\epsilon^{1/4})$. Then we can
show that

$\displaystyle M_{n(r)+2}M_{n(r)+1}|\psi\rangle$
$\displaystyle=M_{n(r)+2}M_{n(r)+1}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1}+M_{n(r)+1}^{2})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{n(r)+2}M_{n(r)+1}M_{0}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}-M_{n(r)+1}M_{n(r)+2}M_{0}^{0}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}-M_{n(r)+1}M_{n(r)+2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}-M_{n(r)+1}N_{n(r)+2}|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}-N_{n(r)+2}N_{n(r)+1}|\psi\rangle,$

where we use the fact that
$M_{0}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(M_{n(r)+2}^{0}+M_{n(r)+2}^{1})|\psi\rangle$.

Next, we show that
$M_{1}M_{2}|\psi_{2}\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{-1}|\psi_{2}\rangle$,
which gives us eq. 79 after substituting in eq. 71. With similar derivation as
in the proof of Proposition 6.12, we can apply results from Section 4.1 to the
strategy $\mathbbmtt{S}_{2}$ to get that

$\displaystyle(M_{1}+M_{2})N_{n(r)+1}^{0}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}2cN_{n(r)+1}^{0}|\psi\rangle.$
(72)
$\displaystyle(M_{1}+M_{2})N_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-2cN_{n(r)+1}^{1}|\psi\rangle,$
(73)
$\displaystyle(M_{1}-M_{2})N_{n(r)+1}^{0}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-2sN_{n(r)+2}N_{n(r)+1}^{1}|\psi\rangle$
(74)
$\displaystyle(M_{1}-M_{2})N_{n(r)+1}^{1}|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}-2sN_{n(r)+2}N_{n(r)+1}^{0}|\psi\rangle.$
(75)

So we can further deduce that

$\displaystyle
M_{1}M_{2}(N_{n(r)+1}^{0}-iN_{n(r)+2}N_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{-1}(N_{n(r)+1}^{0}-iN_{n(r)+2}N_{n(r)+1}^{1})|\psi\rangle.$
(76)

It can be shown that
$|\psi_{2}\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}1/2(\mathbb{1}+iN_{n(r)+2})(N_{n(r)+1}^{0}-iN_{n(r)+2}N_{n(r)+1}^{1})|\psi\rangle$.
Proving this approximation of $|\psi_{1}\rangle$ uses the same techniques as
in the proof of Proposition 6.12, so we omit it here.

We multiply both sides of eq. 76 by $1/2(\mathbb{1}+iN_{n(r)+2})$ and get that

$\displaystyle
M_{1}M_{2}|\psi_{2}\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{-1}|\psi_{2}\rangle.$
(77)

In the end, the relation
$|\psi_{1}\rangle\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}|\psi_{2}\rangle$
implies that

$\displaystyle
M_{1}M_{2}|\psi_{1}\rangle\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}\omega_{d}^{-1}|\psi_{1}\rangle.$
(78)

∎

The effects of $M_{1},M_{2}$ and $N_{1},N_{2}$ acting on $|\psi_{1}\rangle$
are summarized in the next proposition.

######  Proposition 6.14.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$ and $|\psi_{1}\rangle$ be as defined in eq. 59. Then,

$\displaystyle
M_{1}|\psi_{1}\rangle\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}\omega_{d}M_{2}|\psi_{1}\rangle,$
(79) $\displaystyle
N_{1}|\psi_{1}\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{-1}N_{2}|\psi_{1}\rangle.$
(80)

###### Proof.

From the proof of Proposition 6.12, we know

$\displaystyle
N_{1}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(c-si)M_{n(r)+1}^{0}|\psi\rangle-(ci+s)M_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle,$
$\displaystyle
N_{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(c+si)M_{n(r)+1}^{0}|\psi\rangle+(s-ci)M_{n(r)+2}M_{n(r)+1}^{1}|\psi\rangle,$

so

$\displaystyle
N_{1}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{-1}N_{2}(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})|\psi\rangle,$

which gives us the second approximation relation of the proposition.

For the first approximation relation, we follow the proof of Proposition 6.13
and examine the effect of $M_{1}$ and $M_{2}$ on $|\psi_{2}\rangle$. In
particular, we know

$\displaystyle
M_{1}(N_{n(r)+1}^{0}-iN_{n(r)+2}N_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(c+si)N_{n(r)+1}^{0}|\psi\rangle+(ci-s)N_{n(r)+2}N_{n(r)+1}^{1}|\psi\rangle$
$\displaystyle
M_{2}(N_{n(r)+1}^{0}-iN_{n(r)+2}N_{n(r)+1}^{1})|\psi\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}(c-si)N_{n(r)+1}^{0}|\psi\rangle+(ci+s)N_{n(r)+2}N_{n(r)+1}^{1}|\psi\rangle.$

So we know
$M_{1}|\psi_{2}\rangle\simeq_{O(r^{1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}M_{2}|\psi_{2}\rangle$.
Lastly, using eq. 71, we get the first approximation relation. ∎

Next lemma is the major result of this subsection, which gives us a
decomposition of $|\psi\rangle$. Before proving the next lemma, we make one
important observation. Recall that Proposition 6.2 establishes that there
exist observables $\\{M(s),N(s)\\}$ such that
$M(s)N(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|\psi\rangle$ for
$s\in S$. Then we can deduce that

$\displaystyle M(a_{4})M(a_{3})\otimes
N(a_{4})N(a_{3})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(a_{4})\otimes
N(a_{4})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|\psi\rangle,$

or equivalently,

$\displaystyle U_{A}^{\dagger}\otimes
U_{B}^{\dagger}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}|\psi\rangle.$

Intuitively, it means that $|\psi\rangle$ is invariant under the permutation
induced by $U_{A}^{\dagger}\otimes U_{B}^{\dagger}$. We use this observation
in the proof of the following lemma.

######  Lemma 6.15.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$ and define
$|\psi^{\prime}\rangle:=\sum_{j=1}^{(d-1)}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle$
with $\log_{r}j$ being the discrete log and $|\psi_{1}\rangle$ as defined in
eq. 59. Then,

$\displaystyle|\psi\rangle\simeq_{O(dr^{d/2}\epsilon^{1/8})}|\psi^{\prime}\rangle.$
(81)

###### Proof.

The proof takes two steps. In the first step, we show that the norm of
$|\psi^{\prime}\rangle$ is close to $1$. In the second step, we show that
$\langle\psi|\psi^{\prime}\rangle$ is close to $1$.

Expanding $\langle\psi^{\prime}|\psi^{\prime}\rangle$, we get

$\displaystyle\langle\psi^{\prime}|\psi^{\prime}\rangle=\sum_{j=1}^{d-1}\langle\psi_{1}|(U_{A}U_{B})^{\log_{r}j}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle+\sum_{j\neq
j^{\prime}}\langle\psi_{1}|(U_{A}U_{B})^{\log_{r}j}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j^{\prime}}|\psi_{1}\rangle.$

Observe that

$\displaystyle\langle\psi_{1}|(U_{A}U_{B})^{\log_{r}j}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle=\langle\psi_{1}|\psi_{1}\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{d-1},$

so we need to show when $j\neq j^{\prime}$, the inner product
$\langle\psi_{1}|(U_{A}U_{B})^{\log_{r}j}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j^{\prime}}|\psi_{1}\rangle$
is close to $0$. Using the relation
$O_{B}(U_{B}^{\dagger})^{j}|\psi\rangle\simeq_{O(r^{j+1/2}\sqrt{\epsilon})}(U_{B}^{\dagger})^{j}O_{B}^{r^{j}}|\psi\rangle$
and eq. 62, we can deduce that

$\displaystyle O_{B}(U_{B}^{\dagger})^{j}|\psi_{1}\rangle$
$\displaystyle=\frac{1}{2}(\mathbb{1}-iM_{n(r)+2})(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})O_{B}(U_{B}^{\dagger})^{j}|\psi\rangle$
$\displaystyle\simeq_{O(r^{j+1/2}\sqrt{\epsilon})}\frac{1}{2}(\mathbb{1}-iM_{n(r)+2})(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1})(U_{B}^{\dagger})^{j}O_{B}^{r^{j}}|\psi\rangle$
$\displaystyle=(U_{B}^{\dagger})^{j}O_{B}^{r^{j}}|\psi_{1}\rangle$
$\displaystyle\simeq_{O(r^{j+1/4}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{r^{j}}(U_{B}^{\dagger})^{j}|\psi_{1}\rangle$

In short, we have shown that

$\displaystyle
O_{B}(U_{B}^{\dagger})^{j}|\psi_{1}\rangle\simeq_{O(r^{j}\epsilon^{1/4}/\sqrt{d})}\omega_{d}^{r^{j}}(U_{B}^{\dagger})^{j}|\psi_{1}\rangle,$
(82)

where we drop the insignificant error term $r^{1/4}$. With similar derivation,
we can also get

$\displaystyle
O_{A}(U_{A}^{\dagger})^{j}|\psi_{1}\rangle\simeq_{O(\sqrt{d}r^{j}\epsilon^{1/4})}\omega_{d}^{-r^{j}}(U_{A}^{\dagger})^{j}|\psi_{1}\rangle,$
(83)

which will be used in Section 6.4. Hence for $j\neq j^{\prime}$,
$(U_{A}^{\dagger}U_{B}^{\dagger})^{j}|\psi_{1}\rangle$ and
$(U_{A}^{\dagger}U_{B}^{\dagger})^{j^{\prime}}|\psi_{1}\rangle$ are close to
eigenvectors of the unitary $O_{B}$ with different eigenvalues. Applying
Proposition 2.14 to eq. 82 gives us that

$\displaystyle\langle\psi_{1}|(U_{A}U_{B})^{j}(U_{A}^{\dagger}U_{B}^{\dagger})^{j^{\prime}}|\psi_{1}\rangle\simeq_{O((r^{j}+r^{j^{\prime}})\epsilon^{1/4})}0,$

where we use the fact that $\lVert
1-\omega_{d}^{r^{j^{\prime}}-r^{j}}\rVert=O(1/d)$. Therefore, we can calculate
the norm of $|\psi^{\prime}\rangle$

$\displaystyle\langle\psi^{\prime}|\psi^{\prime}\rangle$
$\displaystyle=\sum_{j,j^{\prime}=1}^{d-1}\langle\psi_{1}|(U_{A}U_{B})^{\log_{r}j}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j^{\prime}}|\psi_{1}\rangle$
$\displaystyle\simeq_{O(dr^{d}\epsilon^{1/4})}\sum_{j=1}^{d-1}\langle\psi_{1}|(U_{A}U_{B})^{\log_{r}j}(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle$
$\displaystyle\simeq_{O(dr\sqrt{\epsilon})}(d-1)\frac{1}{d-1}=1.$

Next we calculate $\langle\psi|\psi^{\prime}\rangle$ which is

$\displaystyle\langle\psi|\psi^{\prime}\rangle=\sum_{j=1}^{d-1}\langle\psi|(U_{A}^{\dagger}U_{B}^{\dagger})^{\log_{r}j}|\psi_{1}\rangle\simeq_{O(d^{2}\sqrt{r}\sqrt{\epsilon})}(d-1)\langle\psi|\psi_{1}\rangle.$

The problem is reduced to calculate $\langle\psi|\psi_{1}\rangle$, which is

$\displaystyle\langle\psi|\psi_{1}\rangle$
$\displaystyle=\frac{1}{2}\langle\psi|(M_{n(r)+1}^{0}+iM_{n(r)+2}M_{n(r)+1}^{1}-iM_{n(r)+2}M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle$
$\displaystyle=\frac{1}{2}\left(\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle-i\langle\psi|M_{n(r)+2}M_{n(r)+1}|\psi\rangle\right)$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}\frac{1}{2}\left(\langle\psi|(M_{n(r)+1}^{0}+M_{n(r)+1}^{1})|\psi\rangle-i\langle\psi|N_{n(r)+2}M_{n(r)+1}|\psi\rangle\right)$
$\displaystyle\simeq_{O(r\epsilon)}\frac{1}{2}\frac{2}{d-1}=\frac{1}{d-1},$

where the approximation of $\langle\psi|N_{n(r)+2}M_{n(r)+1}|\psi\rangle$
comes from the correlation. Hence, we know
$\langle\psi|\psi^{\prime}\rangle\simeq_{O(d^{2}\sqrt{r}\sqrt{\epsilon})}1$.

In the end, we combine
$\langle\psi|\psi^{\prime}\rangle\simeq_{O(d^{2}\sqrt{r}\sqrt{\epsilon})}1$
and $\lVert|\psi^{\prime}\rangle\rVert^{2}\simeq_{O(dr^{d}\epsilon^{1/4})}1$,
and apply Proposition 2.15 to conclude

$\displaystyle|\psi\rangle\simeq_{O(dr^{d/2}\epsilon^{1/8})}|\psi^{\prime}\rangle.$

∎

###  6.3 Implications of passing the commutation games

The commutation game is introduced to certify some observables used in $LS(r)$
commute with the operators for the extended weighted CHSH test. For the
details of the general commutation test, we refer to Appendix A.$2$ of
[CGJV19]. We use similar techniques in our proof but our proof also bases on
the correlation given in Table 3.

The implication of winning the commutation game is summarized in the following
proposition.

######  Proposition 6.16.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then,

$\displaystyle
M_{n(r)+1}^{0}M(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(s)M_{n(r)+1}^{0}|\psi\rangle,$
(84) $\displaystyle
M_{n(r)+1}^{1}M(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(s)M_{n(r)+1}^{1}|\psi\rangle,$
(85) $\displaystyle
M_{n(r)+2}M(s)|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(s)M_{n(r)+2}|\psi\rangle,$
(86)

for $s=f_{0},f_{2},g_{0},g_{2}$.

Note that the $M(s)$’s for $s=f_{0},f_{2},g_{0},g_{2}$ tested in the
commutation game are measured for the Magic Square equations in $LS(r)$. They
will be used to construct the isometry in the next subsection.

###### Proof.

Proving eq. 86 is an application of Lemma $28$ of [CGJV19] with
$\sqrt{\epsilon}$ replaced by $O(\sqrt{r}\sqrt{\epsilon})$.

For the other relations, we prove
$M_{n(r)+1}^{0}M(f_{0})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{0})M_{n(r)+1}^{0}|\psi\rangle$
to demonstrate the techniques involved.

We denote Bob’s projectors by $\\{N_{(n(r)+1,f_{0})}^{b_{1}b_{2}}\\}$ where
$b_{1}\in\mathbb{Z}_{3}$ and $b_{2}\in\mathbb{Z}_{2}$. From the correlation in
Table 3, we can get that

$\displaystyle
M_{n(r)+1}^{0}|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(N_{(n(r)+1,f_{0})}^{00}+N_{(n(r)+1,f_{0})}^{01})|\psi\rangle$
$\displaystyle
M(f_{0})|\psi\rangle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(\sum_{b_{1},b_{2}}(-1)^{b_{2}}N_{(n(r)+1,f_{0})}^{b_{1}b_{2}})|\psi\rangle.$

Then we can show that

$\displaystyle M_{n(r)+1}^{0}M(f_{0})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M_{n(r)+1}^{0}(\sum_{b_{1},b_{2}}(-1)^{b_{2}}N_{(n(r)+1,f_{0})}^{b_{1}b_{2}})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(\sum_{b_{1},b_{2}}(-1)^{b_{2}}N_{(n(r)+1,f_{0})}^{b_{1}b_{2}})(N_{(n(r)+1,f_{0})}^{00}+N_{(n(r)+1,f_{0})}^{01})|\psi\rangle$
$\displaystyle=(N_{(n(r)+1,f_{0})}^{00}+N_{(n(r)+1,f_{0})}^{01})(\sum_{b_{1},b_{2}}(-1)^{b_{2}}N_{(n(r)+1,f_{0})}^{b_{1}b_{2}})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}(N_{(n(r)+1,f_{0})}^{00}+N_{(n(r)+1,f_{0})}^{01})M_{r+6}|\psi\rangle$
$\displaystyle=M(f_{0})(N_{(n(r)+1,f_{0})}^{00}+N_{(n(r)+1,f_{0})}^{01})|\psi\rangle$
$\displaystyle\simeq_{O(\sqrt{r}\sqrt{\epsilon})}M(f_{0})M_{n(r)+1}^{0}|\psi\rangle.$

∎

###  6.4 Robust self-testing

Based on the propositions and lemmas proved so far, we can prove the self-
testing theorem.

######  Theorem 6.17.

Let $\mathbbmtt{S}$ be an $\epsilon$-approximate strategy of
$\mathfrak{C}(d,r)$. Then there exists an isometry
$\Phi_{A}\otimes\Phi_{B}=(\Phi_{A,2}\otimes\Phi_{B,2})(\Phi_{A,1}\otimes\Phi_{B,1})$
and a state $|junk\rangle$ such that
$\lVert|junk\rangle\rVert\simeq_{O(\sqrt{d}r^{1/4}\epsilon^{1/4})}1$ and

$\displaystyle\Phi_{A}\otimes\Phi_{B}(|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes|\tilde{\psi}\rangle$ (87)
$\displaystyle\Phi_{A}\otimes\Phi_{B}(O_{A}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}\omega_{d}^{d-j}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
(88)
$\displaystyle\Phi_{A}\otimes\Phi_{B}(O_{B}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}\omega_{d}^{j}|x_{d-j}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
(89)
$\displaystyle\Phi_{A}\otimes\Phi_{B}(U_{A}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{(d-j)r^{-1}}\rangle_{A^{\prime}}|x_{j}\rangle_{B^{\prime}}$
(90)
$\displaystyle\Phi_{A}\otimes\Phi_{B}(U_{B}|\psi\rangle)\simeq_{O(d^{5/2}r^{d}\epsilon^{1/8}))}|junk\rangle\otimes|EPR\rangle^{\otimes
2}\otimes\frac{1}{\sqrt{d-1}}\sum_{j=1}^{d-1}|x_{d-j}\rangle_{A^{\prime}}|x_{jr^{-1}}\rangle_{B^{\prime}}.$
(91)

The state $|\tilde{\psi}\rangle$ is defined in eq. 40.

Before proving Theorem 6.17, we state the consequence of it. It implies that,
for any odd prime number $d$ whose primitive root is $r$, there exists a
correlation of size $\Theta(r)$ that can robustly self-test the maximally
entangled state of local dimension $4(d-1)$. Since there are infinitely many
prime numbers whose smallest primitive roots are in the set $\\{2,3,5\\}$
[Mur88], we can apply Theorem 6.17 to the set $D$ of all such odd prime
numbers and prove the following theorem.

######  Theorem 6.18.

There exists an infinity-sized set $D$ of prime numbers such that for each
$d\in D$, there exists a constant-sized correlation that can self-test the
maximally entangled state of local dimension $4(d-1)$.

Before proving Theorem 6.17, we introduce the isometry
$\Phi_{A}\otimes\Phi_{B}$, which has two steps. We denote the isometry used in
the first step and the second step by $\Phi_{A,1}\otimes\Phi_{B,1}$ and
$\Phi_{A,2}\otimes\Phi_{B,2}$ respectively, which are illustrated in the two
figures below.

To construct the isometry $\Phi_{A,1}\otimes\Phi_{B,1}$, we use $U_{A},O_{A}$
and $U_{B}$, $O_{B}$ defined in eqs. 51 and 52 to produce a copy of
$|\Sigma^{(d-1)}\rangle$.

To construct the isometry $\Phi_{A,2}\otimes\Phi_{B,2}$. we use the
observables $M(f_{0}),M(f_{2}),M(g_{0}),M(g_{2})$ and
$N(f_{0}),N(f_{2}),N(g_{0}),N(g_{2})$ to produce two copies of $|EPR\rangle$.