Shor Code

The Shor code encodes one logical qubit into nine physical qubits and exactly corrects every error in the linear span of the identity and all single-qubit Pauli operators. It was the first explicit quantum error-correcting code and remains the clearest example of how protection against bit- and phase-flip components can be combined without measuring an unknown logical state. In modern notation it is a degenerate CSS stabilizer code with parameters $[[9,1,3]]$.

Its construction is deliberately redundant. Three blocks of three qubits first expose the two classical repetition mechanisms: parity checks within each block locate a bit-flip component, while comparisons between block phases locate a phase-flip component. The stabilizer formulation then turns that picture into an exact quantum statement. Eight independent commuting checks define a two-dimensional code space, weight-three normalizer elements act as logical Paulis, and the Knill–Laflamme condition proves correction of arbitrary coherent one-qubit noise, including noise entangled with an external environment.

The code is degenerate in a concrete and useful sense. The three phase flips $Z_1,Z_2,Z_3$ within the first block have the same syndrome and the same action on every code state; similarly for the other two blocks. Consequently, the identity and twenty-seven weight-one Paulis occupy twenty-two, not twenty-eight, distinguishable error sectors. Recovery needs to identify an equivalence class that reverses the damage, not reconstruct a microscopic story about which indistinguishable phase flip occurred.

This page treats the ideal finite code exactly: its codewords, stabilizers, logical representatives, occupied syndrome ledger, recovery map, distance, degeneracy, and a fixed-decoder depolarizing calculation. It does not turn a bare check circuit into a fault-tolerant gadget, assign a hardware threshold, or count nine data qubits as the total implementation cost.

Required background. Stabilizer Formalism supplies stabilizer groups, code projectors, normalizers, logical cosets, distance, and syndrome algebra. Three-Qubit Codes supplies the targeted bit- and phase-repetition encodings, their ideal lookup recoveries, and the distinction between restricted repetition distance and full Pauli distance.

Helpful background. Why Quantum Error Correction Is Possible develops the encoding-isometry and operator-span viewpoints. Pauli Noise and Depolarizing Channels fixes the channel convention used in the final finite-block calculation.

The Nine-Qubit Logical Subspace

One declared block and tensor convention

Number the physical qubits from one through nine and divide them into three ordered blocks,

$$A=(1,2,3), \qquad B=(4,5,6), \qquad C=(7,8,9).$$

Tensor strings are read from qubit one on the left to qubit nine on the right. An omitted tensor factor is the identity. For example, $X_1X_2X_3$ means $XXXIIIIII$, and $Z_1Z_4Z_7$ means $ZIIZIIZII$. Operators act on kets from right to left, and global phases of state vectors or recovery Paulis have no operational effect. Relative signs inside a codeword are not global phases and must be retained.

Define the normalized three-qubit cat states

$$\lvert\mathrm{GHZ}_+\rangle = \frac{\lvert000\rangle+\lvert111\rangle}{\sqrt2}, \qquad \lvert\mathrm{GHZ}_-\rangle = \frac{\lvert000\rangle-\lvert111\rangle}{\sqrt2}.$$

They obey

$$X_1X_2X_3\lvert\mathrm{GHZ}_\pm\rangle = \pm\lvert\mathrm{GHZ}_\pm\rangle,$$

with the qubit labels shifted appropriately for blocks $B$ and $C$. A single $Z$ on any site of a block exchanges $\lvert\mathrm{GHZ}_+\rangle$ and $\lvert\mathrm{GHZ}_-\rangle$. A single $X$ takes the block out of the span of those two cat states, but the two adjacent $Z$-parity checks record which site changed. These two elementary facts underlie the entire nine-qubit construction.

Normalized codewords and logical amplitudes

Choose the logical computational basis

$$\begin{aligned} \lvert0_L\rangle &= \lvert\mathrm{GHZ}_+\rangle_A \lvert\mathrm{GHZ}_+\rangle_B \lvert\mathrm{GHZ}_+\rangle_C = \frac{1}{2\sqrt2} \left(\lvert000\rangle+\lvert111\rangle\right)^{\otimes3},\\ \lvert1_L\rangle &= \lvert\mathrm{GHZ}_-\rangle_A \lvert\mathrm{GHZ}_-\rangle_B \lvert\mathrm{GHZ}_-\rangle_C = \frac{1}{2\sqrt2} \left(\lvert000\rangle-\lvert111\rangle\right)^{\otimes3}. \end{aligned}$$

Each tensor product contains eight mutually orthogonal computational-basis terms with amplitudes of magnitude $1/(2\sqrt2)$. The states are normalized, and they are orthogonal because $\langle\mathrm{GHZ}_+\vert\mathrm{GHZ}_-\rangle=0$ in every block. The minus sign in $\lvert1_L\rangle$ occurs inside each of the three cat factors. Replacing it by one overall minus sign would merely change the global phase of $\lvert0_L\rangle$ and would not define the second logical basis state.

For example, expanding the first codeword in the declared tensor order gives

$$\begin{aligned} \lvert0_L\rangle =\frac{1}{2\sqrt2}(&\lvert000000000\rangle +\lvert000000111\rangle +\lvert000111000\rangle +\lvert000111111\rangle\\ &+\lvert111000000\rangle +\lvert111000111\rangle +\lvert111111000\rangle +\lvert111111111\rangle). \end{aligned}$$

The eight equal amplitudes make $1/\sqrt8=1/(2\sqrt2)$ and $8/(2\sqrt2)^2=1$ explicit. The corresponding expansion of $\lvert1_L\rangle$ carries a sign $(-1)^r$ when exactly $r$ of its three blocks equal $111$.

The encoding isometry is therefore

$$V = \lvert0_L\rangle\langle0\rvert + \lvert1_L\rangle\langle1\rvert, \qquad V^\dagger V=I_2.$$

Linearity preserves an unknown logical superposition:

$$\alpha\lvert0\rangle+\beta\lvert1\rangle \longmapsto \alpha\lvert0_L\rangle+\beta\lvert1_L\rangle.$$

No amplitude $\alpha$ or $\beta$ is measured or copied. The encoder moves the two-dimensional input into a particular entangled subspace of nine qubits. The redundancy lies in correlations that checks can interrogate without distinguishing the logical basis amplitudes.

Historical scope and name boundary

Shor’s 1995 construction described the code directly in terms of the three cat-state blocks and showed how an arbitrary interaction affecting one qubit could be reversed without destroying an existing superposition. The paper predates the now-standard stabilizer vocabulary. Gottesman’s later group-theoretic formulation makes the code’s checks, logical operators, degeneracy, and distance transparent, while Preskill and Nielsen and Chuang develop the code as a central bridge from repetition to general quantum error-correction conditions.

The historical achievement is an exact code-level theorem. It assumes that encoding, syndrome processing, and recovery can be implemented as specified. Shor already emphasized that imperfect restoration operations introduce new errors; the separate problem of making those operations fault tolerant is not solved merely by writing the codewords.

Four related names must stay separate. This page owns Shor’s nine-qubit code. Shor-style verified-cat-state extraction is a broader circuit family and does not follow merely from drawing the code’s checks. The Shor Algorithm is the canonical owner of factoring and period finding, not an error-correcting code. Bacon–Shor codes are subsystem constructions and must not be imported into this page.

Stabilizers and Logical Paulis

Eight independent CSS checks

The code is the simultaneous $+1$ eigenspace of six $Z$-type checks and two $X$-type checks. The following table also freezes the logical and projector conventions used throughout the page.

Field	Frozen value
Physical qubits	$n=9$
Logical qubits	$k=1$
Full distance	$d=3$
Block partition	$A=(1,2,3)$, $B=(4,5,6)$, $C=(7,8,9)$
Six $Z$-type checks	$Z_1Z_2$, $Z_2Z_3$, $Z_4Z_5$, $Z_5Z_6$, $Z_7Z_8$, $Z_8Z_9$
Two $X$-type checks	$X_1X_2X_3X_4X_5X_6$, $X_4X_5X_6X_7X_8X_9$
Code projector	$P=2^{-8}\prod_{a=1}^{8}(I+g_a)$
Logical basis	$\lvert0_L\rangle=\lvert\mathrm{GHZ}_+\rangle^{\otimes3}$, $\lvert1_L\rangle=\lvert\mathrm{GHZ}_-\rangle^{\otimes3}$
Convenient $\overline X$	$Z_1Z_4Z_7$
Convenient $\overline Z$	$X_1X_2X_3$
Correctable Pauli basis	$(I;X_1,\ldots,X_9;Y_1,\ldots,Y_9;Z_1,\ldots,Z_9)$
Structural status	Concatenated CSS stabilizer code; degenerate; not perfect

In the fixed generator order used below, the eight checks are

$$\begin{aligned} g_1&=Z_1Z_2, & g_2&=Z_2Z_3,\\ g_3&=Z_4Z_5, & g_4&=Z_5Z_6,\\ g_5&=Z_7Z_8, & g_6&=Z_8Z_9,\\ g_7&=X_1X_2X_3X_4X_5X_6,\\ g_8&=X_4X_5X_6X_7X_8X_9. \end{aligned}$$

The $Z$-type generators commute because they are diagonal. Each six-body $X$ check overlaps an included two-body $Z$ check on either zero or two sites. Two Pauli strings anticommute only when the number of local anticommutations is odd, so every $X$-type generator commutes with every $Z$-type generator. The two $X$ checks commute with one another as well.

Independence can be seen without multiplying all $256$ products. Within each block the two adjacent $Z$ checks are independent, giving six independent binary constraints. A product involving $g_7$ or $g_8$ has nonzero $X$ support, so it cannot equal a product of the first six generators. Their $X$-support rows, $111111000$ and $000111111$, are themselves independent. Thus the stabilizer has eight independent generators and contains neither $-I$ nor a hidden relation among the displayed checks.

Each codeword has eigenvalue $+1$ under all eight generators. The inner $Z$ checks stabilize both $\lvert000\rangle$ and $\lvert111\rangle$ in their block. For $g_7$, the $XXX$ eigenvalues of blocks $A$ and $B$ multiply to $+1$ both for $\mathrm{GHZ}_+\mathrm{GHZ}_+$ and for $\mathrm{GHZ}_-\mathrm{GHZ}_-$. The same argument applies to $g_8$ and blocks $B,C$.

Projector and code dimension

Because every $g_a$ is a commuting Hermitian involution, its $+1$ projector is $(I+g_a)/2$. Their product is the code projector

$$P := \frac{1}{2^8}\prod_{a=1}^{8}(I+g_a), \qquad P^2=P.$$

It is Hermitian and idempotent. Expanding the product gives one term for each stabilizer element. Every nonidentity Pauli has zero trace, so only the identity contributes to $\operatorname{Tr}P$:

$$\operatorname{Tr}P = \frac{2^9}{2^8} =2.$$

The simultaneous eigenspace therefore encodes exactly one logical qubit. The two orthonormal codewords already lie in it, so they form a complete basis for $\operatorname{im}P$. Equivalently,

$$P = \lvert0_L\rangle\langle0_L\rvert + \lvert1_L\rangle\langle1_L\rvert.$$

The dimension argument matters because satisfying a collection of checks is not by itself enough to establish which code has been defined. Generator signs, commutation, independence, and the resulting rank must all agree. A minus sign on one generator would select a different syndrome sector, while an unnoticed relation would change the encoded dimension.

Logical Pauli representatives and equivalences

The physical operator $X_1X_2X_3$ reads the cat-state sign in block $A$:

$$\overline Z\lvert0_L\rangle=\lvert0_L\rangle, \qquad \overline Z\lvert1_L\rangle=-\lvert1_L\rangle.$$

It is therefore logical $Z$, despite being composed of physical $X$ operators. Multiplication by the outer stabilizers gives equivalent representatives,

$$X_1X_2X_3 \sim X_4X_5X_6 \sim X_7X_8X_9.$$

Here $A\sim B$ means $A^\dagger B\in S$, so the two operators act identically on the code space.

A physical $Z$ on one site exchanges $\mathrm{GHZ}_+$ and $\mathrm{GHZ}_-$ in its block. Applying one $Z$ in each block therefore exchanges the logical basis states:

$$\overline X\lvert0_L\rangle=\lvert1_L\rangle, \qquad \overline X\lvert1_L\rangle=\lvert0_L\rangle.$$

Within a block, any two choices differ by a weight-two $Z$ stabilizer. Hence all $27$ strings $Z_iZ_jZ_k$ with $i\in A$, $j\in B$, and $k\in C$ represent logical $X$. The declared $Z_1Z_4Z_7$ is only a convenient member of that coset.

The representatives commute with every stabilizer but anticommute with one another because their supports meet at qubit one with physical factors $Z$ and $X$. They are in the normalizer $N(S)$ but not in $S$. Their physical letters must not be used to rename their logical actions: with the codeword convention fixed above, $Z_1Z_4Z_7$ is $\overline X$ and $X_1X_2X_3$ is $\overline Z$. The third logical Pauli is fixed by

$$\overline Y=i\overline X\overline Z.$$

Nested Bit- and Phase-Repetition Structure

Outer phase and inner bit encoders

Let $A,B,C$ first denote three outer qubits. The phase-repetition encoder is

$$\lvert0\rangle \longmapsto \lvert+\rangle_A\lvert+\rangle_B\lvert+\rangle_C, \qquad \lvert1\rangle \longmapsto \lvert-\rangle_A\lvert-\rangle_B\lvert-\rangle_C.$$

Its checks are $X_AX_B$ and $X_BX_C$. Each outer qubit is then encoded by a bit-repetition encoder,

$$\lvert0\rangle_D\longmapsto\lvert000\rangle_D, \qquad \lvert1\rangle_D\longmapsto\lvert111\rangle_D, \qquad D\in\{A,B,C\}.$$

By linearity, an outer $\lvert+\rangle$ becomes $\lvert\mathrm{GHZ}_+\rangle$ and an outer $\lvert-\rangle$ becomes $\lvert\mathrm{GHZ}_-\rangle$. The nested encoder thus reproduces the two Shor codewords exactly.

For the inner bit code, logical $X_D$ may be represented by the product of three physical $X$ operators in block $D$, while logical $Z_D$ may be represented by any one physical $Z$ in that block. Substituting these representatives into the outer checks gives

$$X_AX_B\longmapsto X_1X_2X_3X_4X_5X_6,$$

and

$$X_BX_C\longmapsto X_4X_5X_6X_7X_8X_9.$$

The inner encoders contribute their six adjacent $Z$ checks. This substitution derives the complete stabilizer rather than guessing it from the final codewords.

Stabilizer-support schematic for the Shor $[[9,1,3]]$ code. The six within-block $Z$ checks locate bit-flip components, while the two overlapping six-qubit $X$ checks locate phase-flip components by block. This support diagram is not a syndrome-extraction circuit and does not by itself establish fault tolerance.

CSS substitution and the targeted-distance caveat

The stabilizer is CSS because every displayed generator is purely $X$ type or purely $Z$ type. In binary form, the $Z$-check and $X$-check support matrices may be written

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

and

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

Their rows have even overlaps, equivalently $H_XH_Z^{\mathsf T}=0$ over $\mathbb F_2$. Calderbank and Shor and, independently, Steane developed the classical-code structures now called CSS codes. The Shor code can be understood retrospectively in that language even though Shor’s original presentation preceded the standard terminology. The general CSS construction and Steane’s seven-qubit code require their own canonical treatments; this page uses only the finite matrices needed here.

The phrase “concatenated repetition” must be interpreted with care. The three-qubit bit-repetition code corrects a declared span of single $X$ errors, and its Hadamard-conjugate phase code corrects a declared span of single $Z$ errors. Each has full-Pauli parameters $[[3,1,1]]$, because a complementary weight-one Pauli is already logical. It is therefore incorrect to call the nine-qubit construction a concatenation of two full $[[3,1,3]]$ quantum codes or to infer its distance by multiplying two nonexistent full-Pauli distances.

What the nested picture does establish is an error-component workflow. The inner checks diagnose the $X$ component of a Pauli, while the outer checks diagnose the block parity of its $Z$ component. Since $Y=iXZ$, a single $Y$ activates both records. The full stabilizer and normalizer analysis below is what upgrades that intuition to the exact $[[9,1,3]]$ claim.

Twenty-Two Single-Error Syndromes and Ideal Recovery

Ordered eight-bit syndrome convention

For a phase-free Pauli $E$, define the syndrome bit of generator $g_a$ by

$$Eg_a=(-1)^{s_a(E)}g_aE, \qquad s_a(E)\in\{0,1\}.$$

Thus $s_a=0$ corresponds to a $+1$ check outcome on $E\lvert\psi_L\rangle$, and $s_a=1$ corresponds to a $-1$ outcome. Store the bits in the fixed order

$$s(E)=(s_1s_2s_3s_4s_5s_6\,s_7s_8).$$

The first six bits are the three within-block pairs; the last two compare block phases. Syndrome addition is binary:

$$s(EF)=s(E)\oplus s(F).$$

This is why the syndrome of $Y_j$, up to its irrelevant scalar phase, is the XOR of the syndromes of $X_j$ and $Z_j$.

For each block, the adjacent inner pair has location patterns

$$10\longleftrightarrow\text{first site}, \qquad 11\longleftrightarrow\text{second site}, \qquad 01\longleftrightarrow\text{third site}.$$

The outer pair uses the same three patterns for blocks $A,B,C$, respectively. This repeated $10,11,01$ convention makes the ledger readable, but the six inner positions and two outer positions must never be interchanged.

Complete one-error syndrome ledger

The following table lists every syndrome occupied by the identity or a weight-one Pauli. A grouped $Z$ row denotes three physically distinct errors with identical code-space action.

Error class	Members	Syndrome	Chosen phase-free correction
$I$	$I$	00000000	$I$
$X_1$	$X_1$	10000000	$X_1$
$X_2$	$X_2$	11000000	$X_2$
$X_3$	$X_3$	01000000	$X_3$
$X_4$	$X_4$	00100000	$X_4$
$X_5$	$X_5$	00110000	$X_5$
$X_6$	$X_6$	00010000	$X_6$
$X_7$	$X_7$	00001000	$X_7$
$X_8$	$X_8$	00001100	$X_8$
$X_9$	$X_9$	00000100	$X_9$
$Z_A$	$Z_1,Z_2,Z_3$	00000010	$Z_1$
$Z_B$	$Z_4,Z_5,Z_6$	00000011	$Z_4$
$Z_C$	$Z_7,Z_8,Z_9$	00000001	$Z_7$
$Y_1$	$Y_1$	10000010	$X_1Z_1$
$Y_2$	$Y_2$	11000010	$X_2Z_1$
$Y_3$	$Y_3$	01000010	$X_3Z_1$
$Y_4$	$Y_4$	00100011	$X_4Z_4$
$Y_5$	$Y_5$	00110011	$X_5Z_4$
$Y_6$	$Y_6$	00010011	$X_6Z_4$
$Y_7$	$Y_7$	00001001	$X_7Z_7$
$Y_8$	$Y_8$	00001101	$X_8Z_7$
$Y_9$	$Y_9$	00000101	$X_9Z_7$

There are exactly twenty-two occupied classes:

$$1\text{ identity} +9\text{ X classes} +3\text{ Z classes} +9\text{ Y classes} =22.$$

The other $234$ of the $256$ possible eight-bit strings are not produced by the promised set of identity and weight-one Pauli errors. They can be produced by higher-weight errors. A real decoder may still assign corrections to them, but those assignments are outside the exact one-error guarantee.

Each syndrome projector has the form

$$P_s = \prod_{a=1}^{8} \frac{I+(-1)^{s_a}g_a}{2}$$

and has rank two. Under correctable errors, only twenty-two such sectors are reached, for a total reached dimension of $44$ inside the $512$-dimensional physical Hilbert space. The unused sectors are another reminder that the Shor code is not a perfect packing code.

Separated recovery and Pauli frames

An ideal lookup recovery may be specified by one representative correction $C_s$ for each occupied syndrome. For a nonzero inner pair, apply $X$ at the indicated physical site. For a nonzero outer pair, apply $Z$ at a fixed site of the indicated block, for example site one of that block. When both records are nonzero, combine those two corrections. The order changes at most a global Pauli phase and therefore not the recovered density operator.

For example, $Z_2$ has outer pattern $10$. Choosing $C_s=Z_1$ gives

$$C_sZ_2=Z_1Z_2=g_1,$$

which acts trivially on the code. For $Y_5=iX_5Z_5$, the syndrome is 00110011. A separated choice $C_s=Z_4X_5$ gives, up to a scalar phase,

$$C_sY_5\sim Z_4Z_5=g_3.$$

Applying $Y_5$ itself would also recover that particular error. The separated choice emphasizes that the phase record identifies only a block, not a site.

The ideal channel can be written

$$\mathcal R(\rho) = \sum_s C_sP_s\rho P_sC_s^\dagger + \mathcal R_\perp(\rho),$$

where the displayed sum covers the occupied correctable sectors and $\mathcal R_\perp$ completes the map on their orthogonal complement. Its action on that complement does not affect the exact promised-input theorem.

A device need not physically apply every Pauli correction. It may update a Pauli frame and reinterpret later operations or readout. That operational choice does not change which error class the syndrome identifies. Physical check circuits, repeated noisy outcomes, detector records, and measurement sign conventions belong to Syndrome Measurement, not to this ideal ledger.

Exact Correction of Arbitrary One-Qubit Noise

The degenerate Knill–Laflamme matrix

Consider the ordered phase-free error basis

$$\mathcal E_1= \left( I; X_1,\ldots,X_9; Y_1,\ldots,Y_9; Z_1,\ldots,Z_9 \right).$$

Knill and Laflamme’s necessary and sufficient condition for exact recovery is

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

for a Hermitian matrix $C$ independent of the encoded state. For the declared Shor convention, direct Pauli algebra gives

$$C = I_{19} \oplus J_3 \oplus J_3 \oplus J_3,$$

where $J_3$ is the all-ones matrix. The $I_{19}$ block belongs to $I$, the nine $X$ errors, and the nine $Y$ errors. Each $J_3$ block belongs to the three $Z$ errors within one physical block.

The off-diagonal entry for $Z_1,Z_2$, for example, is nonzero because

$$PZ_1^\dagger Z_2P = PZ_1Z_2P =P.$$

By contrast, if $E_a^\dagger E_b$ anticommutes with any stabilizer generator, then

$$PE_a^\dagger E_bP=0.$$

The matrix has eigenvalues $1$ with multiplicity nineteen, $3$ with multiplicity three, and $0$ with multiplicity six. Hence

$$\operatorname{rank}C=22.$$

This rank equals the number of occupied syndrome classes. Combinations such as $Z_1-Z_2$ annihilate every codeword and correspond to zero modes of $C$. A recovery does not need, and cannot obtain, information that distinguishes such equivalent actions. Replacing $C$ by a Kronecker delta would falsely declare the Shor code nondegenerate.

Coherent one-qubit noise

Every operator acting on a fixed physical qubit $j$ has a Pauli expansion

$$A_j = a_I I+a_X X_j+a_Y Y_j+a_Z Z_j.$$

More generally, every Kraus operator of a channel supported on that qubit has this form. The Knill–Laflamme condition is stable under linear combinations: if

$$A_\mu=\sum_a\alpha_{\mu a}E_a,$$

then

$$PA_\mu^\dagger A_\nu P = \left( \sum_{a,b}\alpha_{\mu a}^*C_{ab}\alpha_{\nu b} \right)P.$$

Thus correcting the finite Pauli basis corrects the complete operator span. The theorem covers a small coherent rotation such as

$$U_j = \exp\!\left[-\frac{i\theta}{2} (n_xX_j+n_yY_j+n_zZ_j)\right]$$

for arbitrary angle and axis, not only a classical mixture in which one Pauli is secretly chosen. Nielsen and Chuang use this discretization of continuous errors to explain why a finite syndrome record can reverse a continuum of one-qubit disturbances.

If the syndrome is measured, coherent components associated with distinct syndrome sectors become different recorded branches. Equivalent components, such as the three $Z$ errors in one block, need not be separated because they already have the same action on the code. Alternatively, the entire recovery can be implemented coherently with an ancilla and no readout. Measurement is a convenient realization, not the mathematical reason the operator span is correctable.

The phrase “arbitrary one-qubit noise” specifies support, not a distribution. It allows the affected site to be unknown and even permits coherent linear combinations across the listed correctable operators. It does not include a generic correlated operator with simultaneous support on two or more physical qubits.

Reference-entangled one-qubit noise

Let $R$ be an external reference and let $L$ denote the encoded logical subsystem. Exact quantum error correction must preserve correlations with $R$, not merely recover isolated pure codewords. A one-qubit system–environment isometry can be expanded as

$$U_{QE} \lvert\psi_L\rangle\lvert0\rangle_E = \sum_a E_a\lvert\psi_L\rangle\lvert e_a\rangle_E,$$

where the environment vectors need not be normalized or orthogonal. The Knill–Laflamme matrix being independent of $\lvert\psi_L\rangle$ means that the environment obtains no information that distinguishes logical states.

For every density operator $\rho_{RL}$ supported on the logical code space, there is a recovery such that

$$(\operatorname{id}_R\otimes\mathcal R) (\operatorname{id}_R\otimes\mathcal N) (\rho_{RL}) = \rho_{RL}$$

on the restored logical output, with syndrome or recovery ancillas discarded as specified. In a dilation, the auxiliary output may remain correlated with the environment, but its state is independent of the logical amplitudes. The recovery transfers error entropy away from the logical subsystem rather than undoing the inaccessible environment’s microscopic evolution.

Knill and Laflamme explicitly connect their conditions to preservation of a maximally entangled state, which is why reference-system fidelity is the right exact test. Shor’s original system–environment argument already contains this essential insight: corresponding environment states must be the same for the two logical basis components. Testing only $\lvert0_L\rangle$ and $\lvert1_L\rangle$ as classical alternatives would miss the coherence requirement.

Distance Three, Degeneracy, and Errors Outside the Promise

No logical operator below weight three

Write a phase-free Pauli as a binary symplectic vector $(x\mid z)$ in $\mathbb F_2^{18}$. Commutation with $Z_1Z_2$ and $Z_2Z_3$ requires

$$x_1=x_2=x_3.$$

The other inner checks similarly require

$$x_4=x_5=x_6, \qquad x_7=x_8=x_9.$$

If a normalizer element has physical weight at most two, none of these three-bit $x$ blocks can be nonzero. It must therefore contain only $I$ and $Z$ factors.

Let $a,b,c$ be the parity of its $Z$ support in blocks $A,B,C$. Commutation with $g_7$ and $g_8$ gives

$$a+b=0, \qquad b+c=0 \pmod2,$$

so $a=b=c$. Weight at most two excludes the odd possibility $a=b=c=1$. Every block must have even $Z$ parity. A nonidentity operator of weight at most two is consequently a pair of $Z$ operators in one block, and every such pair lies in the stabilizer generated by that block’s adjacent checks.

Therefore there is no member of $N(S)\setminus S$ below weight three. The declared $\overline X=Z_1Z_4Z_7$ and $\overline Z=X_1X_2X_3$ are weight-three members of $N(S)\setminus S$, proving both inequalities

$$d\ge3, \qquad d\le3, \qquad \boxed{d=3}.$$

Distance three implies exact correction of all weight-one errors because a product $E_a^\dagger E_b$ has weight at most two and is either a stabilizer on the code or anticommutes with a check. It also means every weight-two Pauli satisfies the error-detection condition $PEP=c_EP$. When $E$ is a weight-two stabilizer, $c_E=1$: it has zero syndrome because it is harmless, not because the distance proof failed.

Weight-two stabilizers and code degeneracy

Each block contributes three weight-two stabilizers,

$$Z_1Z_2, \quad Z_2Z_3, \quad Z_1Z_3,$$

with shifted labels for blocks $B$ and $C$. Hence the stabilizer contains nine weight-two elements. Exhaustive multiplication of its $256$ elements gives the weight enumerator

$$A_S(z) = 1+9z^2+27z^4+75z^6+144z^8.$$

The coefficients sum to $256$, as required for an eight-generator stabilizer. The weight-two coefficient supplies a finite algebraic diagnostic of degeneracy. For example,

$$Z_1\lvert\psi_L\rangle = Z_2\lvert\psi_L\rangle = Z_3\lvert\psi_L\rangle$$

for every code state, because each pairwise product is in $S$.

Preskill uses precisely these within-block phase errors to distinguish the general Knill–Laflamme matrix from the stronger nondegenerate condition. The same fact should not be described as a decoder defect. Microscopic indistinguishability is acceptable when the alternatives require the same logical recovery.

The code does not saturate the nondegenerate one-error quantum Hamming count:

$$2^1\left[1+3\binom91\right] =56 <512=2^9.$$

It is therefore not a perfect code. The quantum Singleton inequality is also loose here, since $n-k=8>2(d-1)=4$. The nine-qubit code is historically and pedagogically important, not length minimal; the Five-Qubit Code owns the distinct perfect-packing and minimum-length results.

Two explicit higher-weight aliases

A distance-three code promises correction through weight one, not through weight two. The ideal lookup can misidentify a higher-weight syndrome as a correctable one. For example,

$$s(X_1X_2) = s(X_1)\oplus s(X_2) = 10000000\oplus11000000 = 01000000 = s(X_3).$$

The one-error lookup applies $X_3$, leaving

$$X_3X_1X_2 = X_1X_2X_3 = \overline Z.$$

The state returns to the code space with a logical phase error. The syndrome did not contain enough information to distinguish one flip at site three from two flips at sites one and two.

A complementary example uses phase components in two blocks:

$$s(Z_1Z_4) = 00000010\oplus00000011 = 00000001 = s(Z_7).$$

Choosing $Z_7$ as the block-$C$ correction leaves

$$Z_7Z_1Z_4 = Z_1Z_4Z_7 = \overline X.$$

Some weight-two errors are nevertheless harmless stabilizers, and some may be corrected accidentally by a particular decoder. Distance specifies the uniform guarantee; it does not say that every error just outside the promise must fail.

Independent depolarizing fixture

To audit a decoder beyond its exact promise, fix the separated recovery for all $256$ syndromes: correct each block’s inner repetition pattern and then correct the outer block-phase repetition pattern. Let every physical qubit undergo the independent depolarizing channel

$$\Pr(I)=1-p, \qquad \Pr(X)=\Pr(Y)=\Pr(Z)=\frac p3.$$

Exhaustive classification of all $4^9=262144$ phase-free Pauli strings by physical weight and residual logical class gives the following finite ledger. The Total column is the required check $\binom9w3^w$.

Physical Pauli weight	Total	$I_L$	$X_L$	$Y_L$	$Z_L$
0	1	1	0	0	0
1	27	27	0	0	0
2	324	180	108	0	36
3	2268	804	756	216	492
4	10206	2502	2628	2520	2556
5	30618	6858	6876	8928	7956
6	61236	14580	15252	15792	15612
7	78732	20916	20556	18072	19188
8	59049	15633	14652	14328	14436
9	19683	4035	4708	5680	5260

Each row sums to $\binom9w3^w$, and all rows sum to $4^9=262144$.

Summing the three nonidentity logical columns with probability $(p/3)^w(1-p)^{9-w}$ gives

$$\begin{aligned} p_L={}& 16p^2 -\frac{520}{9}p^3 +\frac{952}{9}p^4 -\frac{1120}{9}p^5\\ &+\frac{896}{9}p^6 -\frac{12800}{243}p^7 +\frac{4096}{243}p^8 -\frac{16384}{6561}p^9. \end{aligned}$$

The leading coefficient has a direct count. At weight two, $36$ strings have two $X$ or $Y$ components within one block and leave $\overline Z$; another $108$ have $Z$ or $Y$ components in two different blocks and leave $\overline X$. Therefore

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

Useful global checks are $p_L(0)=0$ and $p_L(3/4)=3/4$. At $p=3/4$ every nine-qubit Pauli string is equally likely, and each residual logical coset has $4^9/4$ elements. This calculation is an exact ideal-block result for this recovery and this independent channel. It is not a code-capacity threshold, circuit-level forecast, decoder optimum, device prediction, or result for correlated or leakage noise.

Extraction, resources, and historical scope

The parameter $n=9$ counts data qubits in one code block. It omits state preparation, ancillas, verified cat states, entangling gates, check repetition, measurement, reset, routing, connectivity, classical inference, latency, discarded trials, logical operations, and spare resources. Even an ideal measurement of the six-body checks is a physical operation whose implementation must be specified.

A bare circuit that couples one ancilla sequentially to six data qubits can spread one ancilla fault to several data sites. DiVincenzo and Shor’s fault-tolerant error-correction analysis made dangerous ancilla-fault fanout explicit and developed systematic protected procedures. A high-weight stabilizer equation therefore licenses an ideal observable, not a claim that the most obvious circuit measuring it is fault tolerant.

Shor’s original memory calculation showed quadratic suppression under a small, independent-error idealization and warned that imperfect restoration operations compete with storage noise. The exact polynomial above is a modern, fully enumerated version for a specifically declared Pauli channel and hard decoder, not a replacement for a noisy syndrome-extraction study. Fault-Tolerant Gates owns bounded fault propagation and protected logical gadgets. Error Correction Case Studies owns dated experimental records and evidence dispositions.

Canonical Owners and Boundaries

What this page owns and where to continue

This page is the canonical home of the nine-qubit Shor code in the declared convention: the cat-product logical basis, eight stabilizer generators, projector and encoded dimension, logical Pauli representatives, concatenated repetition interpretation, twenty-two occupied one-error syndrome classes, ideal recovery, degenerate Knill–Laflamme matrix, full-Pauli distance proof, weight enumerator, two explicit aliases, and fixed-decoder depolarizing fixture.

The surrounding owners separate those finite results from broader claims:

• The Quantum Error Correction and Fault Tolerance guide routes among code algebra, extraction, inference, gadgets, thresholds, resources, and evidence classes.
• Why Quantum Error Correction Is Possible owns the general encoding-isometry, information-leakage, operator-span, and Knill–Laflamme explanations.
• Stabilizer Formalism owns general Pauli symplectic algebra, normalizers, logical cosets, projectors, Clifford updates, and tableaus.
• Three-Qubit Codes owns the individual targeted repetition codes and why their restricted distance is not full Pauli distance.
• The Five-Qubit Code owns the nondegenerate cyclic perfect code, complete sixteen-sector lookup, Hamming saturation, and minimum-length proof.
• Syndrome Measurement owns signed physical check instruments, ordered fault propagation, repeated outcomes, and detector records.
• Decoders owns probabilistic inference among equivalence classes when the noise model and syndrome history go beyond this promised lookup.
• Fault-Tolerant Gates owns gadget correctness, controlled fault spread, protected logical operations, and code-switching boundaries.
• Pauli Noise and Depolarizing Channels owns channel parametrizations, Pauli transfer descriptions, composition, twirling boundaries, and noise-model qualifications.
• Error Correction Case Studies owns dated experimental records, matched demonstrations, and evidence dispositions.

Steane Code owns the seven-qubit Hamming-derived, weakly self-dual, nondegenerate CSS construction and its code-specific transversal Clifford action. CSS Codes owns the general matrix, nesting, logical-quotient, and distance construction; this page retains its exact concatenated, degenerate nine-qubit code, syndrome ledger, recovery, distance proof, and depolarizing polynomial. Likewise, an encoding demonstration, a syndrome experiment, and repeated logical-memory operation are different evidence classes. None follows merely from the existence of the ideal $[[9,1,3]]$ code.

Exercises

1. Codeword and logical-action audit

Using the declared block order, prove that $\lvert0_L\rangle$ and $\lvert1_L\rangle$ are normalized and orthogonal. Verify that all eight generators stabilize both codewords. Then compute the action of $X_1X_2X_3$ and $Z_1Z_4Z_7$ on the logical basis and identify their logical Pauli names.

Solution

Each cat factor is normalized, so each three-factor product is normalized. Their overlap factorizes as

$$\langle0_L\vert1_L\rangle = \langle\mathrm{GHZ}_+\vert\mathrm{GHZ}_-\rangle^3 =0.$$

Within each block, $Z_1Z_2$ and $Z_2Z_3$ give eigenvalue $+1$ on both $\lvert000\rangle$ and $\lvert111\rangle$; the shifted checks work identically. The $XXX$ eigenvalue of $\mathrm{GHZ}_+$ is $+1$, while that of $\mathrm{GHZ}_-$ is $-1$. Each outer check multiplies two block eigenvalues, giving $+1$ on both logical codewords.

On the logical basis,

$$X_1X_2X_3\lvert0_L\rangle=\lvert0_L\rangle, \qquad X_1X_2X_3\lvert1_L\rangle=-\lvert1_L\rangle,$$

so this physical triple is $\overline Z$. A $Z$ in one block exchanges $\mathrm{GHZ}_+$ and $\mathrm{GHZ}_-$. Therefore one $Z$ in every block exchanges all three signs,

$$Z_1Z_4Z_7\lvert0_L\rangle=\lvert1_L\rangle, \qquad Z_1Z_4Z_7\lvert1_L\rangle=\lvert0_L\rangle,$$

and is $\overline X$. Their one-site anticommuting overlap confirms the logical Pauli algebra.

2. Construct the concatenated stabilizer

Start from the outer phase-repetition code with codewords $\lvert+++\rangle,\lvert---\rangle$ and encode each outer qubit with the three-qubit bit-repetition code. Derive the eight physical stabilizer generators and the declared logical $X$ and $Z$. Explain why this construction does not justify multiplying two full-Pauli distances of three.

Solution

The outer phase code has checks $X_AX_B$ and $X_BX_C$. Each inner bit code has two checks $Z_{D,1}Z_{D,2}$ and $Z_{D,2}Z_{D,3}$. These give the six adjacent $Z$ generators after assigning physical labels to blocks $A,B,C$.

For an inner bit code, logical $X_D$ is the three-body product of physical $X$ operators. Substituting into the outer checks gives

$$X_AX_B\mapsto X_1X_2X_3X_4X_5X_6,$$

and

$$X_BX_C\mapsto X_4X_5X_6X_7X_8X_9.$$

Outer logical $Z$ may be represented by $X_A$, which becomes $X_1X_2X_3=\overline Z$. Outer logical $X$ is $Z_AZ_BZ_C$. An inner logical $Z_D$ may be any one physical $Z$ in block $D$, giving $Z_1Z_4Z_7=\overline X$ as one choice.

The component repetition codes correct only a declared Pauli axis. In the full Pauli group each is $[[3,1,1]]$, not $[[3,1,3]]$. The nested encoder explains the checks and component workflow, but the separate normalizer proof is required to establish full distance three for the nine-qubit code.

3. Reconstruct the syndrome ledger

Derive the inner location patterns $10,11,01$ and the outer block patterns $10,11,01$. Use them to compute the full syndromes of $Z_2$, $X_8$, and $Y_5$. Give one valid recovery for each and identify any stabilizer left after recovery.

Solution

In one block, an $X$ or $Y$ at the first site anticommutes only with the first adjacent $Z$ check, giving $10$. At the second site it anticommutes with both, giving $11$; at the third it anticommutes only with the second, giving $01$. A $Z$ or $Y$ in block $A$ anticommutes with $g_7$ only, in block $B$ with both outer checks, and in block $C$ with $g_8$ only.

Therefore

$$s(Z_2)=00000010, \qquad s(X_8)=00001100,$$

and

$$s(Y_5) =s(X_5)\oplus s(Z_5) =00110000\oplus00000011 =00110011.$$

For $Z_2$, choose correction $Z_1$; the residual is $Z_1Z_2=g_1$. For $X_8$, choose $X_8$ and the residual is the identity. For $Y_5$, applying $Y_5$ directly gives the identity. A separated decoder may instead apply $Z_4X_5$, leaving $Z_4Z_5=g_3$ up to a scalar phase. Both recoveries act identically on the code space.

4. Build the degenerate Knill–Laflamme matrix

For the ordered basis

$$(I;X_1,\ldots,X_9;Y_1,\ldots,Y_9;Z_1,\ldots,Z_9),$$

determine every nonzero block of $C_{ab}$ in $PE_a^\dagger E_bP=C_{ab}P$. Find the rank and eigenvalues, and explain why a diagonal identity matrix would be wrong.

Solution

Every diagonal entry is one because each phase-free Pauli is unitary. Products between distinct $X$ or $Y$ representatives, or between those errors and any other class, anticommute with at least one generator and therefore project to zero. The exception is a pair of $Z$ errors in the same block. Their product is one of the nine weight-two $Z$ stabilizers, so the projected product is $P$.

Consequently

$$C=I_{19}\oplus J_3\oplus J_3\oplus J_3.$$

Each all-ones block has eigenvalues $3,0,0$. Thus the full spectrum contains nineteen eigenvalues equal to one, three equal to three, and six equal to zero, giving rank twenty-two.

The zero modes include combinations such as $Z_1-Z_2$, which annihilate the code space. A diagonal identity would assign orthogonal sectors to $Z_1$ and $Z_2$, even though $Z_1\lvert\psi_L\rangle=Z_2\lvert\psi_L\rangle$ for every code state. The general Knill–Laflamme condition allows this degeneracy; it requires logical-state independence, not microscopic error distinguishability.

5. Prove distance three

Use binary symplectic variables to prove that every normalizer element of weight at most two is a stabilizer. Then exhibit a weight-three nontrivial logical operator. State separately what this proves about error detection and one-error correction.

Solution

Commutation with the two inner $Z$ checks in each block forces the three $x$ components in that block to be equal. Weight at most two therefore forces all $x$ components to vanish. The candidate normalizer element contains only $Z$ factors.

Let $a,b,c$ be the $Z$-support parity in the three blocks. Commutation with the two outer $X$ checks gives $a+b=0$ and $b+c=0$, hence $a=b=c$. At weight at most two they cannot all be odd, so each is even. The only nonidentity possibility is two $Z$ factors in one block, which is a stabilizer.

Thus $N(S)\setminus S$ has no element of weight one or two. The operator $Z_1Z_4Z_7=\overline X$ is a weight-three member, as is $X_1X_2X_3=\overline Z$, so $d=3$.

Every Pauli of weight below three satisfies $PEP=c_EP$, which is the detection condition; a weight-two stabilizer has $c_E=1$ and is harmless. For two weight-one errors $E_a,E_b$, the product $E_a^\dagger E_b$ has weight at most two, establishing the Knill–Laflamme condition and exact correction through one arbitrary physical-qubit error.

6. Recover coherent and reference-entangled noise

Let one physical qubit undergo an arbitrary system–environment isometry. Expand it in the Pauli basis and explain why the same recovery works without knowing the coefficients or environment vectors. Then state the required result when the encoded qubit is entangled with a reference.

Solution

For an affected site $j$, write

$$U_{QE}\lvert\psi_L\rangle\lvert0\rangle_E = I\lvert\psi_L\rangle\lvert e_I\rangle +X_j\lvert\psi_L\rangle\lvert e_X\rangle +Y_j\lvert\psi_L\rangle\lvert e_Y\rangle +Z_j\lvert\psi_L\rangle\lvert e_Z\rangle.$$

The environment vectors may overlap and need not be normalized. Exact correctability of the Pauli span means a recovery can coherently map each occupied error sector back to the code while transferring the sector label to an ancilla. Degenerate components need not be separated because their actions already agree on the code. No coefficient or environment state enters the recovery lookup.

If $R$ is an untouched reference, linearity and the logical-state-independent Knill–Laflamme matrix imply

$$(\operatorname{id}_R\otimes\mathcal R\mathcal N)(\rho_{RL}) = \rho_{RL}$$

on the restored logical subsystem for every encoded $\rho_{RL}$. The environment and recovery ancilla may remain correlated with each other, but their joint state cannot depend on the logical amplitudes. Recovering only the two basis states without their coherence would not suffice.

7. Diagnose two explicit aliases

Under the promised one-error lookup, analyze $X_1X_2$ and $Z_1Z_4$. For each, compute the syndrome, the selected correction, and the residual logical class. Explain why these examples do not imply that every weight-two error fails.

Solution

Binary syndrome addition gives

$$s(X_1X_2) =10000000\oplus11000000 =01000000 =s(X_3).$$

The lookup applies $X_3$, and the residual is $X_1X_2X_3=\overline Z$.

Similarly,

$$s(Z_1Z_4) =00000010\oplus00000011 =00000001 =s(Z_7).$$

With $Z_7$ as the block-$C$ representative correction, the residual is $Z_1Z_4Z_7=\overline X$. In both cases the correction returns the state to the code space but changes the encoded qubit.

These are decoder-relative logical aliases outside the promised error set, not examples of degeneracy. They witness that the one-error lookup does not uniformly correct weight two, but they do not classify all weight-two errors. For instance, $Z_1Z_2$ is a stabilizer and has no logical effect. Other errors can be corrected accidentally depending on the decoder. Distance three states the uniform correction radius and the minimum logical weight, not that every error outside the radius must cause failure.

8. Audit the ideal depolarizing decoder

For independent depolarizing noise, count the weight-two Pauli strings that produce logical $X$ or logical $Z$ under the separated repetition decoder. Derive the leading term of $p_L$. Then explain the checks $p_L(0)=0$ and $p_L(3/4)=3/4$ and the limits of the result. As a computational extension, enumerate all $4^9$ phase-free Pauli strings to reproduce the full residual enumerator or logical-failure polynomial.

Solution

A logical $Z$ occurs when two physical errors in one block both have an $X$ component. Choose the block in three ways, the pair of sites in three ways, and choose $X$ or $Y$ independently on the two sites in four ways:

$$3\cdot3\cdot4=36.$$

A logical $X$ occurs when two errors in different blocks both have a $Z$ component. Choose the two blocks in three ways, one site in each in nine ways, and choose $Z$ or $Y$ independently in four ways:

$$3\cdot9\cdot4=108.$$

Each particular weight-two Pauli has leading probability $(p/3)^2$, so

$$p_L = (36+108)\left(\frac p3\right)^2+O(p^3) = 16p^2+O(p^3).$$

At $p=0$ only the identity occurs, so failure vanishes. At $p=3/4$, each one-qubit Pauli is equally likely and therefore all $4^9$ strings are equally likely. The recovery partitions them equally among four residual logical classes, giving failure probability $3/4$.

For the computational extension, encode each phase-free Pauli string as nine base-four digits, compute its eight-bit syndrome, apply the fixed separated recovery, and reduce the residual modulo the stabilizer. Accumulating by physical weight and residual logical class reproduces the full table above; substitution into

$$p_L(p) = \sum_{w=0}^{9} \bigl(N_w-N_{w,I_L}\bigr) \left(\frac p3\right)^w(1-p)^{9-w}$$

reproduces the displayed degree-nine logical-failure polynomial.

The full polynomial requires the fixed recovery on all syndromes and the declared independent Pauli channel. It says nothing by itself about faulty extraction, correlated noise, leakage, decoding latency, thresholds, or a device implementation.

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.
• D. P. DiVincenzo and P. W. Shor, “Fault-tolerant error correction with efficient quantum codes,” Physical Review Letters 77, 3260–3263, 1996, doi:10.1103/PhysRevLett.77.3260.
• 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.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press, 2010, doi:10.1017/CBO9780511976667.
• J. Preskill, Quantum Information, Chapter 7, “Quantum Error Correction,” working draft updated March 2026, pre-publication chapter.
• P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Physical Review A 52, R2493–R2496, 1995, doi:10.1103/PhysRevA.52.R2493.
• A. M. Steane, “Error correcting codes in quantum theory,” Physical Review Letters 77, 793–797, 1996, doi:10.1103/PhysRevLett.77.793.