Threshold theorem: below p_T, concatenated circuits simulate C to distance ε with polylog overhead

Notions used.

A protocol $P$ consists of:

• numbers $n,t,A$;
• a code $\mathcal C\subseteq\mathbb C^{2^n}$;
• an encoder $\mathrm{enc}$ and a decoder $\mathcal D$;
• gadget circuits $G_\kappa$ for the location kinds prep, $H$, $T=\mathrm{diag}(1,e^{i\pi/4})$, CNOT, meas and wait;
• an EC circuit $G_{ec}$;
• a classical $\mathrm{measDecode}$.

"$P$ is fault tolerant" means all of the following:

• $\dim\mathcal C=2$, and all operators on $\le2t$ qubits are detectable on $\mathcal C$.
• $\mathrm{enc}$ is an isometry onto $\mathcal C$.
• $\mathcal D$ is a Kraus channel decoding $E\,\mathrm{enc}\,\psi$ to $\|E\,\mathrm{enc}\,\psi\|^2|\psi\rangle\langle\psi|$ for all $E$ in the span of weight-$\le t$ Pauli strings.
• All gadgets are well formed with the stated live data wires.
• The Meas, Prep A/B, Gate A/B and EC A/B superoperator identities hold under Pauli faults. Each is stated with the filters $\mathcal F_r$ (projection onto Pauli-weight-$\le r$ errors of $\mathcal C$) whenever fault count plus filter parameters is $\le t$.

"Uniform depth" means all gadgets have the same number of time steps.

Concatenation. $C^{(L)}$ is the level-$L$ concatenation, on $N(n+A)^L$ wires: $C^{(0)}=C$ and $C^{(L+1)}=\mathrm{FT}_P(C^{(L)})$. $\mathrm{FT}_P$ replaces each step by a gadget phase followed by an EC phase on the blocks of non-measured wires. The decoder $\mathrm{dec}^{(L)}$ applies the one-level logical record decoding $L$ times, from the top level down. For a circuit:

• $\mathrm{numQubits}$ is its wire count;
• $\mathrm{numSteps}$ is its number of time steps;
• $\mathrm{size}$ is its number of locations.

Distributions. For a local stochastic model $M$ (described below):

$$\mathrm{noisy}(C,M)(r)=\sum_{S\subseteq\mathrm{locs}}\Pr_M(S)\,\mathrm{out}(C,\ \ell\mapsto[\ell\in S]\mathcal E_S(\ell),\ \sigma_0)(r).$$

The ideal distribution $\mathrm{ideal}(C)$ is the output distribution with no errors and a trivial one-dimensional environment. The push-forward is $\mathrm{push}_{\mathrm{dec}}\mu(r)=\sum_{\mathrm{dec}(r')=r}\mu(r')$, and the total variation distance is

$$\mathrm{tv}(\mu,\nu)=\tfrac12\sum_r|\mu(r)-\nu(r)|.$$

A model $M$ is local stochastic for a circuit with bound $b$ when:

• its initial environment is a density matrix;
• its weights are nonnegative, vanish off subsets of the locations, and sum to $1$ over those subsets;
• each $\mathcal E_S(\ell)$ with $\ell\in S$ is a channel on the location's wires $\otimes$ environment;
• $\sum_{R\subseteq S\subseteq\mathrm{locs}}\Pr(S)\le\prod_{i\in R}b(i)$ for every $R\subseteq\mathrm{locs}$.

Statement. There exists a fault-tolerant protocol $P$ with uniform depth, and a real $p_T>0$, such that the following holds.

For every $p$ with $0\le p<p_T$ there exist a real $K>0$ and $c\in\mathbb N$, depending only on $p$, with the following property. For every $N$, every ideal circuit $C$ on $N$ wires (well formed from and to no live wires, all conditions constantly true) and every $\varepsilon>0$, there is a level $L$ with:

$$N(n+A)^L\le K\,\log_2\!\Big(2+\frac{\mathrm{size}(C)}{\varepsilon}\Big)^{c}\,N,$$ $$\mathrm{numSteps}(C^{(L)})\le K\,\log_2\!\Big(2+\frac{\mathrm{size}(C)}{\varepsilon}\Big)^{c}\,\mathrm{numSteps}(C).$$

Moreover, for every local stochastic model $M$ on $N(n+A)^L$ wires with any bound $b$ satisfying $b(\ell)<1$ and $b(\ell)\le p$ at every location $\ell$ of $C^{(L)}$:

$$\mathrm{tv}\Big(\mathrm{push}_{\mathrm{dec}^{(L)}}\mathrm{noisy}(C^{(L)},M),\ \mathrm{ideal}(C)\Big)\le\varepsilon.$$

Remarks on edge cases.

• The qubit count of $C^{(L)}$ is by definition $N(n+A)^L$. For $N=0$ the qubit inequality reads $0\le0$.
• The constant $2$ inside the logarithm makes the logarithm at least $1$.
• $L=0$ is permitted.