CSS Codes

Calderbank–Shor–Steane (CSS) codes are quantum stabilizer codes whose checks can be chosen to contain only X operators or only Z operators. Their construction turns a pair of compatible classical binary spaces into a quantum code. The central condition is simple: every X-check support must overlap every Z-check support an even number of times.

The separation makes code construction and syndrome calculations easier, but does not make physical bit and phase errors statistically independent. We will build a small example, use it to explain logical quotient spaces and distance, and then identify which transversal gates follow from CSS structure. These ideas arose in the constructions of Calderbank and Shor (1996) and Steane (1996).

Required background. Stabilizer Formalism supplies Pauli commutation, code projectors, and error syndromes. Helpful background. Steane Code gives a familiar CSS example; Why Quantum Error Correction Is Possible explains exact correctability.

Commuting X and Z checks

All binary arithmetic below is modulo two. Write length-n support vectors as rows, with qubit 1 on the left in displayed strings. Define $X(x)$ and $Z(z)$ as products of X and Z on the nonzero positions of x and z. Then

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

A Y at site j has both $x_j=z_j=1$, since $Y=iXZ$. We ignore global Pauli phases when discussing supports and syndromes, while retaining them when calculating an operator’s action.

Let each row of $H_X$ specify a positive X check, and each row of $H_Z$ a positive Z check. Positive means that the code is in the check’s $+1$ eigenspace. Same-type checks commute automatically. Cross-type checks all commute exactly when

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

The matrix entry at row a, column b is the overlap parity of X check a and Z check b. If an entry is one, those two proposed checks anticommute and cannot have a common eigenstate.

Let $r_X$ and $r_Z$ be the binary ranks of the two matrices. The number of encoded qubits is

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

There are $r_X+r_Z$ independent constraints, each halving the Hilbert-space dimension. Ranks, rather than numbers of listed rows, matter. Repeating a check or adding a product of existing checks adds no new constraint. Such extra measurements may still be useful when their outcomes are noisy.

Two nested classical spaces

Define

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

Commutation is precisely the inclusion $C_2\subseteq C_1$. The Z checks restrict computational strings to $C_1$, while X checks translate strings by elements of $C_2$. Conversely, any nested pair $C_2\subseteq C_1$ supplies CSS checks by taking $H_X$ to generate $C_2$ and $H_Z$ to generate $C_1^\perp$.

For each coset $[u]=u+C_2$ in $C_1/C_2$, form

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

A coset is the group of strings reachable from u by adding elements of $C_2$. Each X check permutes those strings, leaving their equal superposition unchanged. Each Z check gives phase $+1$ because every string is in $C_1$. Different cosets are disjoint, so their normalized superpositions are orthogonal. There are

$$2^{\dim C_1-\dim C_2}=2^k$$

such states: a complete logical basis. This is why classical redundancy can protect quantum amplitudes without copying an unknown state. The amplitudes multiply entire coset superpositions.

The notation $C_1,C_2$ is not uniform across sources. The explicit kernel and row-space definitions above determine its meaning here; at the classical level $H_X$ generates $C_2$, while $H_Z$ checks $C_1$.

A five-qubit example: detecting is easier than correcting

Consider

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

Every cross-row overlap is two, so the checks commute. Both matrices have rank two, giving $k=5-2-2=1$. Their generators are $XXXXI$, $IIXXX$, $ZIIZZ$, and $IZZIZ$. This example will have distance two; it differs from the non-CSS perfect five-qubit code.

The X-check row space consists of

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

The kernel of $H_Z$ has these four words and the second coset $01100+C_2$. Thus $0_L$ is the equal superposition of the four C₂ words, and $1_L$ the equal superposition of their sums with $01100$. Each amplitude is $1/2$.

Each column represents a normalized superposition of four strings. Adding an X-check word, such as $11110$, only permutes strings within a column. Adding $01100$ exchanges the columns and acts as $\overline X=X_2X_3$. The phase from $\overline Z=Z_1Z_2$ is constant within each column and opposite between them.

Indeed, $X_2X_3$ exchanges the two cosets, while $Z_1Z_2$ has even overlap with every word in the first coset and odd overlap with every word in the second. We can choose

$$\overline X=X_2X_3, \qquad\overline Z=Z_1Z_2.$$

Their single overlapping X/Z site makes them anticommute.

For errors, write the Z-check bits first and the X-check bits second. The columns of $H_Z$ give X-error syndromes, while the columns of $H_X$ give Z-error syndromes:

Site j	X-error bits from Z checks	Z-error bits from X checks
1	$10$	$10$
2	$01$	$10$
3	$01$	$11$
4	$10$	$11$
5	$11$	$01$

A Y error has both listed halves. All single-qubit nonidentity Paulis have nonzero syndrome, so each is detected. However,

$$s(X_2)=s(X_3)=(01,00),$$

while $X_2^\dagger X_3=\overline X$. These two errors have the same syndrome and differ by a logical operation. No recovery can correct both for an arbitrary encoded state. The same problem occurs for $Z_1$ and $Z_2$, whose product is $\overline Z$.

The code detects an unknown one-qubit error, but cannot correct the entire set of such errors. It can correct an arbitrary error at a known single location, as Exercise 8 explains. Knowing where an error occurred changes the correction problem.

Logical operators as quotient spaces

An X operator commutes with all Z checks when its support is in $\ker H_Z$. If its support is also in $\operatorname{row}H_X$, it is a stabilizer and does nothing to a code state. Thus

$$\mathcal L_X=\ker H_Z/\operatorname{row}H_X.$$

The slash identifies two supports when their difference is an X-stabilizer support. In the example, adding either X-check row to $01100$ changes the physical representative but preserves its logical action. This quotient is exactly $C_1/C_2$: X logical operators translate logical coset labels.

Similarly,

$$\mathcal L_Z=\ker H_X/\operatorname{row}H_Z.$$

For $z\in\ker H_X$, the phase $(-1)^{zu^{\mathsf T}}$ is constant throughout each coset, so

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

Both logical spaces have binary dimension k. To label k logical qubits, choose representative matrices $L_X,L_Z$ satisfying

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

The diagonal ones give anticommutation within each logical X/Z pair; the off-diagonal zeros give commutation between different logical qubits. Such paired bases exist because the induced pairing of quotient spaces is nondegenerate. Exercise 3 proves this without choosing a particular code.

Axis distances and the full distance

For $k>0$, define $d_X$ and $d_Z$ as minimum weights of nontrivial pure-X and pure-Z logical supports:

$$\begin{aligned} d_X&=\min_{x\in\ker H_Z\setminus\operatorname{row}H_X}\operatorname{wt}(x),\\ d_Z&=\min_{z\in\ker H_X\setminus\operatorname{row}H_Z}\operatorname{wt}(z). \end{aligned}$$

Some sources reverse axis labels according to which errors a check detects, so the support-based definitions matter. The full Pauli distance is

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

To see why mixed Paulis cannot do better, take a zero-syndrome Pauli $(x,z)$. If both components are stabilizer supports, their product is a stabilizer up to global phase. Otherwise at least one component is a nontrivial logical support. Its weight is at least the corresponding axis distance, and the union of the X and Z supports cannot be smaller than that component. Pure-axis representatives attain the smaller bound.

In the five-qubit example, neither kernel has a weight-one word because neither check matrix has a zero column. The displayed weight-two logical representatives therefore prove $d_X=d_Z=d=2$.

Excluding stabilizers in these minima is essential. A low-weight classical kernel word may represent a harmless stabilizer rather than a logical error. For example, a same-block $ZZ$ in the Shor code has weight two and zero syndrome but is a stabilizer; the minimum nontrivial logical Z still has weight three. Raw classical distances can therefore underestimate a quantum axis distance.

CSS does not require equal protection along the two axes. The bit-repetition example in Exercise 4 has $d_X=3$ and $d_Z=1$. If $k=0$, both quotients are trivial and the construction gives a stabilizer state; a distance defined by a nontrivial logical operator has no finite minimum.

Syndrome equations and recovery choices

For a Pauli with binary components $(x,z)$,

$$s_Z=H_Zx^{\mathsf T}, \qquad s_X=H_Xz^{\mathsf T}.$$

The subscript names the check type, not the error type. Z checks detect X components and X checks detect Z components. A Y event contributes to both. Linear addition of supports gives linear addition of syndromes.

Two errors with the same syndrome can differ in two importantly different ways:

• Their component differences lie in $\operatorname{row}H_X$ and $\operatorname{row}H_Z$. Their product is a stabilizer up to phase, so a single correction works for both. This is harmless degeneracy.
• At least one difference represents a nonzero logical quotient class. Their product acts on the encoded information, so they cannot both be corrected as part of the same arbitrary-state error set.

This is the Pauli form of the Knill–Laflamme condition, $PE_a^\dagger E_bP=c_{ab}P$. Different syndromes give a zero projected cross term; a stabilizer product gives a scalar; a nontrivial logical product fails the condition. For the full stabilizer treatment, see Gottesman (1997).

If a decoder chooses correction components $(r_x,r_z)$, successful recovery requires

$$\begin{aligned} x+r_x&\in\operatorname{row}H_X,\\ z+r_z&\in\operatorname{row}H_Z. \end{aligned}$$

Matching the syndrome ensures return to the code space, but the stronger row-space conditions ensure the original logical state is restored.

Separate equations do not imply independent noise

Suppose the one-qubit Pauli probabilities are

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

The marginal probabilities for X and Z components are 0.08 and 0.07. Their product is 0.0056, whereas the true probability that both occur—the Y probability—is 0.06. Multiplying the marginals would erase a strong correlation.

Under Pauli noise, a decoder seeking the most likely logical recovery class should add the probabilities of all physical errors in that stabilizer class. Selecting the single most likely physical error need not select the most likely logical class. Separate X/Z decoding can be effective, but its optimality depends on the noise distribution and decision rule; it does not follow from the split syndrome equations. Decoders develops these inference choices. Actual check measurements and noisy repeated outcomes are treated in Syndrome Measurement.

Transversal gates and extra algebraic conditions

Apply coordinatewise CNOT between two identical CSS blocks. A control X check becomes the product of the matching X checks on both blocks; a target Z check becomes the product of the matching Z checks. The remaining checks are unchanged. Hence the joint stabilizer is preserved for every CSS code.

On coset states the action is

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

With the same logical coordinates in both blocks, this implements CNOT on each corresponding pair of logical qubits. It follows by relabeling the target summation variable after binary addition, as in the Steane-code derivation.

Hadamard exchanges X and Z supports. Bare $H^{\otimes n}$ preserves the positive CSS code exactly when the two check row spaces agree. Unequal matrices can still describe equal row spaces, so compare spans rather than printed rows. Otherwise the operation maps to the code with the two spaces exchanged; a further permutation may sometimes restore the original code. CSS structure alone does not supply such a permutation.

For $S=\operatorname{diag}(1,i)$,

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

For the positive-check convention, bitwise S preserves the code when every X-check generator has weight divisible by four and its support belongs to the Z-check row space. These conditions ensure both the correct support and the correct sign of each image; the Z checks are unchanged. The induced logical phase still needs to be calculated. In the Steane basis, physical bitwise S implements logical $S^\dagger$.

The five-qubit example fails both bare H and bare S preservation. Its two row spaces differ, and the X check $IIXXX$ has odd weight and no matching Z-stabilizer support. Specialized CSS families can admit non-Clifford transversal operations, so “CSS means only Clifford gates” is also incorrect.

Transversality limits propagation within a block under an appropriate local fault model; full protection also requires preparation, measurement, and recovery procedures. Fault-Tolerant Gates treats those constructions. The Eastin–Knill theorem rules out a universal entirely transversal unitary set for a nontrivial finite-dimensional code detecting arbitrary errors on each physical subsystem.

A short connection to chain complexes

Using column coordinates for the linear maps, CSS commutation gives

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

The composition is zero, so the image of the first map lies inside the kernel of the second. Their quotient at the middle space is $\mathcal L_Z$: undetectable Z supports, with Z stabilizers identified as trivial. Exchanging X and Z gives the analogous description of $\mathcal L_X$.

Here $m_X,m_Z$ are row counts, including any dependent rows; the dimensions of the images are the ranks. Relations among redundant checks appear at the ends of the sequence and do not add logical qubits. This algebra becomes geometric in the surface code. To obtain a quantum LDPC family one additionally needs uniformly bounded check weights and qubit degrees. Zero composition alone imposes neither locality nor sparsity.

Exercises

1. Add a redundant check

Repeat the first row of $H_X$ in the five-qubit example. Find the row counts, ranks, and number of logical qubits. Interpret the dependence among the listed checks.

Solution

The row counts become $m_X=3,m_Z=2$, while $r_X=r_Z=2$. Thus $k=5-2-2=1$ remains unchanged. Multiplying the first and third X checks gives identity, so their ideal outcomes must agree. Measuring them at separate times could supply two noisy observations, but repeating a row does not halve the ideal code space again. Using row counts in place of ranks would incorrectly give $k=0$.

2. Why is a coset superposition well defined?

Prove that the normalized state for $[u]$ is unchanged when u is replaced by another representative. Show that the coset states form an orthonormal basis of the quantum code.

Solution

Replacing u by $u+w$, with $w\in C_2$, changes the summation variable from v to $v+w$, a permutation of $C_2$. There are $|C_2|$ distinct computational basis states in each sum, each with squared amplitude $1/|C_2|$, so its norm is one. Different cosets are disjoint and give zero overlap.

X checks permute terms. Z checks contribute $+1$ because their supports lie in $C_1^\perp$ and every summand is in $C_1$. The number of orthonormal states is $|C_1/C_2|=2^k$, equal to the common eigenspace dimension. They therefore form a basis of that space.

3. Pair logical X and Z classes

Prove that $xz^{\mathsf T}$ is well defined and nondegenerate on the two logical quotients. Verify the pairing for the five-qubit example.

Solution

Adding an X-check row to x leaves the pairing unchanged because $z\in\ker H_X$. Adding a Z-check row to z also leaves it unchanged because $x\in\ker H_Z$. Thus the pairing depends only on quotient classes.

If x pairs to zero with every z in $\ker H_X$, then

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

so its logical class is zero. The reverse argument is identical. The pairing is therefore nondegenerate and admits dual bases with $L_XL_Z^{\mathsf T}=I_k$. In the example, $01100\cdot11000^{\mathsf T}=1$, which verifies the logical anticommutation.

4. Find unequal axis distances

Take three qubits with no X checks and Z-check rows $110$ and $011$. Compute $k,d_X,d_Z$, and d using quotient spaces.

Solution

The ranks are zero and two, so $k=1$. The kernel of $H_Z$ is $\{000,111\}$, and the X-stabilizer space is zero; hence $d_X=3$. The kernel of the empty X-check matrix is all $\mathbb F_2^3$. The Z-stabilizer row space consists of the four even-weight words, so a single Z is a nontrivial logical operation and $d_Z=1$. Thus $d=1$.

This is bit repetition: it corrects one bit flip but leaves phase information unprotected. A single favorable axis distance does not establish correction of an arbitrary one-qubit error.

5. Detection versus a common recovery

Use the five-qubit columns to count the distinct syndromes of the identity and all single-qubit Paulis. Explain why $X_2$ and $X_3$ obstruct joint correction.

Solution

The X errors occupy three nonzero syndromes in the first half. The Z errors occupy three in the second half. The Y errors occupy five distinct pairs with both halves nonzero. Including identity gives $1+3+3+5=12$ sectors. All 15 nonidentity single-qubit Paulis are detected.

But $X_2$ and $X_3$ have the same syndrome and product $X_2X_3=\overline X$. Thus their Knill–Laflamme cross term is a logical X on the code, not a scalar. Choosing correction $X_2$ restores an $X_2$ error but changes the logical state after an $X_3$ error. This is a logical ambiguity, whereas stabilizer-equivalent errors would admit the same correction.

6. Check the statistical assumption

For the Pauli probabilities in the text, calculate the X/Z-component covariance and compare the actual Y probability with a product model.

Solution

The binary component means are $\mathbb E[x]=0.08$ and $\mathbb E[z]=0.07$. Their product moment is $\mathbb E[xz]=p_Y=0.06$, so

$$\begin{aligned} \operatorname{Cov}(x,z)&=0.06-0.08(0.07)\\ &=0.0544. \end{aligned}$$

The product model gives $p_Y=0.0056$, about 10.7 times smaller than the actual value. Both models would use the same exact CSS syndrome equations. Their different joint probabilities can nevertheless lead to different preferred recovery classes.

7. Test three transversal operations

Show that coordinatewise CNOT preserves two copies of the five-qubit example, and determine whether bare tensorwise H or S preserves one copy.

Solution

Under CNOT, control X checks and target Z checks become matching-check products on the two blocks, so the joint stabilizer is preserved. The two coset labels transform as $(a,b)\mapsto(a,a+b)$, giving logical CNOT.

H exchanges the row spaces. They are unequal, so $H^{\otimes5}$ does not preserve the original code. For S, the first X support $11110$ is a Z-stabilizer support and has weight four. The second support $00111$ has weight three and is absent from the Z-stabilizer space. Its conjugate is therefore not a stabilizer with the required sign, and $S^{\otimes5}$ also fails to preserve the code. CSS structure guarantees the stated CNOT construction, but the other two gates require extra conditions.

8. Correct one known erasure

Explain why the distance-two example can recover after loss of one known physical qubit, despite failing to correct an error at an unknown single location. Why can the pair of lost sites $\{2,3\}$ not be corrected?

Solution

For a known site j, consider the error basis $\{I,X_j,Y_j,Z_j\}$. Products of two members are either scalar or a Pauli on that same site. Every nonscalar such Pauli has nonzero syndrome, so all projected cross terms satisfy Knill–Laflamme. This correctability criterion also characterizes recovery from erasure of that site after supplying a replacement subsystem. The recovery may depend on the known lost location.

Unknown-location correction must include errors on every site in one common error set, introducing the incompatible pair $X_2,X_3$. For erasure of sites $\{2,3\}$, the entire logical operator $\overline X=X_2X_3$ is supported on the lost set. The erasure criterion therefore fails: the lost subsystem can carry logical information. The locations and supports matter, not only the number of erased qubits.

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, arXiv:quant-ph/9512032.
• 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.
• A. M. Steane, “Error correcting codes in quantum theory,” Physical Review Letters 77, 793–797, 1996, doi:10.1103/PhysRevLett.77.793.