CSS Codes

Calderbank–Shor–Steane, or CSS, codes turn a compatible pair of binary linear codes into a quantum stabilizer code whose checks are purely $X$-type or purely $Z$-type. That separation makes the construction unusually transparent. Commutation becomes one binary matrix product, logical Paulis become quotient spaces, and ideal syndromes split into two classical-looking parity equations. The separation is algebraic, however, not a promise that physical noise, decoding, or fault-tolerant operations split into independent problems.

This page develops the family rather than one celebrated member. It fixes one row-vector convention for $H_X$ and $H_Z$, translates it into nested classical codes, constructs normalized coset states, derives exact $X$- and $Z$-logical quotients and distances, and specializes Pauli correctability to CSS language. A deliberately unequal five-qubit detection fixture keeps every convention auditable without duplicating the exact Shor Code, Steane Code, or perfect non-CSS Five-Qubit Code.

The construction emerged independently through Calderbank and Shor’s existence construction and Steane’s code-theoretic construction, with a fuller classical-code recipe in Steane’s subsequent treatment. The language below uses the stabilizer synthesis developed systematically by Gottesman and the standard presentation of Nielsen and Chuang.

Required background. Stabilizer Formalism supplies Pauli supports, stabilizer groups, normalizers, logical cosets, syndromes, and full-Pauli distance.

Helpful background. Classical Information Review supplies parity-check and binary-code orientation. Why Quantum Error Correction Is Possible supplies the general Knill–Laflamme theorem. Every binary-space convention needed below is nevertheless declared here.

Two Classical Codes and One Commuting Stabilizer

One declared binary and Pauli convention

All vectors are binary row vectors, arithmetic is over $\mathbb F_2$, and a length-$n$ string is read from qubit one on the left to qubit $n$ on the right. For $x,z\in\mathbb F_2^n$, define

$$X(x)=\bigotimes_{j=1}^{n}X_j^{x_j}, \qquad Z(z)=\bigotimes_{j=1}^{n}Z_j^{z_j}, \qquad E(x,z)=X(x)Z(z).$$

$E(x,z)$ is a phase-free representative. On one qubit $Y=iXZ$, so a physical $Y_j$ has $x_j=z_j=1$ although its global phase is discarded in the binary record. That phase suppression is legitimate for commutation, syndrome, stabilizer-coset, and distance calculations; it would not be legitimate in a calculation whose output depends on an operator’s signed action.

The ordinary binary inner product controls the cross-commutation:

$$X(x)Z(z)=(-1)^{xz^{\mathsf T}}Z(z)X(x).$$

Thus two supports commute exactly when their overlap has even cardinality. The convention table records the objects used throughout. “Positive check” means that the code occupies the $+1$ eigenspace of the associated Pauli, not that the binary entries have a sign.

Quantity	Frozen definition	Role
Binary support vectors	$x,z\in\mathbb F_2^n$, written as row vectors	Locate physical $X$ and $Z$ factors
Phase-free Pauli representative	$E(x,z)=X(x)Z(z)$ with $Y_j=iX_jZ_j$	Suppress irrelevant global phase while retaining both $Y$ components
X-check matrix	$H_X\in\mathbb F_2^{m_X\times n}$	Each row supports one positive $X$ stabilizer generator
Z-check matrix	$H_Z\in\mathbb F_2^{m_Z\times n}$	Each row supports one positive $Z$ stabilizer generator
Cross-commutation	$H_XH_Z^{\mathsf T}=0$	Make every $X$ check commute with every $Z$ check
Independent check ranks	$r_X=\operatorname{rank}H_X$, $r_Z=\operatorname{rank}H_Z$	Remove redundant parity equations
Encoded qubits	$k=n-r_X-r_Z$	Give code-space dimension $2^k$
X-logical quotient	$\ker H_Z/\operatorname{row}H_X$	Identify nontrivial pure-$X$ logical supports
Z-logical quotient	$\ker H_X/\operatorname{row}H_Z$	Identify nontrivial pure-$Z$ logical supports
Axis distances	$d_X,d_Z$ are minimum nontrivial quotient weights	Resolve asymmetric pure-axis protection
Ordered syndrome	$\sigma(E)=(H_Zx^{\mathsf T}\mid H_Xz^{\mathsf T})$	List $Z$-check bits before $X$-check bits

The two halves of a binary Pauli record should not be confused with two independent physical errors. They are coordinates of one operator. In particular, the same microscopic event can populate both halves, as $Y_j$ does, and a physical prior may correlate supports at different qubits as well.

The check-matrix commutation condition

Let

$$H_X\in\mathbb F_2^{m_X\times n}, \qquad H_Z\in\mathbb F_2^{m_Z\times n}.$$

For a row $h$ of $H_X$, use the positive check $X(h)$; for a row $g$ of $H_Z$, use the positive check $Z(g)$. Checks within either sector commute automatically. A cross-sector pair obeys

$$X(h)Z(g)=(-1)^{hg^{\mathsf T}}Z(g)X(h).$$

Consequently, the entire proposed generating set commutes exactly when

$$H_XH_Z^{\mathsf T}=0.$$

This equation says that every $X$-row support meets every $Z$-row support in an even number of coordinates. It is both a construction rule and a fast audit: one nonzero matrix entry identifies a pair of anticommuting proposed checks, so no common code space with the declared signs exists.

The row counts $m_X,m_Z$ need not equal the numbers of independent checks. Experimental schedules and decoder inputs often retain redundant checks because they can expose measurement faults or improve inference. Algebraically the code depends on the row spaces. If

$$r_X=\operatorname{rank}H_X, \qquad r_Z=\operatorname{rank}H_Z,$$

then there are $r_X+r_Z$ independent commuting Pauli constraints and

$$k=n-r_X-r_Z.$$

Duplicating a row changes $m_X$ or $m_Z$ but changes neither rank nor code space. Replacing ranks by row counts can therefore produce a negative or otherwise false value of $k$. Row reduction is only a mathematical simplification; it does not declare a redundant physical measurement useless.

All check signs here are positive. A general signed stabilizer presentation can describe another joint eigenspace with the same binary supports, but its sign consistency belongs to the general stabilizer formalism. The CSS construction in this page starts from positive $X$ and $Z$ generators and uses the binary matrices to specify their supports.

Nested classical codes without label ambiguity

The same construction can be expressed as a nested pair of classical linear codes. Freeze

$$C_2=\operatorname{row}H_X, \qquad C_1=\ker H_Z.$$

The matrix equation $H_XH_Z^{\mathsf T}=0$ is then exactly

$$C_2\subseteq C_1.$$

Taking binary orthogonal complements gives

$$C_1^\perp=\operatorname{row}H_Z, \qquad C_2^\perp=\ker H_X, \qquad C_1^\perp\subseteq C_2^\perp.$$

These familiar row-space, kernel, and duality identities are standard classical coding theory; MacWilliams and Sloane give the broader theory. They also make the converse construction immediate. Starting from $C_2\subseteq C_1$, choose rows of $H_X$ spanning $C_2$ and rows of $H_Z$ spanning $C_1^\perp$. Orthogonality then guarantees commuting CSS checks.

Classical object	Frozen identity	CSS role
$C_2$	$\operatorname{row}H_X$	Supports $X$ stabilizers and translations within one logical coset
$C_1$	$\ker H_Z$	Contains computational strings satisfying every $Z$ check
$C_1^\perp$	$\operatorname{row}H_Z$	Supports $Z$ stabilizers
$C_2^\perp$	$\ker H_X$	Contains supports commuting with every $X$ check
$C_1/C_2$	$\ker H_Z/\operatorname{row}H_X$	Labels $X$-logical translations and logical basis cosets
$C_2^\perp/C_1^\perp$	$\ker H_X/\operatorname{row}H_Z$	Labels $Z$-logical phases

Names such as $C_X$ and $C_Z$ are not uniform across the literature: one author may name a code for the errors it corrects, another for the checks it supports, and a third for the logical operators it contains. This page avoids that ambiguity by treating $H_X,H_Z$ as primary and freezing $C_2=\operatorname{row}H_X$, $C_1=\ker H_Z$. Translating another source requires checking its definitions, not merely replacing subscripts.

There is a second translation hazard. A classical parity-check matrix has a kernel as its code, whereas the rows of $H_X$ here directly generate quantum $X$ checks. Thus $H_Z$ is a parity-check matrix for $C_1$, while $H_X$ is a generator matrix for $C_2$ in the frozen dictionary. Both are called “check matrices” at the quantum level because every row becomes a measured stabilizer. Keeping the row-space and kernel identities visible prevents a classical generator matrix from being mistaken for the wrong quantum check sector.

Code Space and Logical Quotients

Independent checks and encoded dimension

An $[[n,k]]$ CSS code is the simultaneous $+1$ eigenspace of the positive checks generated by the two row spaces. Because a nonidentity commuting Pauli constraint halves the retained Hilbert-space dimension, $r_X+r_Z$ independent constraints leave

$$\dim\mathcal C=2^{n-r_X-r_Z}=2^k.$$

This dimension count agrees with the classical quotient:

$$\dim(C_1/C_2) = \dim C_1-\dim C_2 = (n-r_Z)-r_X =k.$$

The agreement is structural. The stabilizer count says how many quantum degrees of freedom remain; the quotient says how many binary coset labels are available for an orthonormal logical basis.

Redundant rows do not add constraints. Suppose a matrix contains the same $X$ row twice. Both listed operators can be measured, and comparing their records may be useful in a noisy circuit, but the second row does not halve the ideal code space again. Similarly, multiplying existing generators produces another stabilizer without raising the independent rank. A code parameter statement must therefore report ranks or an independently verified generating set.

The formula also exposes an invalid proposal quickly. Cross-commutation alone is not enough if someone declares more independent rows than the ambient dimension permits; row reduction resolves the true ranks. With the positive CSS presentation used here, the two sectors contribute additively because a nonidentity pure-$X$ Pauli cannot equal a pure-$Z$ Pauli.

Dependencies among rows have their own binary witnesses. A nonzero vector in the left kernel of $H_X$ identifies a product of listed $X$ checks equal to identity; the analogous statement holds for $H_Z$. Removing those dependencies produces a minimal algebraic generating set, but retaining them can still be operationally useful. If $k=0$, the construction gives a stabilizer state rather than an encoded logical register. The same formulas remain valid, while both logical quotient spaces become trivial.

Normalized coset-state basis

For a coset $[u]\in C_1/C_2$, define

$$\lvert[u]\rangle = \frac{1}{\sqrt{|C_2|}} \sum_{v\in C_2}\lvert u+v\rangle.$$

Changing the representative from $u$ to $u+w$ with $w\in C_2$ merely relabels the summation variable, so the state depends only on the coset. Every computational basis string appears with the same amplitude and there are $|C_2|$ distinct strings. Therefore the prefactor normalizes the state. Distinct cosets are disjoint subsets of the computational basis, which makes their states orthogonal.

An $X$ check supported on $h\in C_2$ translates every summand:

$$X(h)\lvert u+v\rangle=\lvert u+v+h\rangle.$$

Since $v\mapsto v+h$ permutes $C_2$, the sum is invariant. A $Z$ check supported on $g\in C_1^\perp$ contributes the phase

$$(-1)^{g(u+v)^{\mathsf T}}=1,$$

because both $u$ and $v$ lie in $C_1$. Thus every coset state is stabilized by both sectors. There are $2^k$ cosets, so these orthonormal states fill the entire code space.

This construction does not select a unique computational labeling of the $k$ logical qubits. A basis for $C_1/C_2$ supplies that additional choice. Different quotient bases describe the same encoded subspace but change which products of physical Paulis are called $\overline X_1,\ldots,\overline X_k$. Such changes are logical coordinate changes, not new codes.

X- and Z-logical quotient spaces

A pure-$X$ operator $X(x)$ commutes with every $Z$ check exactly when $x\in\ker H_Z=C_1$. It is an $X$ stabilizer exactly when $x\in\operatorname{row}H_X=C_2$. Hence nontrivial pure-$X$ logical supports are the quotient

$$\mathcal L_X = \frac{\ker H_Z}{\operatorname{row}H_X} = \frac{C_1}{C_2}.$$

The operator $X(x)$ translates the coset label:

$$X(x)\lvert[u]\rangle=\lvert[u+x]\rangle.$$

Likewise, a pure-$Z$ operator commutes with the $X$ checks when $z\in\ker H_X=C_2^\perp$, and it is a $Z$ stabilizer when $z\in\operatorname{row}H_Z=C_1^\perp$. Therefore

$$\mathcal L_Z = \frac{\ker H_X}{\operatorname{row}H_Z} = \frac{C_2^\perp}{C_1^\perp}.$$

For $z$ in that kernel, the phase on a coset state is constant:

$$Z(z)\lvert[u]\rangle = (-1)^{zu^{\mathsf T}}\lvert[u]\rangle,$$

because $zv^{\mathsf T}=0$ for every $v\in C_2$.

Both quotient spaces have dimension $k$. Choose row representatives $L_X,L_Z$ for quotient bases so that

$$L_XL_Z^{\mathsf T}=I_k.$$

The diagonal ones make corresponding logical $X$ and $Z$ representatives anticommute, while off-diagonal zeros make different logical-qubit pairs commute. Such paired bases exist because the induced bilinear pairing between the two quotient spaces is nondegenerate. If a proposed $X$ quotient class paired trivially with every $Z$ class, its support would lie in $(\ker H_X)^\perp=\operatorname{row}H_X$ and would therefore be trivial.

Adding a row of $H_X$ to an $X$ representative or a row of $H_Z$ to a $Z$ representative changes the physical Pauli by a stabilizer. The logical action is unchanged, although physical weight and hardware convenience can change. This equivalence is why a decoder seeks the right logical class rather than a unique microscopic error.

Asymmetric distances and full distance

Freeze the convention that $d_X$ refers to a nontrivial pure-$X$ logical and $d_Z$ to a nontrivial pure-$Z$ logical:

$$d_X = \min\left\{ \operatorname{wt}(x): x\in\ker H_Z\setminus\operatorname{row}H_X \right\},$$ $$d_Z = \min\left\{ \operatorname{wt}(z): z\in\ker H_X\setminus\operatorname{row}H_Z \right\}.$$

If the corresponding nontrivial logical-axis set is empty, take the minimum to be $+\infty$. For a nontrivial CSS code both logical quotients have dimension $k$, and the full Pauli distance is

$$d=\min(d_X,d_Z).$$

To see why mixed Paulis cannot lower this minimum, let $E(x,z)$ be a normalizer element. Its $X$ support belongs to $\ker H_Z$ and its $Z$ support belongs to $\ker H_X$. If both components are stabilizer supports, the whole operator is a stabilizer up to phase. Otherwise at least one component is a nontrivial logical class whose weight is at least $d_X$ or $d_Z$, while the weight of the union support cannot be smaller than that component’s weight.

The quotient exclusions are essential. The classical distance of $C_1$ is the minimum weight of any nonzero word in $C_1$, but that word could belong to $C_2$ and therefore be an $X$ stabilizer rather than a logical operator. Thus raw classical distances can provide useful bounds yet need not equal the exact quantum axis distances. Quotient enumeration or an equivalent proof must exclude stabilizers explicitly.

CSS does not mean symmetric protection. It is possible to have $d_X\ne d_Z$, a useful feature when one noise component dominates. The labels themselves are not universal across sources, so the support-based definitions above accompany every parameter claim. A code of distance $d$ detects every Pauli of weight below $d$ and corrects every arbitrary Pauli set of weight at most $\lfloor(d-1)/2\rfloor$; degeneracy can make selected higher-weight sets correctable without changing the distance definition.

The two axis distances can also support a more refined task statement. A known-location erasure is correctable when no nontrivial logical support fits entirely inside the erased set, so the actual support geometry matters in addition to its size. A biased-noise design may deliberately make one axis distance larger, but quoting only that favorable value would overstate full-Pauli protection. The parameter $[[n,k,d]]$ always uses the smaller axis distance; a more informative asymmetric report gives $[[n,k,(d_X,d_Z)]]$ together with the page’s frozen label convention.

Syndromes and Correctability

Separate algebraic syndrome sectors

For $E(x,z)=X(x)Z(z)$, a $Z$ check detects the $X$ component and an $X$ check detects the $Z$ component. Order the syndrome by check type:

$$s_Z=H_Zx^{\mathsf T}, \qquad s_X=H_Xz^{\mathsf T}, \qquad \sigma(E)=(s_Z\mid s_X).$$

Here $s_Z$ means “bits produced by the ordered $Z$ checks,” not “syndrome of a $Z$ error.” This naming removes a common ambiguity. In the same convention, a single $X_j$ produces column $j$ of $H_Z$ in the first sector, a single $Z_j$ produces column $j$ of $H_X$ in the second, and $Y_j$ produces both.

The equations are linear:

$$\sigma(E(x_1,z_1)E(x_2,z_2)) = \sigma(E(x_1+x_2,z_1+z_2)),$$

where an irrelevant product phase is suppressed. A syndrome therefore specifies an affine set of candidate supports. It rarely identifies a unique fault location, and it never by itself supplies a probability distribution over candidates.

Physical extraction is a separate layer. The equations assume ideal outcomes for the declared checks. Ancilla preparation, controlled-gate order, measurement faults, repeated rounds, and detector construction belong to Syndrome Measurement. Using a matrix as an ideal parity map does not certify a circuit that measures it safely.

Degeneracy in CSS language

Consider two phase-free Pauli errors $E_a=E(x_a,z_a)$ and $E_b=E(x_b,z_b)$. Their syndromes are equal exactly when

$$x_a+x_b\in\ker H_Z, \qquad z_a+z_b\in\ker H_X.$$

Equivalently, $E_a^\dagger E_b$ lies in the Pauli normalizer of the stabilizer. Equal syndrome is therefore weaker than equal action on the code. There are two possibilities. If

$$x_a+x_b\in\operatorname{row}H_X, \qquad z_a+z_b\in\operatorname{row}H_Z,$$

then the difference is a stabilizer up to phase. The errors are harmlessly degenerate: one correction class reverses both. If either quotient class is nontrivial, the difference is a logical Pauli. The errors then have the same syndrome but require incompatible logical corrections.

This is the CSS specialization of the Knill–Laflamme condition,

$$PE_a^\dagger E_bP=c_{ab}P.$$

If the product anticommutes with a check, the projected operator is zero. If it is a stabilizer, it is scalar on the code. If it is a nontrivial normalizer element, it acts logically and is not scalar, so an error set containing both members is not exactly correctable.

For a proposed phase-free recovery $R=E(r_X,r_Z)$, the residual succeeds on the code precisely when

$$x+r_X\in\operatorname{row}H_X, \qquad z+r_Z\in\operatorname{row}H_Z.$$

This condition allows a recovery to differ from the microscopic error by any stabilizer. Demanding $r_X=x$ and $r_Z=z$ would discard degeneracy and impose an unnecessary identification task.

For a fixed syndrome, choosing one representative identifies an affine normalizer coset. Quotienting that set by the stabilizer leaves the possible logical residual classes. The syndrome tells which check eigenspace contains the corrupted state; it does not select among those logical classes. This separation explains both sides of degeneracy: many physical representatives inside one stabilizer class are harmless, while two representatives in different logical classes remain indistinguishable to the checks. A decoder must use a noise model or additional records to choose among them.

When separate decoding loses information

The check equations split, but a probabilistic model need not. Let $p(x,z\mid s_Z,s_X)$ be the posterior over binary components. Independent half-decoding is exact only under assumptions strong enough to factor the relevant posterior or preserve its optimum after marginalization. A physical $Y_j$ is one event with $x_j=z_j=1$; CSS algebra does not determine whether that event arises from correlated or independently sampled components.

For example, with a one-qubit prior

$$(p_I,p_X,p_Y,p_Z)=(0.91,0.02,0.06,0.01),$$

the marginal probabilities that the $X$ and $Z$ components are present are $0.08$ and $0.07$. Multiplying them would assign $0.0056$ to their joint presence, more than a factor of ten below the true $Y$ probability $0.06$. The parity equations remain correct; the factorized statistical assumption does not.

Correlations can also come from multi-qubit mechanisms, common controls, leakage followed by return, or a syndrome circuit whose one fault propagates to several data qubits. Degeneracy adds another distinction: the desired posterior is over logical recovery classes, so probabilities of many physical representatives should be combined rather than compared one by one.

Decoders owns those likelihoods, correlations, algorithm families, confidence measures, throughput, and latency. This page supplies the algebraic interface: the two syndrome equations, stabilizer row spaces, logical quotients, and the criterion by which a candidate residual is judged.

An Unequal-Matrix Five-Qubit Detection Fixture

Frozen check matrices and stabilizers

Consider the deliberately unnamed pair

$$H_X= \begin{pmatrix} 1&1&1&1&0\\ 0&0&1&1&1 \end{pmatrix}, \qquad H_Z= \begin{pmatrix} 1&0&0&1&1\\ 0&1&1&0&1 \end{pmatrix}.$$

Every cross-row overlap has size two, so

$$H_XH_Z^{\mathsf T} = \begin{pmatrix} 0&0\\ 0&0 \end{pmatrix}.$$

Both matrices have rank two. The four independent positive stabilizer generators, in declared row order, are

$$XXXXI,\qquad IIXXX,\qquad ZIIZZ,\qquad IZZIZ.$$

They define a code with

$$k=5-2-2=1.$$

This is a compact $[[5,1,d]]$ CSS fixture constructed for the present audit. It is not the cyclic perfect Five-Qubit Code, whose mixed-Pauli generators, sixteen one-error sectors, and distance-three correction are owned by that page.

The matrices are intentionally unequal. An all-ones even-parity detector would make every $X$ location share one syndrome and every $Z$ location another. The present pair remains completely enumerable while exercising two-bit check sectors, a nontrivial nested coset basis, paired quotient representatives, and several same-syndrome logical collisions.

Logical basis and paired representatives

The $X$-check row space is

$$C_2 = \{00000,00111,11110,11001\}.$$

Solving $H_Zu^{\mathsf T}=0$ gives

$$C_1 = C_2\cup \{01100,01011,10010,10101\}.$$

Thus $C_1/C_2$ has two cosets. Their normalized states are

$$\lvert0_L\rangle = \frac12\left( \lvert00000\rangle+ \lvert00111\rangle+ \lvert11110\rangle+ \lvert11001\rangle \right),$$ $$\lvert1_L\rangle = \frac12\left( \lvert01100\rangle+ \lvert01011\rangle+ \lvert10010\rangle+ \lvert10101\rangle \right).$$

Translation by $x_L=01100$ swaps the two cosets, so a convenient logical operator is

$$\overline X=X_2X_3.$$

The support $z_L=11000$ lies in $\ker H_X$ but not in $\operatorname{row}H_Z$. Its phase is even on the first coset and odd on the second, so

$$\overline Z=Z_1Z_2.$$

Their binary pairing is

$$x_Lz_L^{\mathsf T}=1,$$

which gives the required logical anticommutation. Adding an $X$-check row to $x_L$ or a $Z$-check row to $z_L$ produces another representative of the same logical operator.

Enumeration of the two quotient spaces gives no weight-one nontrivial class. Both displayed representatives have weight two, so

$$d_X=d_Z=d=2.$$

Complete single-Pauli syndrome ledger

Apply the frozen order

$$\sigma(E)=(H_Ze_X^{\mathsf T}\mid H_Xe_Z^{\mathsf T}).$$

The ledger includes identity and every single-qubit phase-free Pauli:

Error	Z-check bits $H_Ze_X^{\mathsf T}$	X-check bits $H_Xe_Z^{\mathsf T}$	Ordered syndrome
$I$	00	00	00|00
$X_1$	10	00	10|00
$X_2$	01	00	01|00
$X_3$	01	00	01|00
$X_4$	10	00	10|00
$X_5$	11	00	11|00
$Z_1$	00	10	00|10
$Z_2$	00	10	00|10
$Z_3$	00	11	00|11
$Z_4$	00	11	00|11
$Z_5$	00	01	00|01
$Y_1$	10	10	10|10
$Y_2$	01	10	01|10
$Y_3$	01	11	01|11
$Y_4$	10	11	10|11
$Y_5$	11	01	11|01

The first half of each $X_j$ row is column $j$ of $H_Z$; the second half of each $Z_j$ row is column $j$ of $H_X$. Each $Y_j$ row is their concatenation. This column rule reconstructs the table without multiplying five-qubit matrices explicitly.

Identity and the fifteen weight-one Paulis occupy twelve syndrome sectors: one zero sector, three pure-$X$ sectors, three pure-$Z$ sectors, and five mixed sectors. Every nonidentity row has nonzero syndrome, so every weight-one Pauli is detected. Detection does not imply that all such errors are jointly correctable.

Detection without arbitrary one-qubit correction

The repeated syndromes reveal the obstruction. For example,

$$\sigma(X_2)=\sigma(X_3)=01\mid00,$$

but

$$X_2^\dagger X_3=X_2X_3=\overline X.$$

Likewise,

$$\sigma(Z_1)=\sigma(Z_2)=00\mid10, \qquad Z_1^\dagger Z_2=Z_1Z_2=\overline Z.$$

These pairs differ by nontrivial logical operators, not stabilizers. $X_1/X_4$ and $Z_3/Z_4$ form the other repeated pairs and differ by the same logical classes times stabilizers. A recovery selected from a repeated sector must therefore fail on at least one member of the corresponding pair.

The result agrees with $d=2$: the code detects all weight-one Paulis but cannot correct the complete arbitrary one-qubit set. This distinction is stronger than saying that a syndrome is “ambiguous.” Harmless degeneracy would allow the same correction to work for both candidates; a logical collision violates the scalar Knill–Laflamme condition.

Complete enumeration provides useful cross-checks. Four independent generators produce a phase-free stabilizer of size $2^4=16$. Its Pauli normalizer has size $2^{n+k}=64$, split into four logical Pauli cosets of sixteen elements each. Searching the normalizer outside the stabilizer finds weight-two representatives in both pure axes and none at weight one. Searching all $4^5=1024$ phase-free Paulis reproduces every ledger entry and collision class without changing the analytic conclusion.

Algebraic Operations and Their Limits

Bitwise CNOT between identical blocks

Take two blocks with the same $H_X,H_Z$ convention and apply CNOT from each physical control qubit to the corresponding target qubit. Conjugation gives

$$X_c(x)\longmapsto X_c(x)X_t(x), \qquad Z_c(z)\longmapsto Z_c(z),$$ $$X_t(x)\longmapsto X_t(x), \qquad Z_t(z)\longmapsto Z_c(z)Z_t(z).$$

An $X$ stabilizer on the control becomes the product of the same $X$ stabilizer on control and target; an $X$ stabilizer on the target remains there. A $Z$ stabilizer on the target becomes the corresponding product, and a control $Z$ stabilizer remains there. The joint two-block stabilizer group is therefore preserved for every CSS code.

The action is especially direct on coset states. Computational CNOT adds the control string into the target string. Summing over the two $C_2$ cosets and relabeling the target summation variable gives

$$\lvert[u]\rangle_c\lvert[v]\rangle_t \longmapsto \lvert[u]\rangle_c\lvert[u+v]\rangle_t.$$

After choosing paired quotient bases, this is a logical CNOT between corresponding logical qubits. A different quotient basis can compose that action with a logical linear coordinate change, which is why conventions must be fixed before naming individual logical wires.

This statement is algebraic. It assumes the ideal tensor product of physical CNOTs and says how stabilizers and logical classes transform. Whether one fault in the physical layer remains correctable, whether all pairings are available, and how syndrome extraction surrounds the operation are separate gadget questions.

Hadamard and phase gates need extra structure

Tensorwise Hadamard obeys

$$H^{\otimes n}X(x)H^{\otimes n}=Z(x), \qquad H^{\otimes n}Z(z)H^{\otimes n}=X(z).$$

It swaps the $X$- and $Z$-check row spaces. Bare $H^{\otimes n}$ preserves the same frozen code when those row spaces agree; it can also implement a logical operation if an explicit qubit permutation or other code equivalence returns the swapped presentation. CSS structure alone does not provide that equivalence. In the five-qubit fixture, $\operatorname{row}H_X\ne\operatorname{row}H_Z$, so bare $H^{\otimes5}$ does not preserve the declared stabilizer.

For the phase gate, the tensorwise identities are

$$S^{\otimes n}X(v)(S^\dagger)^{\otimes n} = i^{\operatorname{wt}(v)}X(v)Z(v),$$ $$S^{\otimes n}Z(v)(S^\dagger)^{\otimes n} = Z(v).$$

An $X$-check support must therefore have the necessary $Z$ support inside the $Z$-check row space, and its weight-dependent phase must reproduce the declared positive stabilizer sign. These are containment and divisibility conditions beyond CSS commutation. Logical phases then depend on the weights and pairings of quotient representatives. The Steane code supplies one exact, convention-sensitive example; it should not be promoted into a theorem about all CSS codes.

Nor does CSS structure grant a tensorwise $T$ gate. Special divisible or otherwise structured CSS families can admit transversal operations higher in the Clifford hierarchy, so the opposite slogan—“CSS transversal gates are only Clifford”—would also be false. Every claimed operation needs a code-specific stabilizer and logical-action audit.

Algebraic preservation is not fault tolerance

A physical operation may normalize a stabilizer perfectly in the absence of faults while failing as a protected gadget. A complete certificate must state the allowed input errors and internal faults, propagate them through the circuit, include ancillas and measurements, and show that every accepted output differs from the intended logical action by a correctable residual in each block. Connectivity, common-mode faults, leakage, waits, decoder timing, and surrounding correction rounds can all matter.

Bitwise CNOT has a useful containment structure because one faulty pairwise location touches at most one qubit in each block under a local fault model. That observation is not itself a proof for a particular device or syndrome schedule. Fault-Tolerant Gates owns the gadget criterion, fault-spread audits, code switching, and universal completion.

Eastin and Knill prove, under their exact finite-dimensional assumptions, that a nontrivial code detecting arbitrary errors on each physical subsystem cannot possess a universal set of transversal encoded unitaries. The theorem does not say transversal subsets are unimportant, forbid measurements or resource states, or prove that a particular algebraic transversal gate is fault tolerant under a device noise model. CSS structure and transversality answer different questions.

Chain-Complex Dictionary

Boundary maps and zero composition

The commutation equation can be displayed as two short chain complexes:

$$\mathbb F_2^{m_Z} \xrightarrow{H_Z^{\mathsf T}} \mathbb F_2^n \xrightarrow{H_X} \mathbb F_2^{m_X},$$ $$\mathbb F_2^{m_X} \xrightarrow{H_X^{\mathsf T}} \mathbb F_2^n \xrightarrow{H_Z} \mathbb F_2^{m_Z}.$$

The first composition is $H_XH_Z^{\mathsf T}=0$; the second is its transpose. Images are therefore contained in kernels, exactly as stabilizer supports are contained among normalizer supports.

The CSS commutation equation supplies two zero compositions. The middle-space quotients are $\ker H_X/\operatorname{im}H_Z^{\mathsf T}$ for $Z$-type logical supports and $\ker H_Z/\operatorname{im}H_X^{\mathsf T}$ for $X$-type logical supports. This is an algebraic dictionary: it asserts neither a spatial lattice nor a sparse Tanner graph.

Using $m_X,m_Z$ keeps the displayed maps valid when a check matrix contains dependent rows. The dimensions of the images are the ranks $r_X,r_Z$, so the middle homology dimensions still equal $k$. Replacing each check matrix by a full-row-rank basis produces a smaller presentation of the same CSS code with the same middle quotients; it discards the endpoint kernels that record relations among redundant checks.

Redundant rows appear at the ends of these sequences as nontrivial kernels of the transpose maps. They encode relations among checks rather than additional logical qubits. In a repeated-measurement setting such relations can become useful consistency constraints on outcomes, but that temporal use requires a measurement model not contained in the static complex. The middle quotient continues to describe ideal logical Pauli classes even when the endpoint spaces retain every redundant check.

Logical quotients without geometry or sparsity

The middle homology of the first sequence is

$$\frac{\ker H_X}{\operatorname{im}H_Z^{\mathsf T}} = \frac{\ker H_X}{\operatorname{row}H_Z} = \mathcal L_Z,$$

while the second gives

$$\frac{\ker H_Z}{\operatorname{im}H_X^{\mathsf T}} = \frac{\ker H_Z}{\operatorname{row}H_X} = \mathcal L_X.$$

This dictionary is useful because many code constructions can be organized by maps whose composition vanishes. It does not, by itself, supply a spatial cellulation, a boundary type, a local check schedule, or a sparse graph.

Surface Code owns the geometry of chains, boundaries, logical strings, detector graphs, and planar patches. Quantum LDPC Codes owns bounded check weight and qubit degree, Tanner graphs, redundant sparse checks, product constructions, asymptotic rate–distance results, and qLDPC-specific decoding and scheduling. A finite CSS matrix can be dense and nonlocal; the equation $\partial^2=0$ alone says nothing about low density or hardware locality.

Canonical Owners and Boundaries

What this page owns and where to continue

This page owns the general conversion among positive binary check matrices, nested classical codes, normalized coset states, logical quotient spaces, axis distances, ordered CSS syndromes, and the Pauli correctability classification. It also owns the algebraic statement that bitwise CNOT preserves identical CSS blocks and the extra-structure warnings for Hadamard and phase gates.

Stabilizer Formalism retains general Pauli and symplectic algebra, projectors, normalizers, Cliffords, and tableaus. Why Quantum Error Correction Is Possible retains the general exact and approximate correctability theorems. Shor and Steane retain their complete finite code conventions, ledgers, recoveries, distance proofs, and code-specific operations; Five-Qubit Code retains the perfect non-CSS comparison.

Syndrome Measurement owns physical check instruments and detector records; Decoders owns probabilistic logical-class inference; Fault-Tolerant Gates owns protected gadgets and universal completion. Surface Code retains patch geometry and lattice surgery, while Quantum LDPC Codes retains sparsity, Tanner graphs, product families, asymptotics, and architecture evidence.

Color Codes owns 2-colex face checks, colored boundaries, topological logical representatives, and family-specific gate and decoder tradeoffs. Topological Codes owns local-check topology, homological syndromes, and active-versus-passive protection. Subsystem Codes owns gauge centers, bare and dressed logical quotients, gauge-derived syndromes, and Bacon–Shor constructions. This page retains the shared CSS matrix and subspace-code algebra rather than duplicating either specialization.

The same boundary applies to claims about performance. A valid pair $H_X,H_Z$ and a large algebraic distance do not establish a threshold, decoder runtime, hardware overhead, or experimental advantage. Those claims need a code family, extraction circuit, fault model, decoder, logical task, and evidence at the appropriate layer. Conversely, a hardware demonstration of one CSS block does not redefine the general construction. The matrices and quotients here are the stable interface through which those specialized owners state their additional assumptions.

Exercises

1. Convert a nested pair into CSS checks

For the five-qubit fixture, take $C_2=\operatorname{span}\{11110,00111\}$ and the displayed eight-word $C_1$. Construct $H_X$ from a spanning list in which 11110 is deliberately repeated, construct $H_Z$ from a basis of $C_1^\perp$, and determine $m_X,m_Z,r_X,r_Z,k$. Explain why the repeated physical parity equation may be recorded but does not encode one fewer logical qubit.

Solution

One permitted matrix is

$$H_X'= \begin{pmatrix} 1&1&1&1&0\\ 0&0&1&1&1\\ 1&1&1&1&0 \end{pmatrix}, \qquad H_Z= \begin{pmatrix} 1&0&0&1&1\\ 0&1&1&0&1 \end{pmatrix}.$$

Every row of $H_X'$ lies in $C_1$, so $H_X'H_Z^{\mathsf T}=0$. The listed row counts are $m_X=3,m_Z=2$, but the first and third rows of $H_X'$ coincide. Hence $r_X=2,r_Z=2$ and

$$k=5-r_X-r_Z=1.$$

The repeated row does not enlarge $\operatorname{row}H_X'$ and therefore does not add a stabilizer constraint. Measuring it twice could create two noisy records for inference, but the ideal common eigenspace is unchanged. Using $m_X+m_Z$ in the dimension formula would incorrectly give $k=0$.

2. Normalize the coset-state basis

For arbitrary $C_2\subseteq C_1$, prove that

$$\lvert[u]\rangle = |C_2|^{-1/2}\sum_{v\in C_2}\lvert u+v\rangle$$

is independent of the representative $u$, is normalized, is orthogonal to states from different cosets, and is stabilized by $X(C_2)$ and $Z(C_1^\perp)$.

Solution

If $u'=u+w$ with $w\in C_2$, then $v\mapsto v+w$ permutes $C_2$, so the two sums are identical. The map $v\mapsto u+v$ is injective, giving $|C_2|$ distinct orthonormal computational states; the squared norm is therefore $|C_2|^{-1}|C_2|=1$. Distinct cosets are disjoint, so their computational supports have zero overlap.

For $h\in C_2$, $X(h)$ sends the summand labeled by $v$ to the one labeled by $v+h$, another permutation of the sum. For $g\in C_1^\perp$,

$$g(u+v)^{\mathsf T}=0$$

because $u,v\in C_1$, so $Z(g)$ gives phase $+1$ to every summand. The coset states are common $+1$ eigenstates of all declared checks. Their number is $|C_1/C_2|=2^k$, so they form a full logical basis.

3. Construct paired logical quotient bases

Show that the pairing between $\ker H_Z/\operatorname{row}H_X$ and $\ker H_X/\operatorname{row}H_Z$ is well defined and nondegenerate. Then use $x_L=01100$ and $z_L=11000$ to construct the paired basis for the fixture.

Solution

The pairing is $xz^{\mathsf T}$. Adding $h\in\operatorname{row}H_X$ to $x$ does not change it because $z\in\ker H_X$. Adding $g\in\operatorname{row}H_Z$ to $z$ does not change it because $x\in\ker H_Z$. It is therefore well defined on quotient classes.

If an $X$ class pairs to zero with every $Z$ class, its representative is orthogonal to $\ker H_X$. Hence it belongs to

$$(\ker H_X)^\perp=\operatorname{row}H_X$$

and is the trivial $X$ class. The same argument with sectors exchanged proves nondegeneracy on the other side. Equal quotient dimensions then permit bases with $L_XL_Z^{\mathsf T}=I_k$.

For the fixture, both quotients have dimension one. $01100\cdot11000^{\mathsf T}=1$, so the single-row matrices $L_X=(01100)$ and $L_Z=(11000)$ already satisfy the required identity.

4. Rebuild the unequal-matrix detection fixture

Starting only from the four generators

$$XXXXI,\quad IIXXX,\quad ZIIZZ,\quad IZZIZ,$$

reconstruct $H_X,H_Z$, verify commutation and ranks, find $C_2$ and $C_1$, and derive the two logical basis states and both axis distances.

Solution

Reading supports gives

$$H_X= \begin{pmatrix} 1&1&1&1&0\\ 0&0&1&1&1 \end{pmatrix}, \qquad H_Z= \begin{pmatrix} 1&0&0&1&1\\ 0&1&1&0&1 \end{pmatrix}.$$

The four cross inner products vanish, and each matrix has rank two. Thus $k=5-2-2=1$. Spanning the $H_X$ rows gives

$$C_2=\{00000,11110,00111,11001\}.$$

Solving $H_Zu^{\mathsf T}=0$ adds the coset

$$01100+C_2=\{01100,10010,01011,10101\}.$$

Uniform normalized sums over these two cosets give the displayed $|0_L\rangle$ and $|1_L\rangle$. The supports $01100$ and $11000$ represent nontrivial paired logical $X$ and $Z$ operators of weight two. Direct kernel enumeration finds no weight-one nontrivial class in either quotient, so $d_X=d_Z=d=2$.

5. Diagnose a same-syndrome logical collision

Reconstruct the complete sixteen-entry identity-plus-single-Pauli ledger from the columns of $H_X,H_Z$. Then compare $X_2$ with $X_3$ and $Z_1$ with $Z_2$. Apply the Pauli-specialized Knill–Laflamme condition to explain why the complete weight-one Pauli set is not correctable even though every nonidentity member has nonzero syndrome.

Solution

Identity gives 00|00. The five $X_j$ rows copy the ordered columns of $H_Z$ into the first half:

$$10,\ 01,\ 01,\ 10,\ 11.$$

The five $Z_j$ rows copy the columns of $H_X$ into the second half:

$$10,\ 10,\ 11,\ 11,\ 01.$$

Each $Y_j$ row concatenates the corresponding two columns. This reconstructs all sixteen rows in the displayed order and gives twelve occupied sectors: identity, three pure-$X$, three pure-$Z$, and five mixed sectors.

The two $X$ errors both have syndrome $01\mid00$, while the two $Z$ errors both have syndrome $00\mid10$. Their pairwise products are

$$X_2^\dagger X_3=X_2X_3=\overline X, \qquad Z_1^\dagger Z_2=Z_1Z_2=\overline Z.$$

Both products commute with every stabilizer, as equality of syndromes requires, but neither belongs to the stabilizer. They act nontrivially on the logical qubit. Consequently $PE_a^\dagger E_bP$ is a logical Pauli restricted to the code rather than a scalar multiple of $P$.

In this fixture every nonidentity weight-one Pauli has nonzero syndrome, so each is detectable. More generally, a stabilizer error has zero syndrome but is also detectable in the Knill–Laflamme sense because it acts scalarly on the code. Correction of an entire set additionally requires every pair either to have distinct syndromes or to differ by a stabilizer. These repeated sectors fail that pairwise condition, consistently with distance two.

6. Retain correlations between CSS syndrome halves

For the one-qubit prior

$$(p_I,p_X,p_Y,p_Z)=(0.91,0.02,0.06,0.01),$$

compute the marginal probabilities that the binary $X$ and $Z$ components are present. Compare the product of those marginals with the true joint probability, and state what this does and does not imply about CSS decoding.

Solution

The $X$ component is present for physical $X$ or $Y$, so its marginal is

$$p(x=1)=p_X+p_Y=0.08.$$

The $Z$ component is present for $Z$ or $Y$, giving

$$p(z=1)=p_Z+p_Y=0.07.$$

If the components were independent, their joint probability would be $0.08\times0.07=0.0056$. The actual joint event is physical $Y$, with probability $0.06$. The product model understates it by a factor $0.06/0.0056\approx10.7$.

Nothing is wrong with the CSS equations $s_Z=H_Zx^{\mathsf T}$ and $s_X=H_Xz^{\mathsf T}$; they remain exact. What fails is the extra factorized prior. Separate decoders are optimal only under appropriate noise and decision assumptions. A general decoder should retain joint information and sum probabilities over stabilizer-equivalent physical representatives when comparing logical classes.

7. Test algebraic transversal operations

Prove that bitwise CNOT preserves two identical CSS blocks. Then decide what bare tensorwise Hadamard and phase gates do to the five-qubit fixture, and explain why none of these algebraic calculations alone establishes a fault-tolerant universal gate set.

Solution

Under bitwise CNOT, a control $X(h)$ becomes $X(h)$ on both blocks and a target $Z(g)$ becomes $Z(g)$ on both blocks. These products remain in the joint stabilizer, while target $X(h)$ and control $Z(g)$ remain unchanged. The logical cosets transform as $([u],[v])\mapsto([u],[u+v])$, so paired quotient bases see logical CNOT.

Hadamard swaps the two row spaces. The fixture has $\operatorname{row}H_X\ne\operatorname{row}H_Z$, so bare $H^{\otimes5}$ does not preserve its exact stabilizer. Tensorwise $S$ maps $X(v)$ to $i^{\operatorname{wt}(v)}X(v)Z(v)$. The first $X$ support 11110 has weight four and lies in $\operatorname{row}H_Z$, but the second, 00111, has weight three and is not in $\operatorname{row}H_Z$. Its image therefore fails both the required $Z$-support containment and the positive stabilizer phase/sign condition. Bare $S^{\otimes5}$ does not preserve the fixture.

Even a preserving tensor product must be audited under faults, ancillas, measurements, and recovery. Eastin–Knill also forbids a universal transversal unitary set under its assumptions. Algebraic normalization, fault tolerance, and universality are three distinct claims.

8. Audit a chain complex and its ownership boundary

For general $H_X,H_Z$, verify both zero compositions, identify the two middle homologies, and list one additional assumption needed to infer each of: geometric locality, a qLDPC presentation, and a physical extraction circuit.

Solution

The CSS equation gives

$$H_XH_Z^{\mathsf T}=0,$$

and transposition gives

$$H_ZH_X^{\mathsf T}=0.$$

Therefore the middle homologies are

$$\ker H_X/\operatorname{im}H_Z^{\mathsf T}=\mathcal L_Z, \qquad \ker H_Z/\operatorname{im}H_X^{\mathsf T}=\mathcal L_X.$$

No geometry follows without an embedding or cellulation that assigns the binary coordinates and maps to spatial objects. No qLDPC claim follows without a family of presentations having uniformly bounded row and column weights. No extraction circuit follows without ancillas, a gate schedule, preparation and measurement conventions, and a fault model. The chain complex captures zero composition and logical quotients; Surface Code, Quantum LDPC Codes, and Syndrome Measurement own those three additional layers respectively.

References

• A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” Physical Review A 54, 1098–1105 (1996), doi:10.1103/PhysRevA.54.1098.
• B. Eastin and E. Knill, “Restrictions on transversal encoded quantum gate sets,” Physical Review Letters 102, 110502 (2009), doi:10.1103/PhysRevLett.102.110502.
• D. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, California Institute of Technology (1997), doi:10.7907/rzr7-dt72, arXiv:quant-ph/9705052.
• E. Knill and R. Laflamme, “Theory of quantum error-correcting codes,” Physical Review A 55, 900–911 (1997), doi:10.1103/PhysRevA.55.900.
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library 16, North-Holland, Amsterdam (1977), ISBN 978-0-444-85009-6.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary ed., Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• A. M. Steane, “Error correcting codes in quantum theory,” Physical Review Letters 77, 793–797 (1996), doi:10.1103/PhysRevLett.77.793.
• A. M. Steane, “Simple quantum error-correcting codes,” Physical Review A 54, 4741–4751 (1996), doi:10.1103/PhysRevA.54.4741.