A fault-tolerant circuit simulates the ideal circuit with errors at the bad ExRecs

Data. The statement takes:

• a fault-tolerant protocol $P$;
• a circuit $C$ of locations on $N$ wires;
• an arbitrary Pauli fault arrangement $f\!a$;
• a natural number $\sigma$;
• a complex matrix $W$ with rows indexed by $\{0,1\}\times\{0,\dots,\sigma-1\}$ and columns indexed by $n$-bit strings.

The protocol $P$. It consists of:

• natural numbers $n, t, A$;
• a subspace $\mathcal C\subseteq\mathbb C^{2^n}$, the code;
• a $2^n\times 2$ matrix $\mathrm{enc}$;
• a superoperator $\mathcal D$ from $n$-qubit matrices to $2\times 2$ matrices, the decoder;
• for each location kind $\kappa\in\{\text{prep},H,T,\text{CNOT},\text{meas},\text{wait}\}$, a gadget circuit $G_\kappa$ on $\mathrm{ar}(\kappa)(n+A)$ wires, where $\mathrm{ar}(\text{CNOT})=2$ and the other kinds have arity $1$;
• an error-correction circuit $G_{ec}$ on $n+A$ wires;
• a classical decoding map $\mathrm{measDecode}$ from bit lists to bits.

Block $i$, position $j$ is wire $i(n+A)+j$. Positions $j<n$ are data wires and the rest are ancillas.

Fault semantics. A Pauli fault arrangement assigns to some location ids $\ell=(s,j)$ a pair of Paulis $(P_1,P_2)$. At a location of the circuit, it acts as conjugation by the Pauli string that has $P_1$ on the location's first wire and $P_2$ on its others. This Pauli acts after the location's ideal action, or before it at a measurement. The faults carry a trivial one-dimensional environment.

For any $f\!a$, write $f(G,f\!a)$ for the number of locations of $G$ at which $f\!a$ is defined. Every gadget superoperator is computed the same way:

1. the input is placed on the data wires with all ancillas in $|0\rangle$;
2. the gadget is run with these Pauli faults;
3. the outputs are summed over all measurement records;
4. the ancillas are traced out.

This yields the following superoperators:

• $\mathrm{gateOp}_\kappa(f\!a)$ on $\mathrm{ar}(\kappa)$ blocks;
• $\mathrm{ecOp}(f\!a)$ on one block;
• the matrix $\mathrm{prep}(f\!a)$, obtained by starting from $|0\cdots0\rangle$ on all wires;
• the functional $\mathrm{measF}(f\!a,\beta)(\rho)$, the trace of the meas-gadget output summed only over records $r$ with $\mathrm{measDecode}(r)=\beta$.

Let $\mathcal F_r$ be conjugation by the orthogonal projection onto $\mathrm{span}\{Pc : P \text{ a Pauli string of weight}\le r,\ c\in\mathcal C\}$. Let $\bigotimes$ denote the tensor product of superoperators, defined on matrix units and extended linearly.

Hypothesis "$P$ is fault tolerant". All of the following hold:

1. $\dim\mathcal C=2$. Every operator acting nontrivially on at most $2t$ qubits is detectable: $\langle\psi|E\psi\rangle$ is the same constant for all unit $\psi\in\mathcal C$.
2. $\mathrm{enc}^\dagger\mathrm{enc}=I_2$ and $\operatorname{range}(\mathrm{enc})=\mathcal C$.
3. $\mathcal D$ is a channel with a finite Kraus family satisfying $\sum K_j^\dagger K_j=I$. For every $E$ in the complex span of Pauli strings of weight $\le t$ and every unit $\psi\in\mathbb C^2$,

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

4. Each gadget is well formed with respect to its live wires:

   • $G_{\text{prep}}$ goes from no live wires to the data wires;
   • $G_{\text{meas}}$ goes from the data wires to none;
   • $G_H, G_T, G_{\text{CNOT}}, G_{\text{wait}}, G_{ec}$ go from data wires to data wires.

   Well formed means that in each step, locations touch disjoint wires and every live wire is touched. Preparations act only on non-live wires and other locations only on live wires. Preparations add live wires and measurements remove them, and the final live set is the stated one.

5. Meas. Whenever $r+f(G_{\text{meas}},f\!a)\le t$, for all $\beta$ and $\rho$:

$$\mathrm{measF}(f\!a,\beta)(\mathcal F_r\rho)=\mathcal D(\mathcal F_r\rho)_{\beta\beta}.$$

6. Prep A. If $f(G_{\text{prep}},f\!a)\le t$, then $\mathcal F_{f(G_{\text{prep}},f\!a)}(\mathrm{prep}(f\!a))=\mathrm{prep}(f\!a)$.
7. Prep B. If $f(G_{\text{prep}},f\!a)\le t$, then $\mathcal D(\mathrm{prep}(f\!a))=|0\rangle\langle0|$.
8. Gate A. For $\kappa\in\{H,T,\text{CNOT},\text{wait}\}$ and $r_i\in\mathbb N$ with $f+\sum_i r_i\le t$, where $f=f(G_\kappa,f\!a)$:

$$\textstyle\bigotimes\mathcal F_{f+\sum r_i}\circ\mathrm{gateOp}_\kappa\circ\bigotimes_i\mathcal F_{r_i}=\mathrm{gateOp}_\kappa\circ\bigotimes_i\mathcal F_{r_i}.$$

9. Gate B. Under the same conditions:

$$\textstyle\bigotimes\mathcal D\circ\mathrm{gateOp}_\kappa\circ\bigotimes\mathcal F_{r_i}=(U_\kappa\cdot U_\kappa^\dagger)\circ\bigotimes\mathcal D\circ\bigotimes\mathcal F_{r_i}.$$

Here $U_\kappa$ is, respectively, the Hadamard, $\mathrm{diag}(1,e^{i\pi/4})$, CNOT with the first wire as control, or the identity. 10. EC A. If $f=f(G_{ec},f\!a)\le t$, then $\mathcal F_f\circ\mathrm{ecOp}=\mathrm{ecOp}$. 11. EC B. If $r+f(G_{ec},f\!a)\le t$, then $\mathcal D\circ\mathrm{ecOp}\circ\mathcal F_r=\mathcal D\circ\mathcal F_r$.

Further hypotheses.

• Uniform depth: every gadget has as many time steps as $G_{\text{prep}}$.
• $C$ is ideal: it is well formed from no live wires to no live wires, and every location's classical condition is constantly true.
• $W$ is a $*$-decoder for $\mathcal D$: $W^\dagger W=I$, $WW^\dagger=I$, and $\mathrm{Tr}_{\sigma}(W\rho W^\dagger)=\mathcal D(\rho)$ for all $\rho$, where $\mathrm{Tr}_\sigma$ traces out the $\sigma$-dimensional factor. In particular, this forces $2\sigma=2^n$. For $\sigma=0$ the hypothesis is unsatisfiable.

The circuits. $C'$ is the fault-tolerant circuit $\mathrm{FT}_P(C)$ on $N(n+A)$ wires. Each time step of $C$ becomes two phases:

• a gadget phase, in which each location is replaced by its gadget on the blocks of its wires;
• an EC phase, in which $G_{ec}$ runs on the block of every wire whose location at that step is not a measurement.

Gadget conditions are conjoined with the original location's condition evaluated on decoded logical outcomes.

$\mathrm{ftDecode}$ maps a $C'$ record to the list, over the measurement locations of $C$ in order, of $\mathrm{measDecode}$ applied to the outcomes of that location's meas gadget. Missing outcomes are read as false. For a decoding map $\mathrm{dec}$, the push-forward of a distribution $\mu$ is

$$\mathrm{push}_{\mathrm{dec}}\mu(r)=\sum_{r':\,\mathrm{dec}(r')=r}\mu(r').$$

Output distributions. $\mathrm{out}(C,\mathrm{err},\sigma_0)(r)$ is $\operatorname{Re}\operatorname{Tr}$ of the classical–quantum run of $C$ at record $r$. The run starts from $|0\cdots0\rangle\langle0\cdots0|\otimes\sigma_0$ with the empty record. The error superoperator $\mathrm{err}(\ell)$ is applied after location $\ell$, or before it at a measurement.

The bad set. $\mathrm{Bad}(S)$ is defined for a set $S$ of $C'$ locations, scanning the steps of $C$ from last to first. A location $\ell$ of $C$ is bad if more than $t$ elements of $S$ lie in its ExRec. The ExRec of $\ell$ consists of:

• $\ell$'s gadget;
• the EC instances on $\ell$'s wires from the preceding step, if $\ell$ is not a preparation;
• the EC instances on $\ell$'s wires from the same step, if $\ell$ is not a measurement, omitting wires that are also wires of a bad location in the next step.

Conclusion. There exist a matrix $\sigma_0$ on the environment indexed by $\{0,\dots,\sigma-1\}^N$ (one $\sigma$-dimensional register per wire) and an error assignment $\mathrm{err}$ such that:

• $\sigma_0$ is a density matrix (PSD with trace $1$);
• $\mathrm{err}$ is a "tilde" error assignment for $B=\mathrm{Bad}(\text{faulty locations of }C'\text{ under }f\!a)$, defined as follows:
  • $\mathrm{err}(\ell)$ is absent wherever $C$ has no location;
  • at each location $l$, $\mathrm{err}(\ell)$ is some channel $\Psi$ acting on $l$'s wires together with their $\sigma$-registers, extended by the identity elsewhere;
  • if $\ell\notin B$, then $\Psi=\mathrm{id}_{\text{qubits}}\otimes V$ for some channel $V$ on the $\sigma$-registers alone;
• the decoded faulty output equals the output of $C$ under these errors:

$$\mathrm{push}_{\mathrm{ftDecode}}\big(\mathrm{out}(C',\text{Pauli faults }f\!a,\,1)\big)=\mathrm{out}(C,\mathrm{err},\sigma_0).$$

No bound on the number of faults in $f\!a$ is assumed.