Stabilizer and CSS Codes, Syndromes, and Procedures

Since $C_2\subseteq C_1$, every $x\in C_1$ has a coset in $C_1\mathrm{/}{C}_2$. If $x^{\mathrm{\prime }}=x+c_0$ with $c_0\in C_2$, then $c\mapsto c+c_0$ permutes $C_2$; reindexing the finite sum gives $\mathrm{\mid }{x}^{\mathrm{\prime }}+C_2⟩=\mathrm{\mid }x+C_2⟩$. Thus the displayed vector is independent of the representative.

By [F4], $\dim C_2\le \dim C_1$, so $k\ge 0$. Extend a basis of $C_2$ to a basis of $C_1$. If the dimensions are $m$ and $m+k$, respectively, the added $k$ basis vectors span a complement $D$ with $C_1=C_2\oplus D$. Each coset has exactly one representative in $D$, so $D\to C_1\mathrm{/}{C}_2$, $d\mapsto d+C_2$, is a bijection. Coordinate expansion in the chosen basis identifies $D$ with ${\mathbb{F}}_2^k$. There are $2^k$ such coordinate lists, since each of the $k$ coordinates has two choices; for $k=0$ there is one empty list. Hence $\mathrm{\mid }{C}_1\mathrm{/}{C}_2\mathrm{\mid }=2^k$.

For each coset, the basis vectors $\mathrm{\mid }x+c⟩$ in its sum are distinct, so [F3] gives squared norm $\mathrm{\mid }{C}_2{\mathrm{\mid }}^{-1}\mathrm{\mid }{C}_2\mathrm{\mid }=1$. Different cosets have disjoint supports in that basis, so their inner product is zero. The code space therefore has the $2^k$ orthonormal coset vectors indexed by $C_1\mathrm{/}{C}_2$.

Let $e_0,\dots ,e_{n-1}$ be the standard basis of ${\mathbb{F}}_2^n$. Its coordinate dual basis is $e_0^{\ast },\dots ,e_{n-1}^{\ast }$, and $e_i\cdot y=y_i=e_i^{\ast }(y)$ for $0\le i<n$ by [F1]. Thus the linear map $J:{\mathbb{F}}_2^n\to ({\mathbb{F}}_2^n{)}^{\ast }$, $J(x)(y)=x\cdot y$, sends a basis to the dual basis from [F2], so it is an isomorphism.

Choose a basis $c_1,\dots ,c_m$ of $C$ and extend it to a basis of ${\mathbb{F}}_2^n$ by [F3]. For every $f\in C^{\ast }$, define $\tilde{f}$ on the extended basis by $\tilde{f}(c_i)=f(c_i)$ and value $0$ on each added basis vector, then extend linearly. This is a linear functional on ${\mathbb{F}}_2^n$ whose restriction to $C$ is $f$. Hence restriction $({\mathbb{F}}_2^n{)}^{\ast }\to C^{\ast }$ is onto.

The composite $T:{\mathbb{F}}_2^n\stackrel{J}{\to }({\mathbb{F}}_2^n{)}^{\ast }\to C^{\ast }$ is onto by the isomorphism in step 1.1 and surjectivity in step 1.2. Its kernel consists exactly of those $x$ for which $x\cdot c=0$ for all $c\in C$, namely $C^{\perp }$ by [F1]. Since $\dim C^{\ast }=\dim C=m$ by [F2], rank-nullity [F4] gives $n=\dim C^{\perp }+m$. Therefore $\dim C^{\perp }=n-\dim C$.

For each face, every vertex outside $R$ is incident to either zero or two of its boundary edges. If a boundary edge lies in $R$, its endpoints are in $R$ and are omitted from $Q_0$. Therefore every nonrough vertex appears an even number of times in ${\mathrm{\partial }}_1{\mathrm{\partial }}_2$ of that face, so ${\mathrm{\partial }}_1{\mathrm{\partial }}_2=0$.

The row vectors of $H_X$ and $H_Z$ have binary dot products given by $H_X{H}_Z^{\mathsf{T}}={\mathrm{\partial }}_1{\mathrm{\partial }}_2=0$ from step 1.1. Hence every X check commutes with every Z check; X checks commute among themselves, as do Z checks, since equal-type Pauli factors commute. This defines a commuting CSS stabilizer family without any physical or topological-order premise.

Applying [F3] to $E$ and $g_j$ gives $E{g}_j=(-1{)}^{\omega (\lambda (E),\lambda (g_j))}{g}_{j}E$. The exponent is in ${\mathbb{F}}_2$, so it determines exactly one bit, and this verifies the stated sign-to-bit convention.

If $E^{\mathrm{\prime }}=i^{a}E$ for a scalar phase $i^a$, then $E^{\mathrm{\prime }}{g}_j=i^{a}E{g}_j$ and $g_j{E}^{\mathrm{\prime }}=i^a{g}_{j}E$; the same commutation sign results. Equivalently, $\lambda (E^{\mathrm{\prime }})=\lambda (E)$ by [F1]. Hence the syndrome depends only on the Pauli coset modulo scalar phase.

If $E\in Z_{n}S$, write $E=zs$ with $z\in Z_n$ and $s\in S$. The scalar $z$ commutes with every generator, and $s$ commutes with every generator because $S$ is abelian, so $E\in N(S)$ and its logical quotient class is the identity. Conversely the denominator of the displayed quotient is exactly the scalar phases times stabilizers; thus a normalizer element outside $Z_{n}S$ represents a nonidentity logical Pauli class.

After $j$ pivots, the first $j$ rows are $+Z_0,\dots ,+Z_{j-1}$, and every remaining row has zero $X$ and $Z$ coordinates on those $j$ wires. This holds before the first pivot. At pivot $j$, the selected row is interchanged into row $j$ when necessary; the interchange also updates the signed row-operation data and is not a circuit gate. All circuit gates act only on unused wires. For any zero-based circuit wire $q$, the one-based factor index in [F2]–[F4] is $q+1$; a CNOT with circuit control $q$ and target $s$ therefore uses supplier indices $q+1,s+1$. The local Clifford gates turn each nonidentity pivot factor into $Z$, and [F4] clears every other pivot-row $Z$ using a control on that wire and target $j$. Commutation is preserved by conjugation, so remaining rows have no $X_j$ factor. Row multiplication by the pivot then clears $Z_j$ without changing earlier wires.

The remaining $r-j$ binary row labels are independent on the unused $n-j$ wires: a dependence there would be a dependence among the original labels because all earlier coordinates are already zero. Since $r-j>0$ when $j<r$, at least one remaining row is nonidentity on an unused wire. Thus every valid pivot finds a row and a wire, and the loop executes exactly $r$ iterations. This proves termination, including $r=0$.

During one pivot, at most one SWAP is used. On each of at most $n$ unused wires, normalization uses at most two one-qubit gates. Clearing the pivot's other $Z$ factors uses at most $n-1$ CNOTs, and correcting its sign uses at most one $X$. The total is at most $1+2n+(n-1)+1=3n+1$ gates per pivot, hence at most $r(3n+1)$ overall.

The current phase-aware tableau and the phase-aware input-combination rows together store $4rn$ label bits and $O(r)$ phase bits. The signed row-operation output stores $r^2$ bits for $M$ and $O(r)$ bits for $\kappa$. The output has at most $r(3n+1)$ gates; each gate type takes constant space and each wire index takes at most $\lceil {\log }_2(n+1)\rceil$ bits. Their total is $O(rn+r^2+rn\log (n+1))$. For $r=0$, the output and signed row-operation data are empty, as specified.

The subgroup in the Statement meets the definition in [F1]. By [F2], $P_S$ is self-adjoint and idempotent with image equal to the common $+1$ eigenspace.

The rank-$r$ hypothesis is the same rank convention used in [F3]: independent Hermitian generators give a binary label space of dimension $r$ by [F5]. Therefore [F3] gives $\dim \mathcal{C}(S)=\mathrm{Tr}(P_S)=2^{n-r}$.

By [F4] and step 1.1, $P_S$ is the orthogonal projector onto $\mathcal{C}(S)$. Since $2^{n-r}\ge 1$, this space is nonzero; the endpoint $r=n$ has rank one and $r=0$ gives the full $2^n$-dimensional register.

There are $\mathrm{\mid }{C}_2\mathrm{\mid }$ distinct basis vectors in each coset sum. By [F4], its squared norm is $\mathrm{\mid }{C}_2{\mathrm{\mid }}^{-1}\mathrm{\mid }{C}_2\mathrm{\mid }=1$. Distinct cosets have disjoint supports, so their vectors are orthogonal. By [F1] there are $\mathrm{\mid }{C}_1\mathrm{/}{C}_2\mathrm{\mid }=2^{\dim C_1-\dim C_2}=2^k$ such vectors, giving an orthonormal basis indexed by a $k$-bit logical register.

By [F5], for $c\in C_2$, $X^c$ sends $\mathrm{\mid }x+u⟩$ to $\mathrm{\mid }x+u+c⟩$. Translation $u\mapsto u+c$ permutes $C_2$, so $X^c$ fixes the whole coset sum. For $h\in C_1^{\perp }$, each $x+u\in C_1$ and therefore $(-1{)}^{h\cdot (x+u)}=1$; the diagonal operator $Z^h$ fixes every term. Thus both check families fix every encoded basis state and hence their linear span.

The binary labels of $X^c$ and $Z^h$ are $(c,0)$ and $(0,h)$. Their symplectic pairing is $c\cdot h$. Since $c\in C_2\subseteq C_1$ and $h\in C_1^{\perp }$, this dot product is zero by [F2].

On a computational basis vector $\mathrm{\mid }w⟩$, multiplying the one-bit Hadamard formulas from [F7] gives $H^{\otimes n}\mathrm{\mid }w⟩=2^{-n\mathrm{/}2}{\sum }_{y\in {\mathbb{F}}_2^n}(-1{)}^{y\cdot w}\mathrm{\mid }y⟩$. Substituting the coset definition [F1] yields $H^{\otimes n}\mathrm{\mid }x+C_2⟩=2^{-n\mathrm{/}2}\mathrm{\mid }{C}_2{\mathrm{\mid }}^{-1\mathrm{/}2}{\sum }_{y\in {\mathbb{F}}_2^n}(-1{)}^{y\cdot x}({\sum }_{u\in C_2}(-1{)}^{y\cdot u})\mathrm{\mid }y⟩$. For $y\in C_2^{\perp }$, the inner sum is $\mathrm{\mid }{C}_2\mathrm{\mid }$. Otherwise choose $u_0\in C_2$ with $y\cdot u_0=1$; translation $u\mapsto u+u_0$ pairs terms with opposite signs, so the sum is zero.

Choose independent bases of $C_2$ and $C_1^{\perp }$. Their separate $X$- and $Z$-type labels are independent: a zero combined label has both binary halves zero. By [F3] the combined number is $\dim C_2+n-\dim C_1=n-k$. This includes $k=0$.

The checks are commuting Hermitian Paulis by steps 1.3 and [F5]. They fix the nonzero encoding from step 1.2, so their generated group cannot contain $-I$. Step 2.1 gives $n-k$ independent checks; [F9] therefore gives their common $+1$ eigenspace dimension $2^{n-(n-k)}=2^k$. By step 1.1 the encoding has dimension $2^k$, and step 1.2 says it lies in that eigenspace. Equal finite dimensions force equality: the CSS encoding is exactly the stabilizer code space [F8].

The transformed vector is supported exactly on $C_2^{\perp }$, with constant magnitude on that set. Since $x\in C_1$, the phase $(-1{)}^{x\cdot y}$ is constant on each coset of $C_1^{\perp }$ in $C_2^{\perp }$. Grouping terms by those cosets gives $H^{\otimes n}\mathrm{\mid }x+C_2⟩=2^{-k\mathrm{/}2}{\sum }_{y+C_1^{\perp }\in C_2^{\perp }\mathrm{/}{C}_1^{\perp }}(-1{)}^{x\cdot y}\mathrm{\mid }y+C_1^{\perp }⟩$. The coefficient is $2^{-k\mathrm{/}2}$ because $\mathrm{\mid }{C}_2\mathrm{\mid }\mathrm{\mid }{C}_1^{\perp }\mathrm{\mid }\mathrm{/}{2}^n=2^{-k}$ by [F3]. This is the dual coset basis Fourier transform; the pairing is independent of representatives since $C_2\subseteq C_1$ and $C_1^{\perp }\subseteq C_2^{\perp }$.

The procedure terminates after $r$ pivots on every valid input by [F2]. By [F7]–[F8], each appended local gate acts on its ordered wires and the chronological list denotes its composed unitary. Each tableau coordinate and circuit wire $q$ corresponds to supplier factor $q+1$, as fixed in [F1]; in particular, one-wire updates use factor $q+1$ and a CNOT on circuit wires $q,s$ uses supplier control and target indices $q+1,s+1$. At each pivot, the local $H$, $S^{†}$, and $H$ transformations send the pivot row's nonidentity one-wire Pauli factors to signed $Z$ factors. The $S^{†}$ step sends $Y$ to $X$ by the inverse phase-gate action [F4], and then [F3] sends $X$ to $Z$. For each remaining pivot-row $Z_q$, the control-$q$, target-$j$ CNOT changes the pivot label $Z_q{Z}_j$ to $Z_j$ by [F5]. If the resulting row is negative, $X_j$ changes $-Z_j$ to $+Z_j$. Conjugation preserves commutation, while the exact phase-aware gate actions track every resulting sign.

Interchanging the selected pivot row into position $j$ and each subsequent row multiplication are invertible elementary operations on the generator list; the former swaps rows of $M$ and $G$, and the latter updates them by the same binary row addition and exact Pauli product. Thus $M$ remains invertible and $G_i={\prod }_a{g}_a^{M_{ia}}$ retains its recorded phase ${\kappa }_i$. Row multiplication by the pivot clears the remaining row's $Z_j$ coordinate because that row has no $X_j$ coordinate: it commutes with the now-$Z_j$ pivot. Consequently the transformed input-product rows are exactly $+Z_0,\dots ,+Z_{r-1}$, as asserted by [F1].

A vector is fixed by every $Z_j$ for $j<r$ exactly when all its computational-basis coordinates with a $1$ among the first $r$ bits vanish. Thus the common $+1$ eigenspace of the canonical checks is $\mathrm{\mid }{0}^r⟩\otimes ({\mathbb{C}}^2{)}^{\otimes (n-r)}$. By the row-basis equivalence in step 2.1 and the denotation [F8], this is exactly $D\mathcal{C}(S)$.

The ordered computational basis is orthonormal by [F9], and $x\mapsto \mathrm{\mid }{0}^r⟩\otimes \mathrm{\mid }x⟩$ embeds the logical computational basis as an orthonormal family. The finite product unitary $D^{†}$ from [F8] therefore defines the isometry $V$ in the Statement and sends these $2^{n-r}$ vectors to orthonormal vectors in $\mathcal{C}(S)$. Step 3.1 shows they span that space, and [F6] confirms its dimension is $2^{n-r}$. Hence they form the stated stabilizer code basis.

By [F1], phase classes of Paulis are the vectors of $V_n$. By [F2] the stabilizer labels form an $r$-dimensional subspace $W$. The commutator criterion [F3] identifies the normalizer labels exactly with $W^{\perp }$. The scalar phases label zero, so the subgroup $Z_{n}S$ has image $W$. Therefore $N(S)\mathrm{/}(Z_{n}S)$ is identified with $W^{\perp }\mathrm{/}W$.

The nondegenerate pairing [F6] gives an injective map $J:V_n\to V_n^{\ast }$, $J(v)=\omega (v,\cdot )$. Restricting functionals from $V_n$ to $W$ is onto: extend a basis of $W$ to one of $V_n$ by [F7], then extend each functional by assigning zero to the added basis vectors. Since $\dim V_n^{\ast }=\dim V_n=2n$ by [F9], injectivity and rank-nullity [F8] make $J$ onto. Thus the composite $V_n\to W^{\ast }$ is onto; its codomain has dimension $r$ by [F9], and its kernel is $W^{\perp }$. By [F8], $\dim W^{\perp }=2n-r$.

Since $W\subseteq W^{\perp }$, the quotient dimension is $\dim (W^{\perp }\mathrm{/}W)=(2n-r)-r=2(n-r)$. By [F5], $k=n-r$ is the number of encoded qubits; hence this dimension is $2k$, which is zero exactly when $k=0$.

If $k>0$, [F1] gives a quotient of positive dimension, so it contains a nonidentity class. Any representative is a Pauli in the finite group ${\mathcal{P}}_n$, and [F2] assigns it an integer weight in $\{0,\dots ,n\}$. Thus the set in the minimum is nonempty and finite, so its minimum exists.