Good implies correct: an extended rectangle with at most t faults is correct

Setting. A fault-tolerant protocol $P$ consists of the following data:

• natural numbers $n$ (block length), $t$ (correctable faults) and $A$ (ancillas per block);
• a subspace $\mathcal C\subseteq\mathbb C^{2^n}$ (the code);
• an encoding matrix $\mathrm{enc}\in\mathbb C^{2^n\times 2}$;
• a decoder $\mathrm{dec}$, an arbitrary map from $n$-qubit operators to $1$-qubit operators;
• for each location kind $\kappa\in\{\text{prep},H,T,\mathrm{CNOT},\text{meas},\text{wait}\}$, a gadget circuit $G_\kappa$ on $a_\kappa(n+A)$ physical qubits, where the arity is $a_\kappa=2$ for CNOT and $1$ otherwise;
• an error-correction circuit $G_{\mathrm{EC}}$ on $n+A$ qubits;
• a classical decoding function $\mathrm{md}$ from bit lists to bits.

In each block, the first $n$ wires are data and the last $A$ are ancillas.

Pauli fault arrangements. A Pauli fault arrangement $f$ assigns to each location id $(s,j)$ either nothing or a pair $(P,Q)$ of single-qubit Paulis from $\{I,X,Y,Z\}$. Running a gadget under $f$ works as follows:

• At each location where $f$ gives $(P,Q)$, the state is conjugated by $P$ on the location's first wire and by $Q$ on its remaining wire (if any).
• This conjugation is applied after the location's ideal action, but before the measurement for measurement locations.
• Ids that are not locations are ignored.
• Classically controlled gate locations act only when their condition, read on earlier-step outcomes, is true.

We write $\#_G(f)$ for the number of locations of $G$ at which $f$ places a pair. A pair $(I,I)$ counts.

Derived maps.

• $\mathrm{Gate}_{\kappa,f}$. Put an operator $X$ on the data qubits of $a_\kappa$ blocks, with all ancillas in $|0\rangle\langle 0|$. Run $G_\kappa$ under $f$, add the resulting unnormalized states over all measurement records, and trace out the ancillas.
• $\mathrm{EC}_f$. The same construction with $G_{\mathrm{EC}}$ on one block.
• $\mathrm{Prep}_f$. The $n$-qubit operator obtained by running $G_{\text{prep}}$ from the all-zero state in the same way.
• $\mathrm{Meas}^\beta_f(\rho)$. The complex number obtained by running $G_{\text{meas}}$ on $\rho$ (ancillas zero) and taking the trace of the sum over those records $r$ with $\mathrm{md}(r)=\beta$.
• $\mathcal F_r$. The map $\rho\mapsto\Pi_r\rho\Pi_r$, where $\Pi_r$ is the orthogonal projector onto the span of $\{Pc : P \text{ a Pauli string of weight}\le r,\ c\in\mathcal C\}$. The weight of a Pauli string is the number of its non-identity factors.
• $\bigotimes_i\Phi_i$. The linear extension of the tensor product of superoperators.
• $U_\kappa$. The ideal unitary: $H$, $T=\mathrm{diag}(1,e^{i\pi/4})$, CNOT (first wire is the control), or $I$ for wait. We write $\mathcal U_\kappa(\rho)=U_\kappa\rho U_\kappa^\dagger$.

The fault-tolerance hypothesis $h_P$. It states all of the following.

1. Code. $\dim_{\mathbb C}\mathcal C=2$. Every $n$-qubit operator of the form $M\otimes I$ supported on at most $2t$ qubits is detectable: there is a constant $c$ with $\langle\psi,E\psi\rangle=c$ for all unit $\psi\in\mathcal C$.
2. Encoding. $\mathrm{enc}^\dagger\mathrm{enc}=I_2$ and $\operatorname{range}(\mathrm{enc})=\mathcal C$.
3. Ideal decoder. $\mathrm{dec}$ is a channel, i.e. it has finitely many Kraus operators with $\sum_j K_j^\dagger K_j=I$. Moreover, for every $E$ in the complex span of Pauli strings of weight $\le t$ and every unit $\psi\in\mathbb C^2$,

$$\mathrm{dec}\big(|E\,\mathrm{enc}\,\psi\rangle\langle E\,\mathrm{enc}\,\psi|\big)=\|E\,\mathrm{enc}\,\psi\|^2\,|\psi\rangle\langle\psi| .$$

4. Well-formedness. The live-qubit flows of the gadgets are:

   • prep gadget: from no live qubits to exactly the block's data qubits;
   • meas gadget: from data qubits to none;
   • gate, wait and EC gadgets: from data qubits to data qubits.

   Well-formed means:

   • in each step, locations act on disjoint qubits;
   • every live qubit is touched in the step;
   • preparations act only on non-live qubits and all other locations only on live qubits;
   • preparations add qubits to the live set and measurements remove them;
   • the final live set is as stated.

5. Fault properties. Whenever the fault counts allow it:

   • Meas. If $r+\#_{G_{\text{meas}}}(f)\le t$, then $\mathrm{Meas}^\beta_f(\mathcal F_r\rho)=\mathrm{dec}(\mathcal F_r\rho)_{\beta\beta}$ for all $\beta,\rho$.
   • Prep A. If $\#(f)\le t$, then $\mathcal F_{\#(f)}(\mathrm{Prep}_f)=\mathrm{Prep}_f$.
   • Prep B. If $\#(f)\le t$, then $\mathrm{dec}(\mathrm{Prep}_f)=|0\rangle\langle0|$.
   • Gate A. For gate/wait $\kappa$ and $r_i$ with $\#+\sum_i r_i\le t$:

$$\textstyle(\bigotimes\mathcal F_{\#+\sum r_i})\circ\mathrm{Gate}_{\kappa,f}\circ\bigotimes_i\mathcal F_{r_i}=\mathrm{Gate}_{\kappa,f}\circ\bigotimes_i\mathcal F_{r_i}.$$

• Gate B. Under the same condition:

$$\textstyle(\bigotimes\mathrm{dec})\circ\mathrm{Gate}_{\kappa,f}\circ\bigotimes\mathcal F_{r_i}=\mathcal U_\kappa\circ(\bigotimes\mathrm{dec})\circ\bigotimes\mathcal F_{r_i}.$$

• EC A. If $\#(f)\le t$, then $\mathcal F_{\#(f)}\circ\mathrm{EC}_f=\mathrm{EC}_f$.
• EC B. If $r+\#(f)\le t$, then $\mathrm{dec}\circ\mathrm{EC}_f\circ\mathcal F_r=\mathrm{dec}\circ\mathcal F_r$.

ExRec fault data $F$. For a kind $\kappa$, $F$ consists of:

• leading arrangements $F^{\text{lead}}_i$, one per input block (none for prep);
• a gadget arrangement $F^{\text{gad}}$;
• trailing arrangements $F^{\text{trail}}_j$, one per output block (none for meas).

Its fault count with truncation set $\tau$ is

$$\textstyle\sum_i\#_{\mathrm{EC}}(F^{\text{lead}}_i)+\#_{G_\kappa}(F^{\text{gad}})+\sum_{j\notin\tau}\#_{\mathrm{EC}}(F^{\text{trail}}_j).$$

ExRec correctness with truncation $\tau$.

• prep: $\mathrm{dec}\big(\Phi(\mathrm{Prep}_{F^{\text{gad}}})\big)=|0\rangle\langle0|$, where $\Phi$ is the identity if $0\in\tau$ and $\mathrm{EC}_{F^{\text{trail}}_0}$ otherwise.
• meas: for both $\beta$, the identity $\mathrm{Meas}^\beta_{F^{\text{gad}}}\circ\mathrm{EC}_{F^{\text{lead}}_0}=\big(\rho\mapsto\mathrm{dec}(\mathrm{EC}_{F^{\text{lead}}_0}\rho)_{\beta\beta}\big)$ holds. This ignores $\tau$.
• gate/wait:

$$\textstyle(\bigotimes\mathrm{dec})\circ\mathrm{Tr}\circ\mathrm{Gate}_{\kappa,F^{\text{gad}}}\circ\bigotimes_i\mathrm{EC}_{F^{\text{lead}}_i}=\mathcal U_\kappa\circ(\bigotimes\mathrm{dec})\circ\bigotimes_i\mathrm{EC}_{F^{\text{lead}}_i}.$$

Here $\mathrm{Tr}=\bigotimes_j\Phi_j$, with $\Phi_j=\mathrm{id}$ for $j\in\tau$ and $\Phi_j=\mathrm{EC}_{F^{\text{trail}}_j}$ otherwise.

Statement. For every protocol $P$ satisfying $h_P$, every kind $\kappa$, and every ExRec fault data $F$ whose fault count with empty truncation is at most $t$:

$$\textstyle\sum_i\#_{\mathrm{EC}}(F^{\text{lead}}_i)+\#_{G_\kappa}(F^{\text{gad}})+\sum_j\#_{\mathrm{EC}}(F^{\text{trail}}_j)\le t,$$

the ExRec for $\kappa$ is correct with empty truncation. In particular:

• for prep, the trailing EC is always applied;
• for gates, every trailing EC is applied.