Steane Code

The Steane code uses seven physical qubits to protect one logical qubit against an arbitrary error on any one of them. Its central idea is to use the same classical Hamming checks twice: once to diagnose bit flips and once to diagnose phase flips. The resulting $[[7,1,3]]$ code also supports simple physical implementations of logical Clifford gates.

We will build the code from a small binary matrix, decode its syndromes, and derive those logical gates—including the easily missed direction of the phase gate. Encoding, measurements, and gates are assumed ideal. The construction originates in Steane’s 1996 work; his longer treatment develops the classical-code connection.

Required background. Stabilizer Formalism explains commuting Pauli checks, code projectors, logical operators, and error syndromes. Binary addition below is modulo two.

A Hamming matrix for both kinds of error

Number the qubits $1,\ldots,7$, with qubit 1 on the left in written strings. Use the classical check matrix

$$H_c=\begin{pmatrix} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1 \end{pmatrix}.$$

The subscript distinguishes this binary matrix from the quantum Hadamard gate $H$. Its columns $h_j$ are the binary representations of the integers $j=1,\ldots,7$, written with the most significant bit first. Thus a classical single-bit error at location 5 has syndrome $h_5=101$.

Define

$$C=\ker H_c, \qquad D=\operatorname{row}(H_c)=C^\perp.$$

The three independent rows give $\dim C=4$ and $\dim D=3$. Each row has weight four, and distinct rows overlap twice. Therefore

$$H_cH_c^{\mathsf T}=0, \qquad D\subset C.$$

This inclusion is the crucial compatibility condition. The classical code is dual-containing, not literally self-dual: $C$ and $C^\perp$ have different dimensions. The quantum code is often called weakly self-dual because its X and Z checks have identical supports.

No nonzero word of weight one or two belongs to $C$: such a word would require a zero column or two equal columns of $H_c$. But $h_1+h_2+h_3=000$, so $1110000\in C$. Thus $C$ is the classical $[7,4,3]$ Hamming code. The eight words of $D$ consist of zero and seven words of weight four; $D$ is the $[7,3,4]$ simplex code.

From classical words to quantum superpositions

Let $\mathbf1=1111111$. Define

$$\begin{aligned} \lvert0_L\rangle&=\frac1{\sqrt8}\sum_{u\in D}\lvert u\rangle,\\ \lvert1_L\rangle&=\frac1{\sqrt8}\sum_{u\in D}\lvert\mathbf1+u\rangle. \end{aligned}$$

Each state has eight equal amplitudes. The two sets of strings are disjoint because $\mathbf1\notin D$, so the states are orthogonal. The first contains words of weights zero and four; the second contains their complements, of weights seven and three. An arbitrary logical state is their coherent superposition, not a classical choice of a codeword.

For a binary word $r$, write $X(r)$ and $Z(r)$ for products of X and Z on its nonzero positions. Each row $r_a$ of $H_c$ supplies a positive-signed check $Z(r_a)$ and another $X(r_a)$. For example,

$$\begin{aligned} Z(r_1)&=Z_4Z_5Z_6Z_7,\\ X(r_1)&=X_4X_5X_6X_7. \end{aligned}$$

An X check translates $u$ by a word in $D$, merely permuting the sum in either logical state. A Z check contributes phase $(-1)^{r_a\cdot u}=1$; it also gives $+1$ on the complement coset because $r_a$ has even weight. Thus all six checks stabilize both states. Their commutation follows from $H_cH_c^{\mathsf T}=0$.

The six checks are independent, so their common $+1$ eigenspace has dimension $2^{7-6}=2$. They therefore define exactly the two-dimensional space above. This is a concrete instance of the CSS construction, rather than two independent classical copies of an unknown qubit.

Filled disks mark the qubits included in a check. The rows $r_a$ specify check supports; the columns $h_j$ locate errors. The highlighted fifth column is $101$: an $X_5$ error flips the first and third Z checks, while a $Z_5$ error flips the corresponding X checks. The connecting lines are table guides, not circuit wires.

Logical Paulis and distance three

Choose

$$\overline X=X^{\otimes7}, \qquad \overline Z=Z^{\otimes7}.$$

Bitwise X complements every string and exchanges the two logical states. Bitwise Z gives $+1$ on the even-weight first coset and $-1$ on the odd-weight second coset. These are the actions defining logical X and Z. Their seven anticommuting overlaps make them anticommute with one another, while even check weights make them commute with the stabilizer.

They are not minimum-weight representatives. Multiplication by the checks on sites $4,5,6,7$ gives equivalent logical operators

$$\overline X\sim X_1X_2X_3, \qquad \overline Z\sim Z_1Z_2Z_3,$$

where $\sim$ means the same action on encoded states.

To prove that no lower-weight logical Pauli exists, represent a physical Pauli up to global phase by $(x,z)$. Commutation with all Z checks requires $x\in C$, and commutation with all X checks requires $z\in C$. Any nonzero one of these words has weight at least three. Since the Pauli support is the union of their supports, every nonscalar Pauli commuting with all checks has weight at least three. The displayed logical triples attain this bound, proving $d=3$. Ignoring scalar phases here is essential: $-I$ does not perform a nontrivial logical operation.

The stabilizer itself has no nonidentity element below weight four. Its support-weight distribution is

$$1+21t^4+42t^6.$$

Exercise 2 derives this distribution. In contrast to the Shor code, distinct errors from the one-qubit Pauli basis have distinct actions and distinct syndromes.

Read a syndrome as two binary addresses

Measure the three Z checks first in the written syndrome, followed by the three X checks. A zero bit means outcome $+1$, and a one means $-1$. For a Pauli with components $(x,z)$,

$$\begin{aligned} s(x,z)&=(a,b),\\ a&=H_cx^{\mathsf T},\qquad b=H_cz^{\mathsf T}. \end{aligned}$$

Consequently,

Error	Z-check bits $a$	X-check bits $b$
$I$	$000$	$000$
$X_j$	$h_j$	$000$
$Z_j$	$000$	$h_j$
$Y_j$	$h_j$	$h_j$

This rule gives all 22 syndromes for the identity and 21 single-qubit Paulis. They are distinct because the columns are distinct and nonzero, and the zero-half patterns distinguish X, Z, and Y.

The separated Hamming decoder reads $a$ as the site needing X correction and $b$ as the site needing Z correction. Interpret $000$ as no correction. For example,

$$(a,b)=(101,110) \quad\Longrightarrow\quad R_s=X_5Z_6.$$

If $a=b$, the product acts as Y at that site up to an irrelevant phase. The rule specifies recovery on all 64 syndromes, although only 22 arise from the identity and single-qubit errors. Later error-rate calculations refer to this particular choice on the remaining syndromes.

Let $P$ project onto the code. The distinct single-error syndromes imply the Knill–Laflamme relation

$$PE_a^\dagger E_bP=\delta_{ab}P$$

for the 22 error operators. Their two-dimensional error spaces are mutually orthogonal, so correction is nondegenerate. The theorem also corrects their linear span, including coherent one-qubit rotations and arbitrary one-qubit channels coupled to an environment. It preserves entanglement with an untouched reference; it does not assume that physical noise first chooses a classical Pauli label.

The error spaces occupy $22\times2=44$ dimensions out of 128. Thus the quantum code is not perfect, even though the classical Hamming code used in its construction is perfect for one classical bit error. Nondegeneracy and perfect packing are different properties.

The syndrome-measurement discussion explains how to measure checks without reading logical amplitudes. The present decoding calculation assumes perfect reported syndromes.

Transversal Clifford gates

A transversal gate acts separately at each coordinate: no gate couples two qubits of the same code block. This limits how a single gate fault spreads inside a block. It is especially useful here because the check supports match. The following actions can be obtained directly from the codewords, or from the stabilizer conjugation rules developed by Gottesman (1997).

Hadamard exchanges the two check groups

Since $HXH=Z$ and $HZH=X$, applying H to all seven qubits exchanges each X check with its matching Z check and preserves the code space. It also exchanges $\overline X$ and $\overline Z$, so

$$H^{\otimes7}\big|_{\mathcal C}=H_L,$$

with the stated positive-amplitude logical basis. Here $\mathcal C$ denotes the quantum code space. Exercise 5 verifies the logical state transformation through a binary Fourier sum.

The phase gate runs in the opposite direction

Take $S=\operatorname{diag}(1,i)$. A basis word of weight $w$ receives phase $i^w$ under $S^{\otimes7}$. Every word in $0_L$ has weight zero or four, so its phase is one. Every word in $1_L$ has weight three or seven, so its phase is $-i$. Therefore

$$\begin{aligned} S^{\otimes7}\lvert0_L\rangle&=\lvert0_L\rangle,\\ S^{\otimes7}\lvert1_L\rangle&=-i\lvert1_L\rangle. \end{aligned}$$

Physical bitwise S implements logical $S^\dagger$ in this basis; physical bitwise $S^\dagger$ implements logical S. This sign also follows from the logical conjugation: defining $\overline Y=i\overline X\overline Z$ gives

$$Y^{\otimes7}=i^7\overline X\overline Z=-\overline Y.$$

An X check has weight four, so its corresponding phase is $i^4=1$: it becomes the product of the matching X and Z checks. Thus the stabilizer is preserved even though the logical phase direction is reversed.

CNOT acts coordinate by coordinate

Apply CNOT from each qubit of a control block to the matching qubit of a target block. Control X propagates to target X, and target Z propagates to control Z; the other two Pauli types stay in their blocks. Matching supports ensure that stabilizers transform to products of stabilizers. On logical operators,

$$\begin{aligned} \overline X_c&\mapsto\overline X_c\overline X_t,& \overline Z_c&\mapsto\overline Z_c,\\ \overline X_t&\mapsto\overline X_t,& \overline Z_t&\mapsto\overline Z_c\overline Z_t. \end{aligned}$$

These are exactly the logical CNOT rules. Equivalently, the underlying transformation $(u,v)\mapsto(u,u+v)$ maps logical cosets $(a,b)$ to $(a,a+b)$.

These gates generate the logical Clifford group, which is not computationally universal. Applying the non-Clifford gate $T=\operatorname{diag}(1,e^{i\pi/4})$ to every physical qubit does not even preserve this code space; Exercise 6 quantifies the leakage. More generally, Eastin and Knill (2009) rule out an entirely transversal universal set for a nontrivial finite-dimensional code that detects arbitrary errors on each subsystem. Fault-Tolerant Gates explains additional protected resources and complete gate constructions. Transversality of these ideal layers does not by itself establish fault tolerance of preparation, measurement, and repeated correction.

What happens when two qubits are affected?

Because $h_1+h_2=h_3$, the error $X_1X_2$ has the same syndrome as $X_3$. The decoder applies $X_3$ and leaves the logical operation $X_1X_2X_3\sim\overline X$. Similarly, two Z errors on sites 1 and 2 leave logical Z. Distance three guarantees correction of all single-qubit errors, not all pairs.

Nevertheless, the separated decoder corrects $X_jZ_k$ for any distinct sites $j,k$: the two syndrome addresses identify both components. There are $7\times6=42$ such weight-two Pauli strings. This explains why a statement that “every two-qubit error fails” would be too strong.

For independent depolarizing noise with probabilities $1-p,p/3,p/3,p/3$ for $I,X,Y,Z$, there are $\binom72 3^2=189$ weight-two strings. Their residual classes are

Residual class	Number	Leading probability
$I_L$	$42$	No logical error
$\overline X$	$63$	$7p^2$
$\overline Y$	$21$	$7p^2/3$
$\overline Z$	$63$	$7p^2$

Thus

$$p_L=\frac{49}{3}p^2+O(p^3).$$

Even this symmetric CSS code produces unequal X, Y, and Z error rates under the separated decoder. Independent decoding of the two syndrome halves uses less information than a joint inference procedure might use about correlated X and Z components of Y errors. The quoted coefficient belongs to this decoder and this noise model. Exercise 7 derives it without a long enumeration table; general choices of inference rule are discussed in Decoders.

Exercises

1. Find the two classical spaces

Compute $H_cH_c^{\mathsf T}$ and enumerate $D$. Establish the dimensions, word weights, and orthogonality of the two logical cosets.

Solution

All row self-overlaps are four and all distinct overlaps are two, so $H_cH_c^{\mathsf T}=0$ over $\mathbb F_2$. The three independent rows and their binary sums give

$$D=\{0000000,0001111, 0110011,0111100, 1010101,1011010, 1100110,1101001\}.$$

There are eight words, so $\dim D=3$ and $\dim C=4$. The nonzero D words all have weight four. Their complements have weight three, while the complement of zero has weight seven. Thus the two logical supports are disjoint and each contains eight basis states, proving normalization and orthogonality with amplitude $1/\sqrt8$.

2. Count stabilizers rather than only generators

Show that the stabilizer has 21 elements of weight four and 42 of weight six, besides the identity. Explain what this says about degeneracy for single-qubit Pauli errors.

Solution

The stabilizers are products $X(u)Z(v)$ with $u,v\in D$, with their resulting Pauli signs retained. Seven nonzero pure-X words and seven nonzero pure-Z words have weight four. When $u=v\ne0$, seven more products have that same support and are weight-four Y strings. For the remaining $7\times6=42$ pairs, distinct weight-four supports overlap twice, so their union has size six.

Hence the distribution is $1+21t^4+42t^6$. A product of two different one-qubit Paulis has weight at most two and cannot be a nonidentity stabilizer. Nor is it a nontrivial logical operator, since $d=3$. It therefore has nonzero syndrome, giving orthogonal error spaces and nondegenerate correction.

3. Decode four examples

Find the syndromes and residual logical actions for $X_5$, $Z_6$, $Y_2$, and $X_5Z_6$.

Solution

Their syndrome pairs are, respectively,

$$\begin{aligned} s(X_5)&=(101,000),\\ s(Z_6)&=(000,110),\\ s(Y_2)&=(010,010),\\ s(X_5Z_6)&=(101,110). \end{aligned}$$

The decoder selects $X_5$, $Z_6$, $X_2Z_2$, and $X_5Z_6$. Multiplication by the error gives $I,I,-iI,I$, respectively. Every result is identity on the logical density operator. The final example affects two sites but is still corrected because the separated syndrome halves identify both components.

4. Prove the full quantum distance

Explain why bounding only pure-X and pure-Z weights is insufficient without an argument about mixed Paulis. Supply that argument and exhibit a minimum-weight logical operator.

Solution

A general Pauli has binary components $(x,z)$, including both components at a Y site. Zero syndrome requires both $x,z\in C$. If its total support had weight below three, each component would also have weight below three; the classical distance then forces both to vanish. This excludes every nonscalar mixed Pauli of weight one or two.

The word $1110000$ lies in $C$ but not in $D$, so $X_1X_2X_3$ commutes with all checks and acts as logical X. Its weight three establishes the matching upper bound. Global Pauli phases are ignored in this distance statement.

5. Derive Hadamard and CNOT on the cosets

Use $H^{\otimes7}\lvert u\rangle=2^{-7/2}\sum_v(-1)^{u\cdot v}\lvert v\rangle$ to derive the logical Hadamard action. Then explain CNOT directly on pairs of logical cosets.

Solution

Summing $(-1)^{u\cdot v}$ over $u\in D$ gives eight when $v\in D^\perp=C$ and zero otherwise. The surviving amplitude is $1/4$ on all 16 words of C, yielding

$$H^{\otimes7}\lvert0_L\rangle =\frac{\lvert0_L\rangle+\lvert1_L\rangle}{\sqrt2}.$$

Starting from the complement coset introduces $(-1)^{\mathbf1\cdot v}$, which is $+1$ on D and $-1$ on $\mathbf1+D$. Thus the other input gives the minus combination.

For CNOT, write the two input strings as $a\mathbf1+u$ and $b\mathbf1+v$, with $u,v\in D$. The target becomes $(a+b)\mathbf1+(u+v)$. For fixed u, translation by u permutes D, so the uniform two-coset superposition maps to logical bits $(a,a+b)$ with unchanged positive amplitudes.

6. Distinguish bitwise S from bitwise T

Use word weights to find the logical action of $S^{\otimes7}$. For $T^{\otimes7}\lvert0_L\rangle$, find the probability of projecting back onto the code space. Does bitwise T implement an exact logical unitary?

Solution

Under S, weights zero and four receive phase one, while weights three and seven receive $-i$. Thus bitwise S is logical $S^\dagger$.

Under T, the weight-zero term of $0_L$ receives phase one and its seven weight-four terms receive $-1$. The overlap with $0_L$ is therefore

$$\langle0_L\vert T^{\otimes7}\vert0_L\rangle =\frac{1-7}{8}=-\frac34.$$

The overlap with $1_L$ is zero because their computational supports remain disjoint. The probability of returning to the code space is $9/16$, leaving $7/16$ outside it. Thus bitwise T does not preserve the code space and cannot be an exact logical gate, even though bitwise S is one.

7. Count errors on one pair of sites

For fixed distinct sites j and k, classify the nine Pauli pairs. Use the result to derive the weight-two residual counts and leading logical error probability.

Solution

Let $h_\ell=h_j+h_k$. Since the columns are distinct and nonzero, $\ell$ is different from j and k. The triple supported on $j,k,\ell$ is a weight-three word of C outside D. Hence an X triple is logical X, a Z triple is logical Z, and a Y triple is logical Y, up to phase.

Pairs $XZ$ and $ZX$ are corrected exactly. The pairs $XX,XY,YX$ leave logical X; $ZZ,ZY,YZ$ leave logical Z; and $YY$ leaves logical Y. Multiplying each count by the 21 possible site pairs gives $42,63,21,63$ in the order $I_L,X_L,Y_L,Z_L$.

The 147 failing strings each have probability $(p/3)^2(1-p)^5$. Higher weights contribute at order $p^3$, so

$$p_L=147\frac{p^2}{9}+O(p^3) =\frac{49}{3}p^2+O(p^3).$$

For an optional exact extension, classify all $4^7=16,384$ strings with the same decoder. Each logical class contains 4,096 strings. Thus uniform physical Paulis at $p=3/4$ give $p_L=3/4$, a useful check on the full calculation rather than on the small-$p$ approximation.

References

• 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.
• A. M. Steane, “Multiple-particle interference and quantum error correction,” Proceedings of the Royal Society A 452, 2551–2577, 1996, doi:10.1098/rspa.1996.0136, arXiv:quant-ph/9601029.