CSS syndrome correction

Choose a basis $h_1,\dots ,h_a$ of $C_1^{\perp }$. For an error $X^u$, append ancillas $\mathrm{\mid }{0}^a⟩$ and, for each $i$ and each coordinate $j$ with $(h_i{)}_j=1$, apply CNOT from data wire $j$ to ancilla $i$. On a computational-basis input $\mathrm{\mid }y⟩\mathrm{\mid }{0}^a⟩$, repeated use of [F5] gives $\mathrm{\mid }y⟩\mathrm{\mid }{H}_{1}y⟩$, where the $i$th parity is $h_i\cdot y$. Ordered wire placement and chronological gate composition are fixed by [F17]–[F18].

For a code basis vector $\mathrm{\mid }x+C_2⟩$, each $y=x+c$ belongs to $C_1$, so $h_i\cdot y=0$. For the combined Pauli error $i^k{X}^u{Z}^v$, its action on $\mathrm{\mid }y⟩$ is $i^k(-1{)}^{v\cdot y}\mathrm{\mid }y+u⟩$. The parity circuit therefore writes $H_1(y+u)=H_{1}u$ into the ancillas. The factor $(-1{)}^{v\cdot y}$ changes only the data amplitude, so the first syndrome extraction is unchanged by the $Z^v$ component; it factors the state as a data density operator $\sigma$ tensored with $\mathrm{\mid }s⟩⟨s\mathrm{\mid }$, where $s=H_{1}u$. The circuit maps are unitary by [F18], so $\mathrm{tr}(\sigma )=1$. The kernel of $y\mapsto (h_i\cdot y{)}_i$ is $(C_1^{\perp }{)}^{\perp }$: symmetry gives $C_1\subseteq (C_1^{\perp }{)}^{\perp }$, and [F3] gives equality of dimensions. By [F14] and [F23], $P_r=I_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}\otimes \mathrm{\mid }r⟩⟨r\mathrm{\mid }$ are pairwise orthogonal projections summing to identity, hence form a projective measurement by [F20]. Its weights are probabilities by [F21]; because $P_s(\sigma \otimes \mathrm{\mid }s⟩⟨s\mathrm{\mid })P_s=\sigma \otimes \mathrm{\mid }s⟩⟨s\mathrm{\mid }$ and $P_r(\sigma \otimes \mathrm{\mid }s⟩⟨s\mathrm{\mid })P_r=0$ for $r\mathrm{\ne }s$, [F20] gives weight $1$ at $s$ and $0$ elsewhere. [F22] leaves the data factor unchanged. The observed syndrome is $H_{1}u$, and the classical controller receives it by [F19].

Choose a basis $c_1,\dots ,c_b$ of $C_2$. Apply $H$ to every data wire, perform the parity circuit using the $c_i$ as parity rows, measure the ancillas, and then apply $H$ again unconditionally. The combined error $i^k{X}^u{Z}^v$ is conjugated by these Hadamards to $i^k{Z}^u{X}^v$, since [F6] exchanges $X$ and $Z$ on each wire. The Fourier identity in [F1] shows the transformed encoded state is supported on $C_2^{\perp }$, so the $C_2$ parity vector is zero before the error. After the error, each supported basis word $y\in C_2^{\perp }$ is shifted to $y+v$, giving ancilla parity $H_{2}v$; the diagonal factor $Z^u$ changes only its data amplitude and leaves this parity unchanged. Thus the syndrome is independent of the logical coset and the state factors as a data density operator $\tau$ tensored with $\mathrm{\mid }{H}_{2}v⟩⟨H_{2}v\mathrm{\mid }$. The parity map has kernel $C_2^{\perp }$ by [F2]. Its circuit is unitary, so $\mathrm{tr}(\tau )=1$. For the $b$-bit ancilla register, $Q_r=I_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}\otimes \mathrm{\mid }r⟩⟨r\mathrm{\mid }$ are the computational-basis projectors, so [F20]–[F21] give the unique outcome $H_{2}v$ with probability one. Since $Q_{H_{2}v}$ fixes the product state, $Q_{H_{2}v}(\tau \otimes \mathrm{\mid }{H}_{2}v⟩⟨H_{2}v\mathrm{\mid })Q_{H_{2}v}=\tau \otimes \mathrm{\mid }{H}_{2}v⟩⟨H_{2}v\mathrm{\mid }$, and [F22] leaves the data factor unchanged. The unconditional final Hadamards return the data to the original basis with the same $X^u{Z}^v$ error, up to its original scalar phase. The finite controller records the observed syndrome by [F19].

If $X$ errors $u,u^{\mathrm{\prime }}$ of weight at most $t$ have the same first syndrome, their difference $u+u^{\mathrm{\prime }}$ lies in $C_1$, since the first parity-check kernel is $C_1$ by [F24]. If $C_1=\{0\}$, this immediately gives $u=u^{\mathrm{\prime }}$. If $C_1\mathrm{\ne }\{0\}$, then $2t<\delta (C_1)=d(C_1)$ and [F4] gives $u=u^{\mathrm{\prime }}$. Likewise, equal second syndromes put $v+v^{\mathrm{\prime }}$ in $C_2^{\perp }$ by [F2] and the second parity-map kernel. If $C_2^{\perp }=\{0\}$, then $v=v^{\mathrm{\prime }}$ directly; otherwise $2t<\delta (C_2^{\perp })=d(C_2^{\perp })$ and [F4] gives equality. Thus each observed syndrome with a weight-at-most-$t$ error has at most one such error. For any syndrome with no such error, assign the zero vector as a default; this defines each total finite decoder, including the zero-code cases.

A Pauli error has the form $i^k{X}^u{Z}^v$ by [F12], and [F15] shows that the supports of $u$ and $v$ lie among the same at-most-$t$ physical sites. By [F10], the Z-check syndrome depends only on $u$ and the X-check syndrome only on $v$, so the two decoders determine both components. The finite controller of [F19] applies the selected correction; applying $Z^v{X}^u$ after the error returns every encoded vector to itself up to the scalar $i^k$. Since both syndromes are independent of the logical basis label by steps 3.1 and 2.1, this correction preserves arbitrary superpositions.

Let $S=⟨X^c:c\in C_2;Z^h:h\in C_1^{\perp }⟩$, the group generated by the CSS checks in [F1]. They commute because $c\cdot h=0$ for $c\in C_2\subseteq C_1$ and $h\in C_1^{\perp }$; their common code space is nonzero by [F1], so $-I\mathrm{\notin }S$. By [F10] and [F12], $X^u{Z}^v$ commutes with all $X$ checks exactly when $v\in C_2^{\perp }$, and with all $Z$ checks exactly when $u\in (C_1^{\perp }{)}^{\perp }$. The inclusion $C_1\subseteq (C_1^{\perp }{)}^{\perp }$ follows from [F2]; [F3] gives both spaces dimension $\dim C_1$, so [F25] gives $(C_1^{\perp }{)}^{\perp }=C_1$. Hence the normalizer condition is exactly $u\in C_1$ and $v\in C_2^{\perp }$. The labels of $Z_{n}S$ are exactly pairs $(c,h)$ with $c\in C_2$ and $h\in C_1^{\perp }$, so logical triviality is exactly $u\in C_2$ and $v\in C_1^{\perp }$. A nontrivial logical Pauli therefore has either $u\in C_1\setminus C_2$ or $v\in C_2^{\perp }\setminus C_1^{\perp }$. Its weight is at least $d_{\mathrm{C}\mathrm{S}\mathrm{S}}$, and each nonempty difference set supplies a pure logical Pauli attaining its own minimum. If $k=0$, inclusion $C_2\subseteq C_1$ and equality of their dimensions give $C_1=C_2$ by [F25]; their duals are equal, both difference sets are empty, and $d_{\mathrm{C}\mathrm{S}\mathrm{S}}=+\mathrm{\infty }$. The sufficient condition in the Statement implies $2t<d_{\mathrm{C}\mathrm{S}\mathrm{S}}$ because each pure logical weight is at least the minimum nonzero weight of its containing code. When $k>0$, the least nontrivial logical Pauli weight is the stabilizer distance by [F9]; when $k=0$, both sets are empty and the distance convention is $+\mathrm{\infty }$. The physical support of $X^u{Z}^v$ is $\mathrm{supp}(u)\cup \mathrm{supp}(v)$ by [F15], and its binary-vector weights are given by [F16].

Let $P$ be the code projector. If a Pauli $F$ of weight less than $d_{\mathrm{C}\mathrm{S}\mathrm{S}}$ anticommutes with a check $g$, then [F1] gives $gP=Pg=P$, so $PFP=PgFP=-PFgP=-PFP$ and hence $PFP=0$. If it commutes with all checks, step 6.1 and the definition of $d_{\mathrm{C}\mathrm{S}\mathrm{S}}$ force it to be a scalar-phase stabilizer, so $PFP=\lambda P$.

For Pauli errors $E_a,E_b$ of weight at most $t$, the product $E_a^{\ast }{E}_b$ has weight at most $2t<d_{\mathrm{C}\mathrm{S}\mathrm{S}}$, so step 7.1 gives $P{E}_a^{\ast }{E}_{b}P=C_{ab}P$. On one qubit, direct substitution of [F13] gives the matrix-unit identities $\mathrm{\mid }0⟩⟨0\mathrm{\mid }=(I+Z)\mathrm{/}2$, $\mathrm{\mid }1⟩⟨1\mathrm{\mid }=(I-Z)\mathrm{/}2$, $\mathrm{\mid }0⟩⟨1\mathrm{\mid }=(X+iY)\mathrm{/}2$, and $\mathrm{\mid }1⟩⟨0\mathrm{\mid }=(X-iY)\mathrm{/}2$. For bit strings $a,b\in \{0,1{\}}^n$, the global matrix unit $\mathrm{\mid }a⟩⟨b\mathrm{\mid }$ is the tensor product of these one-qubit matrix units; expanding that product expresses it as a linear combination of tensor Pauli operators. Every operator $A$ on the ordered computational basis has the matrix-unit expansion $A={\sum }_{a,b}⟨A{e}_b,e_a⟩\mathrm{\mid }a⟩⟨b\mathrm{\mid }$, so the tensor Paulis span the full operator space. By [F14]–[F15], every operator supported on at most $t$ sites is a linear combination of Paulis of weight at most $t$. Bilinearity extends the scalar-compression condition to every pair of such Kraus operators.

The finite scalar-compression matrix from step 8.1 satisfies the hypothesis of [F8]. Hence the channel has an exact finite recovery.