For the $O=\top$ component, the conditional states produced by $\fR{\A\B}{\E}$ and $\fI{\E}$ are $\hBrho_{\tM CRB_T\tE}(\mval,0)$ and $\hBrho_{\tM CRB_T\tE}(0^n,0)$ respectively, where the latter can be understood by again using Fact <ref> to swap the values on the $C_1$ and $U_1$ registers.

the distance between the states from $\fR{\A\B}{\E}$ and $\fI{\E}$ at this point is

\begin{align*}
&p_\top \norm{\hBrho_{\tM CRB_T\tE}(\mval,0) - \state{\mval}_{\tM} \otimes \hBrho_{CRB_T\tE}(0^n,0)}_1 \\
\leq& p_\top \norm{\hBrho_{\tM CRB_T\tE}(\mval,0) - \state{\mval}_{\tM} \otimes \hBrho_{CRB_T\tE}(\mval,0)}_1 \\
&\quad + p_\top \norm{\state{\mval}_{\tM} \otimes \hBrho_{CRB_T\tE}(\mval,0) - \state{\mval}_{\tM} \otimes \hBrho_{CRB_T\tE}(0^n,0)}_1.
\end{align*}

By Lemma <ref>, the second term is bounded by $2\lCI$. As for the first term, we have

\begin{align*}
&p_\top\norm{\hBrho_{\tM CRB_T\tE}(\mval,0) - \state{\mval}_{\tM} \otimes \hBrho_{CRB_T\tE}(\mval,0)}_1\\
\leq& p_\top\sum_{\widetilde{m}} \Pr[\tM=\widetilde{m}] \norm{\state{\widetilde{m}}_{\tM} \otimes \hBrho_{CRB_T\tE|\tM=\widetilde{m}}(\mval,0) - \state{\mval}_{\tM} \otimes \hBrho_{CRB_T\tE|\tM=\widetilde{m}}(\mval,0)}_1\\
\leq& p_\top\sum_{\widetilde{m}\neq \mval} 2\Pr[\tM=\widetilde{m}] \leq {2\lEC},
\end{align*}

applying Lemma <ref> in the last line. Adding the two bounds, we arrive at a final bound of $2\lCI + 2\lEC$.

* If $D=1$, the simulator's internal versions of Alice and Bob proceed with the ECD protocol: the simulator releases $y'_{\overline{T}}$ and $b'_{\overline{T}}$, then sets $U_1=0^n \oplus h(k^\A) \oplus u_1 $ and finally releases $R$ at the outer interface.

Through this process, the distinguisher receives $(D,y'_{\overline{T}})$ (at $t_3$), then $b'_{\overline{T}}$ followed by $F$ (at $t_4$), and finally $R\tM$ (at $t_5$).
The distinguisher supplies no inputs, so we can suppose without loss of generality that it applies no operations on its systems through this process, and we only need to bound the distinguishability after $R\tM$ is released. Also, $D$ is trivial since the distinguisher chose it, and so is $\tM$ since here it is always set to $0^n$, so we shall ignore these registers.

We note that the conditional states for the $O=\perp$ component at this point are perfectly indistinguishable, because in that component
all the registers are independent of the message (possibly by being set to “blank” values).
Also, for the $F=\text{\cmark}$ component the conditional states produced by $\fR{\A}{\B\E}$ and $\fI{\B\E}$ are $\sigma_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(\mval,1)$ and $\sigma_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(0^n,1)$ respectively, where the latter can be understood by again using Fact <ref> to swap the values on the $C_1$ and $U_1$ registers.

Overall, the states produced by $\fR{\A\B}{\E}$ and $\fI{\E}$ at this point are respectively of the form

\begin{align*}
&(1-p_\top) \state{\perp}_O \otimes \omega_{FRCY'_{\overline{T}} B'_{\overline{T}} B_T\tE} + p_\top \Frho_{FRCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(\mval,1),\\
&(1-p_\top) \state{\perp}_O \otimes \omega_{FRCY'_{\overline{T}} B'_{\overline{T}} B_T\tE} + p_\top \state{\text{\cmark}}_F \otimes \Frho_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(0^n,1),
\end{align*}

where $\omega$ is an appropriate conditional state (as argued above, it is the same in both scenarios), and

\begin{align*}
\Frho_{FRCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(\mval,1) & = (1-p_{\text{\cmark}|\top}) \state{\text{\xmark}}_F \otimes \psi_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(\mval,1) \\
& \quad + p_{\text{\cmark}|\top} \state{\text{\cmark}}_F \otimes \sigma_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(\mval,1),\\
\state{\text{\cmark}}_F \otimes \Frho_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(0^n,1) & = \state{\text{\cmark}}_F \otimes \left( (1-p_{\text{\cmark}|\top}) \psi_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(0^n,1) \right. \\
& \quad \left. + p_{\text{\cmark}|\top} \sigma_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(0^n,1) \right).
\end{align*}

where $\psi$ are appropriate conditional states, and $p_{\text{\cmark}|\top}$ is the same in both scenarios (by Lemma <ref>). The $\ell_1$ distance between the two expressions is bounded by

\begin{align*}
2p_\top (1-p_{\text{\cmark}|\top}) + p_\top p_{\text{\cmark}|\top} \norm{\sigma_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(\mval,1) - \sigma_{RCY'_{\overline{T}} B'_{\overline{T}} B_T\tE}(0^n,1)}_1 \leq 2\lcom + 2\lCI,
\end{align*}

where we have applied Lemmas <ref> and <ref> (for the latter we use the fact that $\tB$ can contain a copy of $Y'_{\overline{T}} B'_{\overline{T}}$, and apply Fact <ref>).

§.§ Honest Bob and Eve

In this case there are no dishonest parties, so the simulator is trivial and our task is simply to bound the distinguishability between $\fR{\A\B\E}{}$ and $\fideal$.

* We first consider the situation up until $D$ is supplied.

Through this process, the distinguisher releases $O$, then supplies $M$ and $D$.
When $O$ is released, the states produced by $\fR{\A\B\E}{}$ and $\fideal$ are $(1-p_\top) \state{\perp}_O + p_\top \state{\top}_O$ and $\state{\top}_O$ respectively, where $p_\top$ is computed with respect to the honest behaviour in the ECD protocol. Then Lemma <ref> implies the $\ell_1$ distance between them is bounded by

\begin{align*}
2(1-p_\top) \leq 2\lcom.
\end{align*}

After that, $\fR{\A\B\E}{}$ and $\fideal$ do not release any outputs during the steps described here, hence the distance between the states cannot increase.

* If $D=0$:

The distinguisher receives $D$ followed by $\tM$. (There is no $F$ output for $D=0$.) $D$ is trivial since the distinguisher chose it, so we only need to bound the distinguishability after $\tM$ is released. The states produced by $\fR{\A\B\E}{}$ and $\fideal$ at this point are respectively (filling in the register $\tM$ with a “blank value” $\phi$ in the case where $O=\perp$ for $\fR{\A\B\E}{}$):

\begin{gather*}
(1-p_\top) \state{\perp}_O \otimes \state{\phi}_{\tM} + p_\top \state{\top}_O \otimes \sum_{\widetilde{m}} \Pr[\tM=\widetilde{m}] \state{\widetilde{m}}_{\tM}, \\
\state{\top}_O \otimes \state{\mval}_{\tM},
\end{gather*}

and the $\ell_1$ distance between them is upper bounded by

\begin{align*}
&2(1-p_\top) + p_\top \norm{\state{\top}_O \otimes \sum_{\widetilde{m}} \Pr[\tM=\widetilde{m}] \state{\widetilde{m}}_{\tM} - \state{\top}_O \otimes \state{\mval}_{\tM}}_1 \\
\leq& 2(1-p_\top) + p_\top \sum_{\widetilde{m}\neq\mval} 2 \Pr[\tM=\widetilde{m}] \leq 2\lcom + 2\lEC,
\end{align*}

applying Lemmas <ref> and <ref> in the last line.

* If $D=1$:

The distinguisher receives $D$, followed by $F$ and $\tM$. $D$ is trivial, and no inputs occur between $F$ and $\tM$, so we only need to bound the distinguishability after $\tM$ is released. The states produced by $\fR{\A\B\E}{}$ and $\fideal$ at this point are respectively (filling in the registers $\tM F$ with a “blank value” $\phi$ in the case where $O=\perp$ for $\fR{\A\B\E}{}$):

\begin{gather*}
(1-p_\top) \state{\perp}_O \otimes \state{\phi}_F \otimes \state{\phi}_{\tM} + p_\top \state{\top}_O \otimes \Frho_F \otimes \state{0^n}_{\tM}, \\
\state{\top}_O \otimes \state{\text{\cmark}}_F \otimes \state{0^n}_{\tM},
\end{gather*}

where $\Frho_F=(1-p_{\text{\cmark}|\top})\state{\text{\xmark}}_F + p_{\text{\cmark}|\top} \state{\text{\cmark}}_F$. The $\ell_1$ distance between them is upper bounded by

\begin{align*}
2(1-p_\top) + 2 p_\top (1-p_{\text{\cmark}|\top}) \leq 4\lcom,
\end{align*}

applying Lemma <ref>.

§ PARALLEL REPETITION THEOREMS

§.§ Parallel repetition theorem for 2-round 2-player product-anchored game

A 2-round 2-player non-local game is called a product-anchored game with anchoring probability $\alpha$ iff

* Alice and Bob get $(x,y) \in \clX\times\clY$ from a product distribution as their first round inputs.

* Alice and Bob produce $(a,b) \in \clA\times\clB$ as their first round outputs.

* Bob gets $z=\perp$ with probability $\alpha$ and $z=(x,y')$ with probability $1-\alpha$, as his second round input, such that the distribution of $(x,y)$ conditioned on $z=\perp$ is the same as the marginal distribution of $(x,y)$. (Alice has no input.)

* Bob produces $b'$ as his second round output. (Alice has no output.)

* Alice and Bob win the game iff $\sfV(x,y,a,b)$ and $\sfV'(x,y,z,a,b,b')$ are both satisfied.

Let $G$ be a 2-round 2-player non-local product-anchored game satisfying the conditions above with parameter $\alpha$. Then for $\delta >0$ and $t= (\omega^*(G)+\delta)l$,

\begin{align*}
\omega^*(G^l) & = \left(1-(1-\omega^*(G))^3\right)^{\Omega\left(\frac{\alpha^2l}{\log(|\clA|\cdot|\clB|\cdot|\clB'|)}\right)} \\
\omega^*(G^{t/l}) & = \left(1-\delta^3\right)^{\Omega\left(\frac{\alpha^2l}{\log(|\clA|\cdot|\clB|\cdot|\clB'|)}\right)}.
\end{align*}

We shall use the following results in order to prove the theorem.
Let $\sfP_{TU_1\ldots U_lV} = \sfP_T\sfP_{U_1|T}\sfP_{U_2|T}\ldots\sfP_{U_l|T}\sfP_{V|TU_1\ldots U_l}$ be a probability distribution over $\clT\times\clU^l\times\clV$, and let $\clE$ be any event. Then,

\[ \sum_{i=1}^l\Vert\sfP_{TU_iV|\clE}-\sfP_{TV|\clE}\sfP_{U_i|T}\Vert_1 \leq \sqrt{l\left(\log(|\clV|) + \log\left(\frac{1}{\Pr[\clE]}\right)\right)}.\]

[[8], Lemma 16]
Suppose $TVW$ are random variables satisfying $\sfP_{VW}(v,w^*)=\alpha\cdot\sfP_V(v)$ for all $v$. Then,

\[ \left\Vert \sfP_{TVW} - \sfP_{VW}\sfP_{T|V,w^*}\right\Vert_1 \leq \frac{2}{\alpha}\left\Vert \sfP_{TVW}-\sfP_{VW}\sfP_{T|V}\right\Vert_1.\]

Using the above fact, we prove the following lemma that we shall use later.

Suppose $\sfP_{ST}$ and $\sfP_{S'T'R'}$ are distributions such that $\sfP_T(t^*) = \alpha$ and $\sfP_{S|t^*}(s) = \sfP_S(s)$ for all $s$. If $\norm{\sfP_{ST}-\sfP_{S'T'}}_1 \leq \alpha$, then,

* $ \Vert\sfP_{S'R'|t^*} - \sfP_{S'R'}\Vert_1 \leq \dfrac{2}{\alpha}\Vert\sfP_{S'T'R'} - \sfP_{S'R'}\sfP_{T|S}\Vert_1 + \dfrac{5}{\alpha}\norm{\sfP_{S'T'} - \sfP_{ST}}_1$;

* $\displaystyle \begin{aligned}
& \\[0.4cm]
\norm{\sfP_{S'T'R'} - \sfP_{ST}\sfP_{R'|t^*}}_1 & \leq \frac{2}{\alpha}\Big(\norm{\sfP_{S'T'R'} - \sfP_{T'R'}\sfP_{S|T}}_1 + \norm{\sfP_{S'T'R'} - \sfP_{S'R'}\sfP_{T|S}}_1\Big)  \\
& \quad + \frac{5}{\alpha}\norm{\sfP_{S'T'} - \sfP_{ST}}_1.
\end{aligned}$

Note that

\[
\Vert \sfP_{S|t^*} - \sfP_{S'|t^*}\Vert_1 \leq \frac{2}{\alpha}\norm{\sfP_{S'T'}-\sfP_{ST}}_1
\]

by Fact <ref>. Let $\sfP_{STR''}$ denote the distribution $\sfP_{ST}\sfP_{R'|S'T'}$.

\begin{align*}
\Vert \sfP_{S'R'} - \sfP_{SR''}\Vert_1 & = \sum_{s,r}\left| \sfP_{S'}(s)\sum_t\sfP_{T'|s}(t)\sfP_{R'|st}(r) - \sfP_S(s)\sum_t\sfP_{T|s}(t)\sfP_{R'|st}(r)\right| \\
& \leq \sum_{s,t,r}\left|\sfP_{S'}(s)\sfP_{T'|s}(t) - \sfP_S(s)\sfP_{T|s}(t)\right|\sfP_{R'|st}(r) \\
& = \Vert \sfP_{S'T'} - \sfP_{ST}\Vert_1.
\end{align*}

\begin{align*}
\norm{\sfP_{SR''} - \sfP_{SR''|t^*}}_1 & \leq \left\Vert \sfP_{ST}\sfP_{R'|S'T'} - \sfP_{ST}\sfP_{R'|S',t^*}\right\Vert_1 \\
& \leq \frac{2}{\alpha}\left\Vert \sfP_{ST}\sfP_{R'|S'T'}-\sfP_{ST}\sfP_{R'|S'}\right\Vert_1 \\
& \leq \frac{2}{\alpha}\left(\left\Vert \sfP_{ST}\sfP_{R'|S'T'}-\sfP_{T|S}\sfP_{S'R'}\right\Vert_1 + \norm{\sfP_{S'T'} - \sfP_{ST}}_1\right)
\end{align*}

where in the second inequality we have used Fact <ref>.
Combining all this,

\begin{align*}
\Vert \sfP_{S'R'|t^*} - \sfP_{S'R'}\Vert_1 & \leq \Vert \sfP_{S'R'|t^*} - \sfP_{SR''|t^*}\Vert_1 + \Vert \sfP_{SR''|t^*} - \sfP_{SR''}\Vert_1 + \Vert \sfP_{SR''} - \sfP_{S'R'}\Vert_1 \\
& \leq \frac{2}{\alpha}\norm{\sfP_{S'T'}-\sfP_{ST}}_1 + \frac{2}{\alpha}\left(\left\Vert \sfP_{ST}\sfP_{R'|S'T'}-\sfP_{T|S}\sfP_{S'R'}\right\Vert_1 + \norm{\sfP_{S'T'} - \sfP_{ST}}_1\right) \\
& \quad + \norm{\sfP_{S'T'}-\sfP_{ST}}_1 \\
& \leq \frac{2}{\alpha}\Vert\sfP_{S'T'R'} - \sfP_{S'R'}\sfP_{T|S}\Vert_1 + \frac{5}{\alpha}\norm{\sfP_{S'T'} - \sfP_{ST}}_1.
\end{align*}

This proves item (i).

We have $\sfP_{T'}(t^*) \geq \sfP_T(t^*) - \frac{1}{2}\norm{\sfP_{S'T'}-\sfP_{ST}}_1 \geq \alpha/2$. Therefore we have,

\[
\norm{\sfP_{S'T'R'} - \sfP_{S|T}\sfP_{T'R'}}_1 \geq \sfP_{T'}(t^*)\norm{\sfP_{S'R'|t^*} - \sfP_{S|t^*}\sfP_{R'|t^*}}_1 \geq \frac{2}{\alpha}\norm{\sfP_{S'R'|t^*} - \sfP_{S|t^*}\sfP_{R'|t^*}}_1.
\]

Using this we get,

\begin{align}
\norm{\sfP_S\sfP_{R'|S',t^*} - \sfP_S\sfP_{R'|t^*}}_1 & \leq \norm{\sfP_{S'R'|t^*} - \sfP_{S|t^*}\sfP_{R'|t^*}}_1 + \norm{(\sfP_{S'|t^*} - \sfP_{S|t^*})\sfP_{R'|S'}}_1 \nonumber \\
& \leq \frac{2}{\alpha}\norm{\sfP_{S'T'R'} - \sfP_{S|T}\sfP_{T'R'}}_1 + \norm{\sfP_{S'|t^*} - \sfP_{S|t^*}}_1 \nonumber \\
& \leq \frac{2}{\alpha}\norm{\sfP_{S'T'R'} - \sfP_{S|T}\sfP_{T'R'}}_1 + \frac{2}{\alpha}\norm{\sfP_{S'T'} - \sfP_{ST}}_1, \label{eq:anchor-SR}
\end{align}

where we have used Fact <ref> in the last inequality.

On the other hand, using Fact <ref>,

\begin{align}
\norm{\sfP_{S'T'R'} - \sfP_{ST}\sfP_{R'|S',t^*}}_1 & \leq \norm{\sfP_{ST}\sfP_{R'|S'T'} - \sfP_{ST}\sfP_{R'|S',t^*}}_1 + \norm{\sfP_{S'T'} - \sfP_{ST}}_1 \nonumber \\
& \leq \frac{2}{\alpha}\norm{\sfP_{ST}\sfP_{R'|S'T'}-\sfP_{ST}\sfP_{R'|S'}}_1 + \norm{\sfP_{S'T'} - \sfP_{ST}}_1 \nonumber \\
& \leq \frac{2}{\alpha}\Big(\norm{\sfP_{S'T'R'} - \sfP_{S'R'}\sfP_{T|S}}_1 + \norm{\sfP_{ST} - \sfP_{S'T'}}_1 + \norm{\sfP_{S'} - \sfP_S}_1\Big) \nonumber \\
& \quad + \norm{\sfP_{S'T'} - \sfP_{ST}}_1 \nonumber \\
& \leq \frac{2}{\alpha}\norm{\sfP_{S'T'R'} - \sfP_{S'R'}\sfP_{T|S}}_1 + \frac{3}{\alpha}\norm{\sfP_{S'T'} - \sfP_{ST}}_1. \label{eq:anchor-Rt*}
\end{align}

Therefore, using (<ref>) and (<ref>),

\begin{align*}
\norm{\sfP_{S'T'R'} - \sfP_{ST}\sfP_{R'|t^*}}_1 & \leq \norm{\sfP_{S'T'R'} - \sfP_{ST}\sfP_{R'|S',t^*}}_1 + \norm{\sfP_S\sfP_{R'|S',t^*} - \sfP_S\sfP_{R'|t^*}}_1 \\
& \leq \frac{2}{\alpha}\Big(\norm{\sfP_{S'T'R'} - \sfP_{T'R'}\sfP_{S|T}}_1 + \norm{\sfP_{S'T'R'} - \sfP_{S'R'}\sfP_{T|S}}_1\Big)  \\
& \quad + \frac{5}{\alpha}\norm{\sfP_{S'T'} - \sfP_{ST}}_1.
\end{align*}

This proves item (ii).

Finally, we shall use the following two facts.
[[15], Lemma III.1]
Suppose $\rho$ and $\sigma$ are CQ states satisfying $\rho = \delta\sigma + (1-\delta)\sigma'$ for some other state $\sigma'$. Suppose $Z$ is a classical register of size $|\clZ|$ in $\rho$ and $\sigma$ such that the distribution on $Z$ in $\sigma$ is $\sfP_Z$, then

\[ \bbE_{\sfP_Z}\sfD(\sigma_z\Vert\rho) \leq \log(1/\delta) + \log|\clZ|.\]

[Quantum Raz's Lemma, [8]]
Let $\rho_{XY}$ and $\sigma_{XY}$ be two CQ states with $X = X_1\ldots X_l$ being classical, and $\sigma$ being product across all registers. Then,

\[ \sum_{i=1}^l\sfI(X_i:Y)_\rho \leq \sfD(\rho_{XY}\Vert \sigma_{XY}).\]

If two distributions $\sfP_{XY}$ and $\sfP_{X'Y'Z'}$ such that $X,X'$ and $Y,Y'$ are on the same sets $\clX$ and $\clY$ respectively, satisfy

\[ \Vert\sfP_{X'Y'Z'} - \sfP_{XY}\sfP_{Z'|X'}\Vert_1 \leq \eps \quad \quad \Vert\sfP_{X'Y'Z'} - \sfP_{XY}\sfP_{Z'|Y'}\Vert_1 \leq \eps,\]

then there exists a random variable $R$ on a set $\clR$ independent of $XY$ and functions $f_A: \clX \times \clR \to \clS$ and $f_B: \clY\times\clR\to\clT$, such that

\[ \Vert\sfP_{XYf_\A(X,R)f_\B(Y,R)} - \sfP_{X'Y'Z'Z'}\Vert_1 \leq 5\eps.\]

[[15], Lemma II.15]
Let the following pure state be shared between Alice and Bob, with Alice holding registers $X\tX A$ and Bob holding registers $Y\tY B$:

\[ \ket{\vph}_{X\tX Y\tY AB} = \sum_{x,y}\sqrt{\sfP_{XY}(x,y)}\ket{xx}_{X\tX}\ket{yy}_{Y\tY}\ket{\vph}_{AB|xy}.\]

If $\sfI(X:Y\tY B) \leq \eps$ and $\sfI(Y:X\tX A) \leq \eps$, then there exist unitary operators $\{U_x\}_x$ on $X\tX A$ and $\{V_y\}_y$ $Y\tY B$ such that

\[ \bbE_{\sfP_{XY}}\left\Vert\state{\vph}_{X\tX Y\tY AB|xy} - (U_x\otimes V_y)\state{\vph}_{X\tX Y\tY AB}(U_x^\dagger\otimes V_y^\dagger)\right\Vert_1 \leq 8\sqrt{\eps} + \Vert\sfP_{XY} - \sfP_X\sfP_Y\Vert_1.\]

Consider a strategy $\clS$ for $l$ copies of $G$ (it may correspond to $G^l$ or $G^{t/l}$ — it doesn't really matter): before the game starts, Alice and Bob share an entangled state on registers $A\tA B\tB B'\tB' E^\A E^\B$. Here $A, B, B'$ will be the registers in which the outputs are measured in the computational basis, and $\tA, \tB, \tB'$ are registers onto which the contents of $A,B, B'$ are copied — we can always assume the outputs are copied since they are classical. Alice and Bob apply unitaries based on their first round inputs $XY$ to their respective halves of this entangled state and measure in the computational basis to obtain their first round outputs. We define the following pure state to represent the inputs, outputs and other registers in the protocol at this stage:

\begin{align*}
& \ket{\rho}_{X\tX Y\tY Z\tZ A\tA B\tB B'\tB'E^\A E^\B} \\
= & \sum_{x,y}\sqrt{\sfP_{XYZ}(x,y,z)}\ket{xx}_{X\tX}\ket{yy}_{Y\tY}\ket{zz}_{Z\tZ}\sum_{a,b}\sqrt{\sfP_{AB|xy}(ab)}\ket{aa}_{A\tA}\ket{bb}_{B\tB}\ket{\rho}_{B'\tB'E^\A E^\B|xyab}
\end{align*}

where we have used $Z$ to denote Bob's second round input, which is either $\perp$ or $(x,y')$. We have included the $Z\tZ$ registers in this state even though Bob has not received the $z$ input yet; the state in the entangled registers has no dependence on $z$ however. Here $\sfP_{AB|xy}(a,b)$ is the probability of Alice and Bob obtaining outputs $(a,b)$ on inputs $(x,y)$ in the first round.

In the actual protocol, the $AB$ registers are measured on $\ket{\rho}$, and the subsequent unitary Bob applies on the $B'\tB'E^\B$ registers can depend on his first round output, as well as both his inputs. We represent the state of the protocol at this state by:

\begin{align*}
& \ket{\sigma}_{X\tX Y\tY Z\tZ A\tA B\tB B'\tB'E^\A E^\B} \\
= & \sum_{x,y}\sqrt{\sfP_{XYZ}(x,y,z)}\ket{xx}_{X\tX}\ket{yy}_{Y\tY}\ket{zz}_{Z\tZ}\sum_{a,b}\sqrt{\sfP_{AB|xy}(ab)}\ket{aa}_{A\tA}\ket{bb}_{B\tB}\otimes \\
& \quad\quad \sum_{b'}\sqrt{\sfP_{B'|xyzab}(b')}\ket{b'b'}_{B'\tB'}\ket{\sigma}_{E^\A E^\B|xyzabb'}.
\end{align*}

Note that $\ket{\sigma}$ is related to $\ket{\rho}$ by a unitary on the $B'\tB'E^\B$ registers that is controlled on the registers $YZB$, which is why the marginal distribution of $AB$ is the same in $\ket{\rho}$ and $\ket{\sigma}$.

Let $\omega^*(G) = 1 - \eps$. We shall prove the following lemma, from which, using standard techniques (see e.g. [22]), the theorem follows.

For $i\in[l]$, let $T_i=\sfV(A_iB_i,X_iY_i)\land\sfV'(A_iB_iB'_i,X_iY_iZ_i)$ in a strategy $\clS$ for $l$ copies of $G$ (here $X,Y$ are the first round inputs, $A,B$ first round outputs, and $\sfV$ the first round predicate; $Z$ is the second round input, $B'$ the second round output, and $\sfV'$ the second round predicate). If $\clE$ is the event $\prod_{i\in C}T_i=1$ for $C\subseteq [l]$, then

\[ \bbE_{i\in\oC}\Pr[T_i=1|\clE] \leq 1-\frac{\eps}{2} \]

as long as

\[ \delta = \frac{|C|\cdot\log(|\clA|\cdot|\clB|\cdot|\clB'|) + \log(1/\Pr[\clE])}{l} \leq \frac{\eps^2\alpha^2}{265^2}.\]

For each $i\in[l]$, we define the correlation-breaking random variables $D_iG_i$ as follows: $D_i$ is a uniformly random bit, and $G_i$ takes value $X_iY_i$ or $Z_i$ respectively depending on whether $D_i$ is 0 or 1. Clearly $XYZ$ are independent conditioned on $DG$. We can consider the states $\ket{\rho}$ and $\ket{\sigma}$ conditioned on $DG=dg$, and this simply means that the distribution of $XYZ$ used is conditioned on $dg$.

Conditioned on $DG=dg$, we define the state $\ket{\vph}_{dg}$, which is $\ket{\sigma}_{dg}$ conditioned on success in $C$:

\begin{align*}
& \ket{\vph}_{X\tX Y\tY Z\tZ A\tA B\tB B'\tB'E^\A E^\B|dg} \\
= & \frac{1}{\sqrt{\gamma_{dg}}}\sum_{x,y}\sqrt{\sfP_{XYZ|dg}(xyz)}\ket{xx}_{X\tX}\ket{yy}_{Y\tY}\ket{zz}_{Z\tZ}\sum_{\substack{a,b,b': \\ (x_C,y_C,z_C,a_C,b_C,b'_C) \\ \text{win } G^t}}\sqrt{\sfP_{ABB'|xyz}(ab)}\ket{aa}_{A\tA}\ket{bb}_{B\tB}\otimes \\
& \quad\quad \ket{b'b'}_{B'\tB'}\ket{\sigma}_{E^\A E^\B|xyzabb'}
\end{align*}

where $\gamma_{dg}$ is the probability of winning in $C$ conditioned on $DG=dg$, in $\clS$. It is easy to see that $\sfP_{XYZABB'|\clE,dg}$ is the distribution on the registers $XYZABB'$ in $\ket{\vph}_{dg}$, and $\bbE_{\sfP_{DG|\clE}}\sfP_{XYZABB'|\clE,dg}$ is $\sfP_{XYZABB'|\clE}$.

We shall use the following lemma, whose proof we give later, to prove Lemma <ref>.

If $\delta \leq \frac{\eps^2\alpha^2}{265^2}$, then using $R_i = X_CY_CZ_CA_CB_CB'_C D_{-i}G_{-i}$, the following conditions hold:

* $\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{X_iY_iZ_i}\sfP_{R_i|\clE,\perp}}_1 \leq \dfrac{9\sqrt{2\delta}}{\alpha}$;

* For each $i$, there exist unitaries $\{U^i_{x_ir_i}\}_{x_ir_i}$ acting on $X_{\oC}\tX_{\oC}E^\A A_{\oC}\tA_{\oC}$, and $\{V^i_{y_ir_i}\}_{y_ir_i}$ acting on $Y_{\oC}\tY_{\oC}E^\B B_{\oC}\tB_{\oC}B'_{\oC}\tB'_{\oC}$ such that

\[ \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iR_i|\clE}}\norm{U^i_{x_ir_i}\otimes V^i_{y_ir_i}\state{\vph}_{\perp r_i}(U^i_{x_ir_i})^\dagger\otimes(V^i_{y_ir_i})^\dagger - \state{\vph}_{x_iy_i\perp r_i}}_1 \leq \frac{58\sqrt{2\delta}}{\alpha}; \]

* $\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE}\left(\sfP_{A_iB_i|\clE,X_iY_iZ_iR_i} - \sfP_{A_iB_i|\clE,X_iY_i,\perp ,R_i}\right)}_1 \leq \dfrac{30\sqrt{2\delta}}{\alpha}$;

* There exist unitaries $\{W^i_{y_iz_ir_i}\}_{y_iz_ir_i}$ acting on the registers $Y_{\oC}\tY_{\oC}Z_{\oC}\tZ_{\oC}E^\B B'_{\oC}\tB'_{\oC}$ such that

\[ \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iA_iB_iR_i|\clE}}\norm{\Id\otimes W^i_{y_iz_ir_i}\state{\vph}_{x_iy_i\perp a_ib_ir_i}\Id\otimes (W^i_{y_iz_ir_i})^\dagger - \state{\vph}_{x_iy_iz_ia_ib_ir_i}}_1 \leq \frac{90\sqrt{2\delta}}{\alpha}. \]

Using Lemma <ref>, we give a strategy $\clS'$ for a single copy of $G$ as follows:

* Alice and Bob share $\log|\oC|$ uniform bits, for each $i\in\oC$, $\sfP_{R_i|\clE,\perp }$ as randomness, and for each $R_i=r_i$, the state $\ket{\vph}_{\perp r_i}$ as entanglement, with Alice holding registers $X_{\oC}\tX_{\oC}E^\A A_{\oC}\tA_{\oC}$ and Bob holding registers $Y_{\oC}\tY_{\oC}Z_{\oC}\tZ_{\oC}E^\B B_{\oC}\tB_{\oC}B'_{\oC}\tB'_{\oC}$.

* Alice and Bob use their shared randomness to sample $i\in\oC$ uniformly, and in the first round, apply $U^i_{x_ir_i}$, $V^i_{y_ir_i}$ on their parts of the shared entangled state according to their shared randomness from $\sfP_{R_i|\clE,\perp }$ and their first round inputs.

* Alice and Bob measure the $A_i,B_i$ registers of the resulting state to give their first round outputs.

* Bob applies $W^i_{z_ir_i}$ to his half of the shared entangled state after the first round according to his second round input and the shared randomness.

* Bob measures the $B'_i$ register of the resulting state to give his second round output.

We shall first do the analysis assuming Alice and Bob have the distribution $\sfP_{X_iY_iZ_iR_i|\clE}$ exactly. If $\sfP_{\hA_i\hB_i|X_iY_iZ_iR_i}$ is the conditional distribution Alice and Bob get after the first round, and $\sfP_{\hB'_i|X_iY_iZ_iR_i\hA_i\hB_i}$ denotes their conditional distribution after the second round, then from items (ii) and (iii) of Lemma <ref> we have,

\[ \bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE}\left(\sfP_{\hA_i\hB_i|X_iY_iZ_iR_i} - \sfP_{A_iB_i|\clE,X_iY_iZ_iR_i}\right)}_1 \leq \frac{58\sqrt{2\delta}}{\alpha} + \frac{30\sqrt{2\delta}}{\alpha}.\]

From item (iv) we have,

\[ \bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_iA_iB_i}\left(\sfP_{\hB'_i|X_iY_iZ_iR_i\hA_i\hB_i} - \sfP_{B'_i|\clE,X_iY_iZ_iR_iA_iB_i}\right)}_1 \leq \frac{90\sqrt{2\delta}}{\alpha}.\]

Combining these with item (i), then we overall have,

\[ \bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_i}\sfP_{R_i|\clE,\perp }\sfP_{\hA_i\hB_i\hB'_i|X_iY_iZ_iR_i} - \sfP_{X_iY_iZ_iR_iA_iB_iB'_i|\clE}}_1 \leq \frac{9\sqrt{2\delta}}{\alpha} + \frac{58\sqrt{2\delta}}{\alpha} + \frac{120\sqrt{2\delta}}{\alpha} \leq \eps \]

for $\delta \leq \frac{\eps^2\alpha^2}{265^2}$. Therefore, if $\bbE_{i\in\oC}\Pr[T_i=1|\clE] > 1-\frac{\eps}{2}$, then this winning probability is more than $1-\eps=\omega^*(G)$, which is a contradiction. Therefore we must have $\bbE_{i\in\oC}\Pr[T_i=1|\clE] \leq 1 - \frac{\eps}{2}$.

Closeness of distributions. Applying Fact <ref> with $T,V$ being trivial and $U_i = X_iY_iZ_i$ we get,

\begin{equation}
\bbE_{i \in \oC }\Vert\sfP_{X_iY_iZ_i|\clE} - \sfP_{X_iY_iZ_i}\Vert_1 \leq \frac{1}{l-|C|}\sqrt{l\cdot \log(1/\Pr[\clE])} \leq \sqrt{2\delta}. \label{eq:XYZ}
\end{equation}

In particular by Facts <ref> and <ref> this means, $\bbE_i \sfP_{Z_i|\clE}(\perp) \geq \alpha - \sqrt{\delta/2} \geq \alpha/2$. Applying Fact <ref> again with $U_i$ the same, $T=X_CY_CZ_CDG$ and $V=A_CB_CB'_C$, and using $R_i = X_CY_CZ_CA_CB_CB'_CD_{-i}G_{-i}$,

\begin{align}
\sqrt{2\delta} & \geq \bbE_{i\in\oC }\Vert\sfP_{X_iY_iZ_iD_iG_iR_i|\clE} - \sfP_{D_iG_iR_i|\clE}\sfP_{X_iY_iZ_i|D_iG_i}\Vert_1 \nonumber \\
& = \frac{1}{2}\bbE_{i\in\oC }\left(\Vert\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{X_iY_iR_i|\clE}\sfP_{Z_i|X_iY_i}\Vert_1 + \Vert\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{Z_iR_i|\clE}\sfP_{X_iY_i|Z_i}\Vert_1\right) \label{eq:XYZR-1}
\end{align}

Using Lemma <ref> on (<ref>) and (<ref>) we get,

\begin{equation}\label{eq:XYR-z*}
\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{X_iY_iZ_i}\sfP_{R_i|\clE,\perp }}_1 \leq \dfrac{9\sqrt{2\delta}}{\alpha}
\end{equation}

which proves item (i) of the lemma.

Existence of unitaries $U^i_{x_ir_i}$ and $V^i_{y_ir_i}$. Note that $\sigma_{X_{\oC }Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|x_Cy_Cz_Cdg}$ is product across $X_{\oC }$ and the rest of the registers, since $dg$ is being conditioned on. Hence using Fact <ref> and Quantum Raz's Lemma,

\begin{align}
\delta l & \geq \bbE_{\sfP_{X_CY_CZ_CA_CB_CB'_CDG|\clE}}\sfD\left(\vph_{X_{\oC }Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }E^\B|x_Cy_Cz_Ca_Cb_Cb'_Cdg}\middle\Vert\sigma_{X_{\oC }Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }E^\B|x_Cy_Cz_Cdg}\right) \nonumber \\
& \geq \sum_{i\in\oC }\sfI(X_i:Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }E^\B|X_CY_CZ_CA_CB_CB'_CDG)_\vph \nonumber \\
& \geq \frac{l}{2}\bbE_{i\in\oC }\bbE_{\sfP_{D_iG_iR_i|\clE}}\sfI(X_i:Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }E^\B)_{\vph_{d_ig_ir_i}} \nonumber \\
%& \geq \frac{l}{2}\cdot\frac{\alpha}{4}\bbE_{i\in\oC }\bbE_{\sfP_{R_i|\clE,\perp}}\sfI(X_i:Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }E^\B)_{\vph_{\perp,r_i}}
& \geq \frac{l}{2}\cdot\frac{1}{2}\bbE_{i\in\oC }\bbE_{\sfP_{Z_iR_i|\clE}}\sfI(X_i:Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }E^\B)_{\vph_{z_ir_i}} \nonumber \\
& \geq \frac{l}{4}\bbE_{i\in\oC }\bbE_{\sfP_{X_iZ_iR_i|\clE}} \sfB\left(\vph_{Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|x_iz_ir_i}, \vph_{Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|z_ir_i}\right)^2 \nonumber
\end{align}

where we have used Pinsker's inequality in the final step. Using Jensen's inequality on the above we then have,

\begin{align*}
2\sqrt{\delta} & \geq \bbE_{i\in\oC }\bbE_{\sfP_{X_iZ_iR_i|\clE}} \sfB\left(\vph_{Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|x_iz_ir_i}, \vph_{Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|z_ir_i}\right) \\
& \geq \frac{\alpha}{2} \bbE_{i\in\oC }\bbE_{\sfP_{X_iR_i|\clE,\perp}} \sfB\left(\vph_{Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|x_i\perp r_i}, \vph_{Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }|\perp r_i}\right)
\end{align*}

Therefore, by Uhlmann's theorem and the Fuchs-van de Graaf inequality, there exist unitaries $\{U^i_{x_ir_i}\}_{x_ir_i}$ acting on the registers $X_{\oC}\tX_{\oC}E^\A A_{\oC}\tA_{\oC}$ such that

\begin{equation}\label{eq:X-unitary}
\bbE_{i\in\oC }\bbE_{\sfP_{X_iR_i|\clE,\perp}}\norm{U^i_{x_ir_i}\otimes\Id\state{\vph}_{\perp r_i}(U^i_{x_ir_i})^\dagger\otimes\Id - \state{\vph}_{x_i\perp r_i}}_1 \leq \frac{8\sqrt{2\delta}}{\alpha}.
\end{equation}

Similarly, $\sigma_{Y_{\oC}X_{\oC}\tX_{\oC}E^\A A_{\oC}\tA_{\oC}|x_Cy_Cz_Cdg}$ is product across $Y_{\oC}$ and the rest of the registers. Hence by using the same analysis as above, we get that there exist unitaries $\{V^i_{y_ir_i}\}_{y_ir_i}$ acting only on the registers $Y_{\oC }\tY_{\oC }Z_{\oC }\tZ_{\oC } E^\B B_{\oC }\tB_{\oC } B'_{\oC }\tB'_{\oC }$ such that,

\begin{equation}\label{eq:Y-unitary}
\bbE_{i\in\oC }\bbE_{\sfP_{Y_iR_i|\clE,\perp}}\norm{\Id\otimes V^i_{y_ir_i}\state{\vph}_{\perp r_i}\Id\otimes(V^i_{y_ir_i})^\dagger - \state{\vph}_{y_i\perp r_i}}_1 \leq \frac{8\sqrt{2\delta}}{\alpha}.
\end{equation}

Now, if $\clO_{X_i}$ is the channel that measures the $X_i$ register and records the outcome, then

\begin{align*}
\clO_{X_i}\left(\Id\otimes V^i_{y_ir_i}\state{\vph}_{\perp r_i}\Id\otimes(V^i_{y_ir_i})^\dagger\right) & = \bbE_{\sfP_{X_i|\clE,\perp r_i}}\state{x_i}\otimes\left(\Id\otimes V^i_{y_ir_i}\state{\vph}_{x_i\perp r_i}\Id\otimes(V^i_{y_ir_i})^\dagger\right) \\
\clO_{X_i}\left(\state{\vph}_{y_i\perp r_i}\right) & = \bbE_{\sfP_{X_i|\clE,y_i\perp r_i}}\state{x_i}\otimes\state{\vph}_{x_iy_i\perp r_i}.
\end{align*}

Therefore, applying Fact <ref> to (<ref>) with the $\clO_{X_i}$ channel we get,

\begin{align*}
& \bbE_{i\in\oC }\bbE_{\sfP_{Y_iR_i|\clE,\perp}}\norm{\bbE_{\sfP_{X_i|\clE,y_i\perp r_i}}\state{x_i}\otimes\left(\Id\otimes V^i_{y_ir_i}\state{\vph}_{x_i\perp r_i}\Id\otimes(V^i_{y_ir_i})^\dagger\right) - \bbE_{\sfP_{X_i|\clE,\perp r_i}}\state{x_i}\otimes\state{\vph}_{x_iy_i\perp r_i}}_1 \\
\leq & \frac{8\sqrt{2\delta}}{\alpha}.
\end{align*}

From this we have,

\begin{align}
& \bbE_{i\in\oC }\bbE_{\sfP_{X_iY_iR_i|\clE,\perp}}\norm{\Id\otimes V^i_{y_ir_i}\state{\vph}_{x_i\perp r_i}\Id\otimes(V^i_{y_ir_i})^\dagger - \state{\vph}_{x_iy_i\perp r_i}}_1 \nonumber \\
\leq & \frac{8\sqrt{2\delta}}{\alpha} + \bbE_{i\in\oC }\bbE_{\sfP_{X_iY_iR_i|\clE,\perp}}\norm{\bbE_{\sfP_{X_i|\clE,y_i\perp r_i}}\state{x_i} - \bbE_{\sfP_{X_i|\clE,\perp r_i}}\state{x_i}}_1 \nonumber \\
\leq & \frac{8\sqrt{2\delta}}{\alpha} + 2\bbE_{i\in\oC}\norm{\sfP_{X_iY_iR_i|\clE,\perp } - \sfP_{R_i|\clE,\perp }\sfP_{X_i|\clE,\perp ,R_i}\sfP_{Y_i|\clE,\perp ,R_i}}_1. \label{eq:Y-unitary-2}
\end{align}

Combining equations (<ref>) and (<ref>) we then get,

\begin{align}
& \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iR_i|\clE,\perp }}\norm{U^i_{x_ir_i}\otimes V^i_{y_ir_i}\state{\vph}_{\perp r_i}(U^i_{x_ir_i})^\dagger\otimes(V^i_{y_ir_i})^\dagger - \state{\vph}_{x_iy_i\perp r_i}}_1 \nonumber \\
\leq & \frac{16\sqrt{2\delta}}{\alpha} + 2\bbE_{i\in\oC}\norm{\sfP_{X_iY_iR_i|\clE,\perp } - \sfP_{R_i|\clE,\perp }\sfP_{X_i|\clE,\perp ,R_i}\sfP_{Y_i|\clE,\perp ,R_i}}_1. \label{eq:XY-UV-1}
\end{align}

Now note that we have an upper bound of $2\sqrt{2\delta}$ on $\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{X_iY_i|Z_i}\sfP_{Z_iR_i|\clE}}_1$. Thus, by Fact <ref>,

\begin{align*}
\bbE_{i\in\oC}\norm{\sfP_{X_iY_iR_i|\clE,\perp } - \sfP_{X_iY_i|\perp }\sfP_{R_i|\clE,\perp }}_1 & \leq \frac{2}{\sfP_{Z_i}(\perp )}\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{X_iY_i|Z_i}\sfP_{Z_iR_i|\clE}}_1 \\
& \leq \frac{4\sqrt{2\delta}}{\alpha}.
\end{align*}

Using this we get,

\begin{align*}
& \bbE_{i\in\oC}\left\Vert\sfP_{X_iY_iR_i|\clE,\perp } - \sfP_{R_i|\clE,\perp }\sfP_{X_i|\clE,\perp ,R_i}\sfP_{Y_i|\clE,\perp ,R_i}\right\Vert_1 \nonumber \\
\leq & \bbE_{i\in\oC}\left(\left\Vert\sfP_{X_iY_iR_i|\clE,\perp } - \sfP_{X_iY_i|\perp }\sfP_{R_i|\clE,\perp }\right\Vert_1 + \left\Vert\sfP_{X_i|\perp }\sfP_{Y_i|\perp }\sfP_{R_i|\clE,\perp } - \sfP_{Y_iR_i|\clE,\perp }\sfP_{X_i|\clE,\perp ,R_i}\right\Vert_1\right) \nonumber \\
\leq & \frac{4\sqrt{2\delta}}{\alpha} + \bbE_{i\in\oC}\left(\left\Vert(\sfP_{X_i|\perp }\sfP_{R_i|\clE,\perp } - \sfP_{X_iR_i|\clE,\perp })\sfP_{Y_i|\perp }\right\Vert_1 + \left\Vert\sfP_{X_i|\clE,\perp ,R_i}(\sfP_{Y_i|\perp }\sfP_{R_i|\clE,\perp } - \sfP_{Y_iR_i|\clE,\perp })\right\Vert_1\right) \nonumber \\
\leq & \frac{4\sqrt{2\delta}}{\alpha} + \bbE_{i\in\oC}\left(\left\Vert\sfP_{X_i|\perp }\sfP_{R_i|\clE,\perp } - \sfP_{X_iR_i|\clE,\perp }\right\Vert_1 + \left\Vert\sfP_{Y_i|\perp }\sfP_{R_i|\clE,\perp } - \sfP_{Y_iR_i|\clE,\perp }\right\Vert_1\right) \nonumber \\
\leq & \frac{4\sqrt{2\delta}}{\alpha} + 2\bbE_{i\in\oC}\left\Vert\sfP_{X_iY_iR_i|\clE,\perp } - \sfP_{X_iY_i|\perp }\sfP_{R_i|\clE,\perp }\right\Vert_1 \leq \frac{12\sqrt{2\delta}}{\alpha}.
\end{align*}

Putting this in (<ref>) we get,

\[
\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iR_i|\clE,\perp }}\norm{U^i_{x_ir_i}\otimes V^i_{y_ir_i}\state{\vph}_{\perp r_i}(U^i_{x_ir_i})^\dagger\otimes(V^i_{y_ir_i})^\dagger - \state{\vph}_{x_iy_i\perp r_i}}_1 \leq \frac{16\sqrt{2\delta}}{\alpha} + \frac{24\sqrt{2\delta}}{\alpha}.
\]

Finally, using item (i) of Lemma <ref> we get,

\begin{align}
& \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iR_i|\clE}}\norm{U^i_{x_ir_i}\otimes V^i_{y_ir_i}\otimes\Id\state{\vph}_{\perp r_i}(U^i_{x_ir_i})^\dagger\otimes(V^i_{y_ir_i})^\dagger\otimes\Id - \state{\vph}_{x_iy_i\perp r_i}}_1 \nonumber \\
\leq & \frac{40\sqrt{2\delta}}{\alpha} + 2\bbE_{i\in\oC}\norm{\sfP_{X_iY_iR_i|\clE} - \sfP_{X_iY_iR_i|\clE,\perp }}_1 \nonumber \\
\leq & \frac{40\sqrt{2\delta}}{\alpha} + \frac{18\sqrt{2\delta}}{\alpha} \leq \frac{58\sqrt{2\delta}}{\alpha}. \label{eq:XY-UV-2}
\end{align}

This proves item (ii) of the lemma.

Existence of unitaries $W^i_{y_iz_ir_i}$. Note that $\sigma_{Z_{\oC}X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|dg}$ is product across $Z_{\oC}$ and the rest of the registers, since they were product in $\rho$, and $\sigma$ is obtained from $\rho$ by a unitary that acts on the other registers, only using $Z_{\oC}$ as a control register (this is also true if we include $Y_{\oC}\tY_{\oC}$ along with $X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A$, but we don't need to do this). Therefore, by the same analysis as in the case of $X_{\oC}$ and $Y_{\oC}$,

\begin{align*}
2\delta & \geq \bbE_{i\in\oC}\bbE_{\sfP_{Z_iD_iG_iR_i|\clE}}\sfD\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|z_id_ig_ir_i}\middle\Vert\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|d_ig_ir_i}\right) \\
& \geq \frac{1}{2}\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iR_i|\clE}}\sfD\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_iz_ir_i}\middle\Vert\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_ir_i}\right) \\
& \geq \frac{1}{2}\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iR_i|\clE}}\sfB\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_iz_ir_i},\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_ir_i}\right)^2 \\
& \geq \frac{\alpha}{4}\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iR_i|\clE,\perp }}\sfB\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_i\perp r_i},\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_ir_i}\right)^2.
\end{align*}

Using Jensen's inequality on the last two inequalities, we get,

\begin{align*}
\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iR_i|\clE}}\sfB\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_iz_ir_i},\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_ir_i}\right) & \leq 2\sqrt{\delta} \\
\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iR_i|\clE,\perp }}\sfB\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_i\perp r_i},\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_ir_i}\right) & \leq \frac{4\sqrt{\delta}}{\alpha}.
\end{align*}

Now using the bound on $\bbE_{i\in\oC}\norm{\sfP_{X_iY_iR_i|\clE} - \sfP_{X_iY_iR_i|\clE,\perp }}_1$ from item (i) of Lemma <ref>, we have by the triangle inequality,

\[ \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iR_i|\clE}}\sfB\left(\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_iz_ir_i},\vph_{X_{\oC}\tX_{\oC}A_{\oC}\tA_{\oC}B_{\oC}\tB_{\oC}E^\A|x_iy_i\perp r_i}\right) \leq \frac{15\sqrt{\delta}}{\alpha}.\]

Applying the Fuchs-van de Graaf inequality on this and tracing out registers besides $A_iB_i$ already gives us item (iii) of the lemma. To get item (iv), we use Uhlmann's theorem, which gives us unitaries $\{W^i_{x_iy_iz_ir_i}\}_{x_iy_iz_ir_i}$ acting on $Y_{\oC}\tY_{\oC}Z_{\oC}\tZ_{\oC}E^\B B'_{\oC}\tB'_{\oC}$ such that

\begin{equation}\label{eq:Z-unitary-1}
\bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iR_i|\clE}}\norm{\Id\otimes W^i_{x_iy_iz_ir_i}\state{\vph}_{x_iy_i,\perp r_i}\Id\otimes(W^i_{x_iy_iz_ir_i})^\dagger - \state{\vph}_{x_iy_iz_ir_i}}_1 \leq \frac{30\sqrt{2\delta}}{\alpha}.
\end{equation}

Since $z_i$ is either $\perp $, in which case the unitary $W^i_{x_iy_iz_ir_i}$ can just be identity, or $z_i$ contains $x_i$, $W^i_{x_iy_iz_ir_i}$ is in fact just $W^i_{y_iz_ir_i}$.

Let $\clO_{A_iB_i}$ be the channel that measures the $A_iB_i$ registers and records the outcomes. This clearly commutes with $W^i_{y_iz_ir_i}$. Therefore,

\begin{align*}
& \clO_{A_iB_i}\left(\Id\otimes W^i_{y_iz_ir_i}\state{\vph}_{x_iy_i\perp r_i}\Id\otimes(W^i_{y_iz_ir_i})^\dagger\right) \\
= & \bbE_{\sfP_{A_iB_i|\clE,x_iy_i\perp r_i}}\state{a_ib_i}\otimes\left(\Id\otimes W^i_{y_iz_ir_i}\state{\vph}_{x_iy_i\perp a_ib_ir_i}\Id\otimes(W^i_{y_iz_ir_i})^\dagger\right) \\
& \clO_{A_iB_i}\left(\state{\vph}_{x_iy_iz_ir_i}\right) \\
= & \bbE_{\sfP_{A_iB_i|x_iy_iz_ir_i}}\state{a_ib_i}\otimes\state{\vph}_{x_iy_iz_ia_ib_ir_i}
\end{align*}

Using this and Fact <ref> on (<ref>) along with item (iii) we get,

\begin{align*}
& \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iA_iB_iR_i|\clE}}\norm{\Id\otimes W^i_{y_iz_ir_i}\state{\vph}_{x_iy_i\perp a_ib_ir_i}\Id\otimes(W^i_{y_iz_ir_i})^\dagger - \state{\vph}_{x_iy_iz_ia_ib_ir_i}}_1 \\
\leq & \frac{30\sqrt{2\delta}}{\alpha} + 2\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE}\left(\sfP_{A_iB_i|\clE,X_iY_iZ_iR_i} - \sfP_{A_iB_i|\clE,X_iY_i,\perp ,R_i}\right)}_1 \\
\leq & \frac{90\sqrt{2\delta}}{\alpha}
\end{align*}

This proves item (iv).

§.§ Parallel repetition theorem for 1-round 3-player product-anchored game

We call a 1-round 3-player product-anchored iff Alice and Bob's marginal input distribution is a product distribution, and Eve's input takes value either $z=(x,y)$ or $z=\perp$ such that $p(x,y,\perp) = \alpha\cdot p(x,y)$. Note that this is also a special type of anchoring on Charlie's side, but this definition will be sufficient for our purposes.

Let $G$ be a 1-round 3-player non-local product-anchored game with parameter $\alpha$. Then for $\delta>0$ and $t = (\omega^*(G)+\delta)l$,

\begin{align*}
\omega^*(G^l) & = \left(1-(1-\omega^*(G))^3\right)^{\Omega\left(\frac{\alpha^2l}{\log(|\clA|\cdot|\clB|\cdot|\clC|)}\right)} \\
\omega^*(G^{t/l}) & = \left(1-\delta^3\right)^{\Omega\left(\frac{\alpha^2l}{\log(|\clA|\cdot|\clB|\cdot|\clC|)}\right)}.
\end{align*}

Defining the correlation-breaking variables $D_iG_i$ the same way as in the 2-player 2-round case, we have that conditioned on $DG=dg$, Alice's inputs are in product with Bob and Eve's systems in the state of a strategy for $l$ copies of $G$; the analogous statements hold for Bob and Eve's inputs as well. As in the case of the 2-round game, we condition on the success event $\clE$ on a subset $C$, and define $\ket{\vph}$ to be the state of the protocol conditioned on $\clE$. Defining $R_i$ and the quantity $\delta$ the same way, the lemma analogous to <ref> in this case is the following.

If $\delta = O(\eps^2\alpha^2)$, the following conditions hold:

* $\bbE_{i\in\oC}\norm{\sfP_{X_iY_iZ_iR_i|\clE} - \sfP_{X_iY_iZ_i}\sfP_{R_i|\clE,\perp}}_1 \leq \frac{9\sqrt{2\delta}}{\alpha}$;

* For each $i\in\oC$, there exist unitaries ${U^i_{x_ir_i}}_{x_ir_i}, \{V^i_{y_ir_i}\}_{y_ir_i}, \{W^i_{z_ir_i}\}_{z_ir_i}$ acting on Alice, Bob and Charlie's systems such that

\begin{align*}
& \bbE_{i\in\oC}\bbE_{\sfP_{X_iY_iZ_iR_i|\clE}}\norm{U^i_{x_ir_i}\otimes V^i_{y_ir_i}\otimes W^i_{z_ir_i}\state{\vph}_{\perp r_i}(U^i_{x_ir_i})^\dagger\otimes(V^i_{y_ir_i})^\dagger\otimes(W^i_{z_ir_i})^\dagger - \state{\vph}_{x_iy_iz_ir_i}}_1 \\
\leq & \frac{88\sqrt{2\delta}}{\alpha}.
\end{align*}

The proof of item (i) in Lemma <ref> is exactly the same as in Lemma <ref>. The existence of unitaries $U^i_{x_ir_i}$ and $V^i_{y_ir_i}$ in item (ii) is shown in exactly the same way. The existence of Eve's unitaries $W^i_{z_ir_i}$ is shown in a way similar to the existence of the second round unitaries in Lemma <ref>, and using the fact that Eve's inputs are in product with Alice and Bob's systems in the original state, conditioned on $dg$.

Using Lemma <ref>, we can give a strategy for a single copy of $G$ where Alice, Bob and Eve share $\sfP_{R_i|\clE,\perp}$ as randomness and $\ket{\vph}_{\perp r_i}$ as entanglement, and apply the unitaries $U^i_{x_ir_i}, V^i_{y_ir_i}$ and $W^i_{z_ir_i}$ on receiving inputs $(x_i,y_i,z_i)$.

§ ACKNOWLEDGEMENTS

We thank Anne Broadbent for discussions on the result in [6], as well as
Lídia del Rio, Christopher Portmann, Renato Renner and Vilasini Venkatesh for discussions on composable security. We also thank Serge Fehr and anonymous reviewers on an earlier version of this manuscript for pointing out the additional required conditions on Bob's boxes.

This work was prepared while S. K. was at the Centre for Quantum Technologies (National University of Singapore), supported by the National Research Foundation, including under NRF RF Award No. NRF-NRFF2013-13, the Prime Minister's Office, Singapore; the Ministry of Education, Singapore, under the Research Centres of Excellence program and by Grant No. MOE2012-T3-1-009; and in part by the NRF2017-NRF-ANR004 VanQuTe Grant.
E. Y.-Z. T. was at the Institute for Theoretical Physics (ETH Zürich), supported by the Swiss National Science Foundation via the National Center for Competence in Research for Quantum Science and Technology (QSIT), the Air Force Office of Scientific Research (AFOSR) via grant FA9550-19-1-0202, and the QuantERA project eDICT.

[1]
Nati Aharon, André Chailloux, Iordanis Kerenidis, Serge Massar, Stefano
Pironio, and Jonathan Silman.
Weak coin flipping in a device-independent setting.
In Theory of Quantum Computation, Communication, and
Cryptography, pages 1–12, 2014.

[2]
Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and
Thomas Vidick.
Practical device-independent quantum cryptography via entropy
Nature Communications, 9(1):459, 2018.

[3]
Nati Aharon, Serge Massar, Stefano Pironio, and Jonathan Silman.
Device-independent bit commitment based on the CHSH inequality.
New Journal of Physics, 18(2):025014, 2016.

[4]
Charles H. Bennett and Gilles Brassard.
Quantum cryptography: Public key distribution and coin tossing.
In Proceedings of International Conference on Computers,
Systems and Signal Processing, page 175, 1984.

[5]
Jonathan Barrett, Roger Colbeck, and Adrian Kent.
Memory Attacks on Device-Independent Quantum Cryptography.
Physical Review Letters, 110:010503, 2013.

[6]
Anne Broadbent and Rabib Islam.
Quantum encryption with certified deletion.
In Theory of Cryptography, pages 92–122, 2020.

[7]
Michael Ben-Or, Michał Horodecki, Debbie W. Leung, Dominic Mayers, and
Jonathan Oppenheim.
The universal composable security of quantum key distribution.
In Theory of Cryptography, pages 386–406, 2005.

[8]
Mohammad Bavarian, Thomas Vidick, and Henry Yuen.
Anchoring Games for Parallel Repetition.
<https://arxiv.org/abs/1509.07466>, 2015.

[9]
Mohammad Bavarian, Thomas Vidick, and Henry Yuen.
Hardness Amplification for Entangled Games via Anchoring.
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory
of Computing, STOC '17, page 303–316, 2017.

[10]
J. Lawrence Carter and Mark N. Wegman.
Universal classes of hash functions.
Journal of Computer and System Sciences, 18(2):143–154, 1979.

[11]
Honghao Fu and Carl A. Miller.
Local randomness: Examples and application.
Physical Review A, 97:032324, 2018.

[12]
Thomas Holenstein.
Parallel Repetition: Simplifications and the No-Signaling Case.
In Proceedings of the Thirty-Ninth Annual ACM Symposium on
Theory of Computing, STOC '07, page 411–419, 2007.

[13]
Rahul Jain and Srijita Kundu.
A Direct Product Theorem for One-Way Quantum Communication.
In Proceedings of the 36th IEEE Annual Computational Complexity
Conference (CCC 2021), pages 27:1–27:28, 2021.

[14]
Rahul Jain, Carl A. Miller, and Yaoyun Shi.
Parallel Device-Independent Quantum Key Distribution.
IEEE Transactions on Information Theory, 66(9):5567–5584,

[15]
Rahul Jain, Attila Pereszlényi, and Penghui Yao.
A Parallel Repetition Theorem for Entangled Two-Player One-Round
Games under Product Distributions.
In 2014 IEEE 29th Conference on Computational Complexity (CCC
'14), pages 209–216, 2014.

[16]
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick.
Entangled Games are Hard to Approximate.
In 2008 49th Annual IEEE Symposium on Foundations of Computer
Science, pages 447–456, 2008.

[17]
Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan.
A Device-Independent Protocol for XOR Oblivious Transfer.
In 15th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2020), volume 158 of Leibniz
International Proceedings in Informatics (LIPIcs), pages 12:1–12:15, 2020.

[18]
Norbert Lütkenhaus, Ashutosh S. Marwah, and Dave Touchette.
Erasable Bit Commitment from Temporary Quantum Trust.
<https://arxiv.org/abs/1910.13949>, 2020.

[19]
Ueli Maurer and Renato Renner.
Abstract Cryptography.
In The Second Symposium on Innovations in Computer Science, ICS
2011, pages 1–21. Tsinghua University Press, 2011.

[20]
Stefano Pironio, Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar,
and Valerio Scarani.
Device-independent quantum key distribution secure against
collective attacks.
New Journal of Physics, 11(4):045021, 2009.

[21]
Christopher Portmann and Renato Renner.
Cryptographic security of quantum key distribution.
<https://arxiv.org/abs/1409.3525v1>, 2014.

[22]
Anup Rao.
Parallel repetition in projection games and a concentration bound.
In Proceedings of the Fortieth Annual ACM Symposium on Theory of
Computing, STOC '08, page 1–10. Association for Computing Machinery, 2008.

[23]
Ran Raz.
A Parallel Repetition Theorem.
In Proceedings of the Twenty-Seventh Annual ACM Symposium on
Theory of Computing, page 447–456, 1995.

[24]
Renato Renner.
Security of Quantum Key Distribution.
PhD thesis, ETH Zürich, 2005.

[25]
Jonathan Silman, André Chailloux, Nati Aharon, Iordanis Kerenidis, Stefano
Pironio, and Serge Massar.
Fully distrustful quantum bit commitment and coin flipping.
Physical Review Letters, 106:220501, 2011.

[26]
Marco Tomamichel and Anthony Leverrier.
A largely self-contained and complete security proof for quantum key
Quantum, 1:14, 2017.

[27]
Dominique Unruh.
Revocable quantum timed-release encryption.
In Advances in Cryptology – EUROCRYPT 2014, pages 129–146,

[28]
Bart van der Vecht, Xavier Coiteaux-Roy, and Boris Škorić.
Can't Touch This: unconditional tamper evidence from short keys.
<https://arxiv.org/abs/2006.02476>, 2020.

[29]
Thomas Vidick.
Parallel DIQKD from parallel repetition.
<https://arxiv.org/abs/1703.08508>, 2017.

[30]
Vilasini Venkatesh, Christopher Portmann, and Lídia del Rio.
Composable security in relativistic quantum cryptography.
New Journal of Physics, 21(4):043057, 2019.

[31]
Stephen Wiesner.
Conjugate coding.
SIGACT News, 15(1):78–88, 1983.


# Measurement-free fault-tolerant logical zero-state encoding of the distance-
three nine-qubit surface code in a one-dimensional qubit array

Hayato Goto, Yinghao Ho, and Taro Kanao  Frontier Research Laboratory,
Corporate Research & Development Center, Toshiba Corporation, 1, Komukai
Toshiba-cho, Saiwai-ku, Kawasaki-shi, 212-8582, Japan

###### Abstract

Generation of logical zero states encoded with a quantum error-correcting code
is the first step for fault-tolerant quantum computation, but requires
considerably large resource overheads in general. To reduce such overheads, we
propose an efficient encoding method for the distance-three, nine-qubit
surface code and show its fault tolerance. This method needs no measurement,
unlike other fault-tolerant encoding methods. Moreover, this is applicable to
a one-dimensional qubit array. Observing these facts, we experimentally
demonstrate the logical zero-state encoding of the surface code using a
superconducting quantum computer on the cloud. To extend this method to larger
codes, we also investigate the concatenation of the surface code with itself,
resulting in a distance-nine, 81-qubit code. We numerically show that fault-
tolerant encoding of this large code can be achieved by appropriate error
detection. Thus, the proposed encoding method will provide a new way to low-
overhead fault-tolerant quantum computation.

##  I Introduction

Quantum computers are notoriously prone to errors due to decoherence and
nonideal gate operations. To suppress these errors and perform quantum
algorithms for, e.g., prime factoring [1, 2] and quantum chemistry
calculations [3, 4], fault-tolerant quantum computation (FTQC) using quantum
error-correcting codes [5, 6, 7, 8] is highly expected. However, the FTQC in
general requires large computational resource overheads [9, 10, 11], which is
the case even for the first step in FTQC, namely, preparation of logical zero
states encoded with a quantum error-correcting code. Hence, the reduction of
such overheads for logical-qubit state preparation is highly desirable.

For example, an efficient fault-tolerant method for preparation of logical
qubit states has been proposed for the Steane seven-qubit code (one of the
smallest distance-three codes capable of correcting arbitrary single-qubit
errors) [12], which has allowed experimental realization of the Steane-code
logical qubit states, including so-called magic states [13, 14, 15, 16], using
laser-cooled trapped ions [17, 18]. However, the method still requires an
ancilla qubit and its measurement to achieve its fault tolerance.

In this paper, we propose an efficient fault-tolerant logical zero-state
encoding method for the nine-qubit surface code [19, 20], which is another
small distance-three code. Remarkably, this method needs no ancilla qubit and
no measurement [21, 22], which is in contrast to the conventional surface-code
encoding method repeating syndrome measurements realized in recent experiments
[23, 24, 25]. Moreover, the proposed method is applicable to a one-dimensional
qubit array, which allows us to experimentally demonstrate this method using a
superconducting quantum computer on the cloud.

To extend the proposed method to larger codes, we also investigate the
distance-nine, 81-qubit code obtained by concatenating the nine-qubit surface
code with itself. We numerically show that fault-tolerant logical zero-state
encoding of this large code can be achieved by three level-1 error-detecting
teleportations [26, 27, 28], where soft-decision decoding based on conditional
probability calculations [28, 29, 30] is essential for high performance.
Because of the assumption of arbitrary two-qubit gates, the experimental
realization of this encoding of the large code is challenging for
superconducting quantum computers, but will be possible for recently developed
neutral-atom quantum computers using optical tweezers [31, 32].

##  II Measurement-free fault-tolerant logical zero-state encoding of the
nine-qubit surface code

The proposed encoding method for the nine-qubit surface code is summarized in
Fig. 1, where Fig. 1a shows the definition of the code, Figs. 1b and 1c show
the proposed method, and Fig. 1d shows how the stabilizers of the nine-qubit
state change during the encoding. (An $n$-qubit stabilizer state is described
as a simultaneous eigenstate of $n$ stabilizers with eigenvalues of 1 [5].)
The final stabilizers in Fig. 1d are exactly the same as those of the logical
zero state, $|0\rangle_{L}$, encoded with the nine-qubit surface code (see
Fig. 1a). This means that the proposed method can successfully encode
$|0\rangle_{L}$. Also note that this encoding needs no ancilla qubit and no
measurement, as mentioned above.

The fault tolerance of the method is explained as follows. At the end of Step
1 in Fig. 1c, the weights (the numbers of non-identity Pauli operators) of all
the nine stabilizers are two or three, as shown in Fig. 1d, which allows us to
regard any correlated $X$ and $Z$ errors induced by the six controlled-NOT
(CNOT) gates in Step 1 as single-qubit $X$ and $Z$ errors, respectively. (In
this work, we assume that correlated errors occur only by two-qubit gates.)
Hence, we have only to care correlated errors induced by the two CNOT gates in
Step 2. (A similar technique is used for the efficient encoding method for the
Steane code [12].) The correlated errors are $X_{2}X_{3}$ and $X_{7}X_{8}$,
which can be corrected by this code. (The $X_{2}X_{3}$ error can be found by
the flips of the two $Z$ stabilizers $Z_{1}Z_{2}Z_{5}Z_{6}$ and $Z_{3}Z_{4}$,
and the $X_{7}X_{8}$ error can also be found by the flips of $Z_{6}Z_{7}$ and
$Z_{4}Z_{5}Z_{8}Z_{9}$. Also, there are no correlated $Z$ errors, because
$|0\rangle_{L}$ has another stabilizer $Z_{L}$ and consequently the weights of
its $Z$ stabilizers are still two or three after Step 2, as shown in Fig. 1d.)
Thus, this encoding induces no uncorrelatable errors up to the first order of
physical error rates, which means its fault tolerance.

Figure 1: Measurement-free fault-tolerant logical zero-state encoding of the
nine-qubit surface code. a Definition of the nine-qubit surface code. $S_{Z}$
and $S_{X}$ denote its $Z$ stabilizers ($Z_{6}Z_{7}$, $Z_{1}Z_{2}Z_{5}Z_{6}$,
$Z_{4}Z_{5}Z_{8}Z_{9}$, $Z_{3}Z_{4}$) and $X$ stabilizers ($X_{1}X_{2}$,
$X_{2}X_{3}X_{4}X_{5}$, $X_{5}X_{6}X_{7}X_{8}$, $X_{8}X_{9}$), respectively.
${Z_{L}=Z_{1}Z_{2}Z_{3}}$ and ${X_{L}=X_{1}X_{6}X_{7}}$ are its logical Pauli
operators. The logical zero state $|0\rangle_{L}$ is the simultaneous
eigenstate of the eight stabilizers and $Z_{L}$ with eigenvalues of 1. b
Graphical description of the proposed method. Bold circles indicate that the
corresponding qubits are initialized to
${|+\rangle=H|0\rangle=(|0\rangle+|1\rangle)/\sqrt{2}}$, where $H$ denotes the
Hadamard gate, and the others are to $|0\rangle$. Two bold CNOT gates in red
are performed after the other six CNOT gates. c Quantum circuit corresponding
to b. d Nine stabilizers describing the nine-qubit state at the end of each
step in c.

##  III Experimental demonstration of the proposed surface-code encoding

Figure 2: Qubit layout of the superconducting quantum computer used in this work. This is 27-qubit ibm-kawasaki [33]. Qubits 26,25,22,19,16,14,13,12, and 10 in this machine are used for Qubits 1–9 in Fig. 1. Table 1: CNOT-gate perfomance of 27-qubit ibm-kawasaki. “CNOT” column shows the control-qubit (C) and target-qubit (T) numbers of this machine (see Fig. 2). CNOT | Error rate (%) | Gate time (ns)
---|---|---
C26, T25 | 0.69 | 576
C25, T22 | 0.66 | 284
C22, T19 | 0.66 | 281
C19, T16 | 0.89 | 295
C16, T14 | 0.67 | 295
C14, T13 | 0.46 | 277
C13, T12 | 0.53 | 441
C12, T10 | 0.55 | 299
Table 2: Qubit coherence of 27-qubit ibm-kawasaki. “Qubit” column shows the qubit number of this machine (see Fig. 2). Qubit |  $T_{1}$ ($\mu$s) |  $T_{2}$ ($\mu$s)
---|---|---
Q26 | 76 | 140
Q25 | 238 | 66
Q22 | 107 | 196
Q19 | 161 | 272
Q16 | 78 | 82
Q14 | 93 | 97
Q13 | 173 | 35
Q12 | 135 | 55
Q10 | 108 | 27

Observing that the proposed encoding can be realized using a one-dimensional
qubit array, as shown in Fig. 1b, we did experiments of this encoding using a
superconducting quantum computer on the cloud (27-qubit ibm-kawasaki [33]),
the qubit layout of which is shown in Fig. 2. The performance of this machine
is summarized in Tables 1 and 2. We used nine qubits in a row among the 27
qubits, which are highlighted in Fig. 2.

First, we prepare $|0\rangle_{L}$ according to the quantum circuit in Fig. 1c,
and measure $Z$ of all the qubits after a delay time from the preparation. We
decode the measurement results using the hard-decision decoding rule in
Appendix A, and estimate the measurement result of $Z_{L}$. If the decoding
leads to ${Z_{L}=1}$, the decoding succeeds. Otherwise, the decoding fails,
which means a logical error.

Figure 3a shows the experimental results of the logical error probability
$p_{L}$ (circles) and the no-$X$-error probability (squares), $p_{Z}$, that
all the measurement results of $Z_{L}$ and the four $Z$ stabilizers are 1. The
fact that $p_{L}$ is substantially lower than ${1-p_{Z}}$ means the success of
the error correction. When the delay time is zero, the logical error
probability is about 0.5%, which is lower than single-CNOT error rates (see
Table 1). This also indicates that $|0\rangle_{L}$ was successfully prepared
and the logical error probability was suppressed by error correction.

Note that the above results depend only on $Z$ measurements (meaturements of
bit-string states) and provide no information of $X$ measurements (quantum
superpositions of bit-string states). The logical zero state, $|0\rangle_{L}$,
encoded with the nine-qubit surface code is a quantum superposition of 16 bit-
string states satisfying the five $Z$-stabilizer conditions. To evaluate the
quantum superposition in the prepared $|0\rangle_{L}$, we also measured the
$X$ stabilizers, the results of which are shown by squares in Fig. 3b. When
the delay time is zero, the no-$Z$-error probability, $p_{X}$, that all the
measurement results of the four $X$ stabilizers are 1 is 68%. (The
corresponding value of $p_{Z}$ is 85%, as found in Fig 3a.) This result
suggests that the prepared $|0\rangle_{L}$ was actually a quantum
superposition of bit-string states, as expected. In fact, it is shown that the
fidelity of the prepared $|0\rangle_{L}$ is lower bounded by
${p_{Z}+p_{X}-1=0.53}$ (see Appendix C), which is substantially higher than
that for the maximally mixed state of the 16 bit-string states, namely,
${1/16=0.0625}$. (This fidelity evaluation of $|0\rangle_{L}$ prepared by the
proposed method would be useful for benchmarking of real quantum computers.)

It is notable that $p_{X}$ decays more rapidly than $p_{Z}$. (The recovery of
$p_{X}$ to ${1/16=0.0625}$ found in Fig. 3b can be explained by qubit-state
convergence to ground states after a sufficiently long time.) Since this decay
of $p_{X}$ is too fast compared to qubit coherence times (see Table 2), the
decay may be caused by another decoherence source. We identify it with so-
called residual $ZZ$ coupling inducing unwanted additional phase rotation only
for $|11\rangle$ of adjacent qubits. To suppress this dephasing due to the
$ZZ$ coupling, we applied a dynamical decoupling technique shown in Fig. 4.
(Similar studies with different techniques have been reported [34, 35].) The
results are shown by circles in Fig. 3b, which clearly shows that the decay of
$p_{X}$ becomes substantially slower, as expected. This concludes that the
rapid decay of $p_{X}$ is due to the $ZZ$ coupling in this machine, and this
can be suppressed by the proposed dynamical decoupling technique shown in Fig.
4.

Figure 3: Experimental results of the logical zero-state encoding of the nine-
qubit surface code using a superconducting quantum computer on the cloud. a
Delay-time dependence of the logical error probability $p_{L}$ (circles) and
the no-X-error probability $p_{Z}$ (squares) that all the measurement results
of $Z_{L}$ and the four $Z$ stabilizers are 1. b Delay-time dependence of the
no-$Z$-error probability $p_{X}$ that all the measurement results of the four
$X$ stabilizers are 1. The circles and squares show the results, respectively,
with and without the dynamical decoupling (DD) technique shown in Fig. 4. In
both a and b, statistical errors are negligible compared to symbol sizes.
Figure 4: Dynamical decoupling technique for suppressing dephasing in
$|0\rangle_{L}$ due to $ZZ$ coupling. Each dynamical decoupling (DD) cycle
consists of four 0.5-$\mu$s delay times (more precisely, 0.5013 $\mu$s)
followed by four or five $X$ gates with gate times of 36 ns (more precisely,
35.6 ns). Thus, each DD cycle takes 2.1476 $\mu$s. It can easily be shown that
this DD cycle can eliminate unwanted additional phase rotations due to $ZZ$
coupling.

##  IV Fault-tolerant logical zero-state encoding of the concatenated nine-
qubit surface code

The proposed encoding method is applicable only to the distance-three, nine-
qubit surface code, which is small for practical applications [9, 10, 11]. To
extend the proposed method to larger codes, we consider the concatenation of
the nine-qubit surface code with itself [5], which leads to the distance-nine,
81-qubit code.

The logical zero state, $|0\rangle_{L2}$, encoded with the concatenated code
can be generated straightforwardly by the quantum circuit in Fig. 1c, where
the physical zero states, physical Hadamard gates, and physical CNOT gates
are, respectively, replaced by the encoded zero states $|0\rangle_{L1}$,
encoded Hadamard gates, and encoded CNOT gates for the nine-qubit surface
code, where the subscripts $L2$ and $L1$ denote the concatenation levels [26,
27, 28]. The fault-tolerant preparation of $|0\rangle_{L1}$ can be done by the
proposed method explained in Sec. II. The encoded Hadamard gate can be
implemented fault-tolerantly by the transversal Hadamard gate [5],
${H_{1}H_{2}H_{3}H_{4}H_{5}H_{6}H_{7}H_{8}H_{9}}$, followed by renumbering
($90^{\circ}$ rotating) the qubits as ${1\to 7}$, ${2\to 6}$, ${3\to 1}$,
${4\to 2}$, ${9\to 3}$, ${8\to 4}$, ${7\to 9}$, and ${6\to 8}$. The encoded
CNOT gate can also be implemented fault-tolerantly by the transversal CNOT
gate [5, 19].

To evaluate the performance of the straightforward encoding of
$|0\rangle_{L2}$, we numerically simulate it and evaluate its logical error
probability $p_{L2}$ using $Z$ measurement results. This simulation is based
on the stabilizer simulation [36]. In this simulation, we assume the error
model where errors occur only in physical CNOT gates, which is modeled in a
standard manner, that is, a physical CNOT gate is modeled by an ideal CNOT
gate followed by one of 15 two-qubit Pauli errors with equal probability of
$p_{\mathrm{CNOT}}/15$ [26, 27, 28]. For the decoding of the concatenated
code, we use soft-decision decoding based on conditional probability
calculations [28, 29, 30] (see Appendix B), which is important to achieve
almost optimal performance.

Figure 5: Simulation results of the logical zero-state encoding of the
concatenated code. a Logical error probabilities. The circles, triangles,
squares, and crosses show, respectively, the results for encoding without
error-detecting teleportations (EDTs), with an EDT on the level-1 Qubit 5,
with EDTs on the level-1 Qubits 2 and 8, and with EDTs on the level-1 Qubits
2, 5, and 8. The dotted lines and proportionality relations show fitting
results with a power function. The number of repetition to estimate the
probabilities is $10^{8}$ for “No EDT” and “EDT5” and $10^{10}$ for “EDT28”
and “EDT258.” b Average total number of encoding until success. The dotted
lines are eye guides. In both a and b, statistical errors are negligible
compared to symbol sizes, except for “EDT258” in a.

The simulation results are shown by circles in Fig. 5a. Although the logical
error probability can become lower than the physical error probability, its
exponent of about 3 is smaller than that expected from the code distance of 9,
namely, 5. (In general, distance-nine codes can, in principle, correct four
arbitrary independent qubit errors, leading to the exponent of 5.)

To improve the performance, error detection followed by postselection
(restarting from the beginning if errors are detected until no errors are
detected) is effective. We perform level-1 error-detecting teleportations
(EDTs) [26, 27, 28] on the level-1 Qubits 2, 5, and/or 8 after the above
straightforward generation of $|0\rangle_{L2}$. The simulation results are
shown in Fig 5a. When the EDT is performed only on Qubit 5, the logical error
probability becomes lower, but the exponent is still about 3. When the EDT is
performed on Qubits 2 and 8, the logical error probability is reduced by two
orders of magnitude, and also the exponent is increased to about 4 but still
smaller than 5. When the EDT is performed on Qubits 2, 5 and 8, not only the
logical error probability becomes further lower, but also the exponent exceeds
5. (Note that the hard-decision decoding for the concatenated code can, in
principle, achieve the exponent up to 4, and therefore the present result
achieving the exponent of 5 clearly shows the advantage of the soft-decision
decoding.) Thus, it has turned out that EDTs on Qubits 2, 5, and 8 are enough
to achieve potential performance of the concatenated code. In this case, the
logical error probability is estimated around $10^{-11}$ for
${p_{\mathrm{CNOT}}=10^{-3}}$, which is sufficiently low for large-scale
problems. Figure 5b also shows that the increase of overheads by the EDTs and
postselection will not be very large.

##  V Conclusion

We have proposed a measurement-free fault-tolerant logical zero-state encoding
method for the distance-three, nine-qubit surface code, and have
experimentally demonstrated it using a superconducting quantum computer on the
cloud. We have also proposed a fault-tolerant logical zero-state encoding
method for the distance-nine, 81-qubit code obtained by concatenating the
nine-qubit surface code with itself. Because of the assumption of arbitrary
two-qubit gates, this large-scale encoding is challenging for superconducting
quantum computers, but will be possible for recently developed neutral-atom
quantum computers with optical tweezers. Thus, the present results will
provide a new way to low-overhead fault-tolerant quantum computation.

## Acknowledgments

We acknowledge the use of IBM Quantum services for experiments in this work.
The views expressed are those of the authors, and do not reflect the official
policy or position of IBM or the IBM Quantum team. The use of IBM’s
superconducting quantum computer on the cloud was supported by UTokyo Quantum
Initiative.

##  Appendix A Hard-decision decoding of the nine-qubit surface code

Using the results of the $Z$ measurements of $|0\rangle_{L}$, we estimate the
$X$ errors as follows. We first calculate the measurement results of the $Z$
stabilizers as

$\displaystyle s_{1}$ $\displaystyle=m_{6}m_{7},$ (1) $\displaystyle s_{2}$
$\displaystyle=m_{1}m_{2}m_{5}m_{6},$ (2) $\displaystyle s_{3}$
$\displaystyle=m_{4}m_{5}m_{8}m_{9},$ (3) $\displaystyle s_{4}$
$\displaystyle=m_{3}m_{4},$ (4)

where $m_{j}$ denotes the measurement result of $Z_{j}$. Next, we estimate the
$X$ errors according to Table 3. Finally, we flip the measurement results
$\\{m_{j}\\}$ according to the estimated $X$ errors. Then, the value of
$Z_{L}$ is estimated at $m_{1}m_{2}m_{3}$ after the flips.

Table 3: $X$-error estimation from $Z$ measurement results. Measurement results of the $Z$ stabilizers, $s_{1}$–$s_{4}$, are defined by Eqs. (1)–(4). $s_{1}$ | $s_{2}$ | $s_{3}$ | $s_{4}$ |  $X$ errors
---|---|---|---|---
$+1$ | $+1$ | $+1$ | $+1$ | No error
$-1$ | $+1$ | $+1$ | $+1$ | $X_{7}$
$+1$ | $-1$ | $+1$ | $+1$ | $X_{2}$
$+1$ | $+1$ | $-1$ | $+1$ | $X_{8}$
$+1$ | $+1$ | $+1$ | $-1$ | $X_{3}$
$-1$ | $-1$ | $+1$ | $+1$ | $X_{6}$
$-1$ | $+1$ | $-1$ | $+1$ | $X_{7}X_{8}$
$-1$ | $+1$ | $+1$ | $-1$ | $X_{3}X_{7}$
$+1$ | $-1$ | $-1$ | $+1$ | $X_{5}$
$+1$ | $-1$ | $+1$ | $-1$ | $X_{2}X_{3}$
$+1$ | $+1$ | $-1$ | $-1$ | $X_{4}$
$-1$ | $-1$ | $-1$ | $+1$ | $X_{5}X_{7}$
$-1$ | $-1$ | $+1$ | $-1$ | $X_{3}X_{6}$
$-1$ | $+1$ | $-1$ | $-1$ | $X_{4}X_{7}$
$+1$ | $-1$ | $-1$ | $-1$ | $X_{3}X_{5}$
$-1$ | $-1$ | $-1$ | $-1$ | $X_{4}X_{6}$

##  Appendix B Soft-decision decoding of the concatenated nine-qubit surface
code

First, the soft-decision decoding rule for the nine-qubit surface code is
given as follows [28, 30]:

$\displaystyle P^{(1)}(z)$
$\displaystyle=\frac{R^{(1)}(z)}{R^{(1)}(1)+R^{(1)}(-1)},$ (5) $\displaystyle
R^{(1)}(z)$ $\displaystyle=\sum_{z_{1}=\pm 1}\sum_{z_{2}=\pm 1}\sum_{z_{3}=\pm
1}\sum_{z_{4}=\pm 1}\sum_{z_{5}=\pm 1}\sum_{z_{6}=\pm 1}\sum_{z_{7}=\pm
1}\sum_{z_{8}=\pm 1}\sum_{z_{9}=\pm
1}P_{1}^{(0)}(z_{1})P_{2}^{(0)}(z_{2})P_{3}^{(0)}(z_{3})P_{4}^{(0)}(z_{4})P_{5}^{(0)}(z_{5})P_{6}^{(0)}(z_{6})$
$\displaystyle\times
P_{7}^{(0)}(z_{7})P_{8}^{(0)}(z_{8})P_{9}^{(0)}(z_{9})\delta({z_{1}z_{2}z_{3}=z})\delta({z_{6}z_{7}=1})\delta({z_{1}z_{2}z_{5}z_{6}=1})\delta({z_{4}z_{5}z_{8}z_{9}=1})\delta({z_{3}z_{4}=1}),$
(6)

where $P^{(1)}(z)$ is the probability that the level-1 $Z_{L}$ has the value
of $z$, $R^{(1)}(z)$ is the corresponding relative probability, $z_{j}$
denotes the correct value of $Z_{j}$ for the $j$th physical qubit,
$P_{j}^{(0)}(z_{j})$ is the corresponding probability, and the
$\delta(\textrm{condition})$ is the indicator function taking 1 if the
condition is true and otherwise 0. Assuming equal physical-qubit error
probability of $p_{e}$, we have

$\displaystyle P_{j}^{(0)}(m_{j})=1-p_{e},~{}P_{j}^{(0)}(-m_{j})=p_{e},$ (7)

where $m_{j}$ is the measurement result of $Z_{j}$. In this work, we set
$p_{e}$ to 0.01. (The soft-decision decoding is insensitive to the setting of
$p_{e}$ [28].) Thus, we can obtain $P^{(1)}(z)$ using the measurement results
$\\{m_{j}\\}$.

Next, the soft-decision decoding rule for the concatenated code is given
similarly as follows [28, 30]:

$\displaystyle P^{(2)}(z)$
$\displaystyle=\frac{R^{(2)}(z)}{R^{(2)}(1)+R^{(2)}(-1)},$ (8) $\displaystyle
R^{(2)}(z)$ $\displaystyle=\sum_{z_{1}=\pm 1}\sum_{z_{2}=\pm 1}\sum_{z_{3}=\pm
1}\sum_{z_{4}=\pm 1}\sum_{z_{5}=\pm 1}\sum_{z_{6}=\pm 1}\sum_{z_{7}=\pm
1}\sum_{z_{8}=\pm 1}\sum_{z_{9}=\pm
1}P_{1}^{(1)}(z_{1})P_{2}^{(1)}(z_{2})P_{3}^{(1)}(z_{3})P_{4}^{(1)}(z_{4})P_{5}^{(1)}(z_{5})P_{6}^{(1)}(z_{6})$
$\displaystyle\times
P_{7}^{(1)}(z_{7})P_{8}^{(1)}(z_{8})P_{9}^{(1)}(z_{9})\delta({z_{1}z_{2}z_{3}=z})\delta({z_{6}z_{7}=1})\delta({z_{1}z_{2}z_{5}z_{6}=1})\delta({z_{4}z_{5}z_{8}z_{9}=1})\delta({z_{3}z_{4}=1}),$
(9)

where $P^{(2)}(z)$ is the probability that the level-2 $Z_{L}$ has the value
of $z$, $R^{(2)}(z)$ is the corresponding relative probability, $z_{j}$
denotes the correct value of the level-1 $Z_{L}$ for the $j$th level-1 encoded
qubit, $P_{j}^{(1)}(z_{j})$ is the corresponding probability obtained from the
measurement results as explained above.

Thus, we estimate the value of the level-2 $Z_{L}$ at 1 if
${P^{(2)}(1)>P^{(2)}(-1)}$, otherwise at $-1$.

##  Appendix C Fidelity estimation of the experimentally prepared
$|0\rangle_{L}$

The fidelity of the experimentally prepared $|0\rangle_{L}$ is formuated as
${F_{0}={{}_{L}\langle 0|\rho_{0}|0\rangle_{L}}}$, where $\rho_{0}$ denotes
the density operator describing the experimentally prepared $|0\rangle_{L}$.
In the following, we show that ${F_{0}\geq p_{Z}+p_{X}-1}$.

Consider two bits, $b_{Z}$ and $b_{X}$, defined as ${b_{Z}=0}$ if all the five
$Z$ stabilizers of $|0\rangle_{L}$ are 1, otherwise ${b_{Z}=1}$, and
${b_{X}=0}$ if all the four $X$ stabilizers of $|0\rangle_{L}$ are 1,
otherwise ${b_{X}=1}$. We also denote the probability of $(b_{Z},b_{X})$ by
$P_{b}(b_{Z},b_{X})$. Then, we have ${F_{0}=P_{b}(0,0)}$,
${p_{Z}=P_{b}(0,0)+P_{b}(0,1)}$, and ${p_{X}=P_{b}(0,0)+P_{b}(1,0)}$. We also
have ${P_{b}(0,0)+P_{b}(1,0)+P_{b}(0,1)+P_{b}(1,1)=1}$. Using these relations,
we can easily obtain the desired result:

$\displaystyle F_{0}=p_{Z}+p_{X}-1+P_{b}(1,1)\geq p_{Z}+p_{X}-1.$ (10)

## References

  * [1] P. W. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994, (IEEE, 1994), p. 124.
  * [2] A. Ekert and R. Jozsa, Quantum Computation and Shor’s factoring algorithm, Rev. Mod. Phys. 68, 733–753 (1996).
  * [3] A. Aspuru-Guzik, A. D. Dutoi, P. J. Lovec, and M. Head-Gordona, Simulated Quantum Computation of Molecular Energies, Science 309, 1704–1707 (2005).
  * [4] S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Quantum computational chemistry, Rev. Mod. Phys. 92, 015003 (2020).
  * [5] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge Univ. Press, Cambridge, 2000).
  * [6] P. W. Shor, Fault-tolerant quantum computation, in Proc. 37th Symp. on Foundations of Computer Science 56–65 (IEEE Computer Soc. Press, Los Alamitos, CA, 1996).
  * [7] D. Gottesman, Theory of fault-tolerant quantum computation, Phys. Rev. A 57, 127 (1998).
  * [8] E. Knill, R. Laflamme, and W. H. Zurek, Resilient Quantum Computation, Science 279, 342 (1998).
  * [9] N. C. Jones, R. Van Meter, A. G. Fowler, P. L. McMahon, J. Kim, T. D. Ladd, and Y. Yamamoto, Layered Architecture for Quantum Computing, Phys. Rev. X 2, 031007 (2012).
  * [10] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012).
  * [11] C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021).
  * [12] H. Goto, Minimizing resource overheads for fault-tolerant preparation of encoded states of the Steane code, Sci. Rep. 6, 19578 (2016).
  * [13] S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas, Phys. Rev. A 71, 022316 (2005).
  * [14] B. W. Reichardt, Quantum Universality from Magic States Distillation Applied to CSS Codes, Quant. Inf. Proc. 4, 251–264 (2005).
  * [15] H. Goto, Step-by-step magic state encoding for efficient fault-tolerant quantum computation, Sci. Rep. 4, 7501 (2014).
  * [16] C. Chamberland and A. W. Cross, Fault-tolerant magic state preparation with flag qubits, Quantum 3, 143 (2019).
  * [17] C. Ryan-Anderson, J. G. Bohnet, K. Lee, D. Gresh, A. Hankin, J. P. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. C. Brown, T. M. Gatterman, S. K. Halit, K. Gilmore, J. A. Gerber, B. Neyenhuis, D. Hayes, and R. P. Stutz, Realization of Real-Time Fault-Tolerant Quantum Error Correction, Phys. Rev. X 11, 041058 (2021).
  * [18] L. Postler, S. Heußen, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, P. Schindler, M. Müller, and T. Monz, Demonstration of fault-tolerant universal quantum gate operations, Nature 605, 675–680 (2022).
  * [19] C. Horsman, A. G Fowler, S. Devitt, and R. Van Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14, 123011 (2012).
  * [20] Y. Tomita and K. M. Svore, Low-distance surface codes under realistic quantum noise, Phys. Rev. A 90, 062320 (2014).
  * [21] We have recently found a similar encoding method in Ref. 22. However, its fault tolerance has not been shown.
  * [22] K. J. Satzinger et al., Realizing topologically ordered states on a quantum processor , Science 374, 1237–1241 (2021).
  * [23] Y. Zhao et al., Realization of an Error-Correcting Surface Code with Superconducting Qubits, Phys. Rev. Lett. 129, 030501 (2022).
  * [24] S. Krinner et al., Realizing repeated quantum error correction in a distance-three surface code, Nature 605, 669–674 (2022).
  * [25] Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit, Nature 614, 676–681 (2023).
  * [26] E. Knill, Quantum computing with realistically noisy devices, Nature 434, 39–44 (2005).
  * [27] H. Goto and K. Ichimura, Fault-tolerant quantum computation with probabilistic two-qubit gates, Phys. Rev. A 80, 040303(R) (2009).
  * [28] H. Goto and H. Uchikawa, Fault-tolerant quantum computation with a soft-decision decoder for error correction and detection by teleportation, Sci. Rep. 3, 2044 (2013).
  * [29] D. Poulin, Optimal and efficient decoding of concatenated quantum block codes, Phys. Rev. A 74, 052333 (2006).
  * [30] H. Goto and H. Uchikawa, Soft-decision decoder for quantum erasure and probabilistic-gate error models, Phys. Rev. A 89, 022322 (2014).
  * [31] D. Bluvstein et al., A quantum processor based on coherent transport of entangled atom arrays, Nature 604, 451–456 (2022).
  * [32] T. M. Graham et al., Multi-qubit entanglement and algorithms on a neutral-atom quantum computer, Nature 604, 457–462 (2022).
  * [33] IBM Q: https://quantum-computing.ibm.com/
  * [34] B. Pokharel, N. Anand, B. Fortman, and D. A. Lidar, Demonstration of Fidelity Improvement Using Dynamical Decoupling with Superconducting Qubits, Phys. Rev. Lett. 121, 220502 (2018).
  * [35] V. Tripathi, H. Chen, M. Khezri, K.-W. Yip, E. M. Levenson-Falk, and D. A. Lidar, Suppression of Crosstalk in Superconducting Qubits Using Dynamical Decoupling, Phys. Rev. Appl. 18, 024068 (2022).
  * [36] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004).