The Shor Code

An arbitrary error on one qubit is a linear operator on a two-dimensional Hilbert space, so it can always be written in the Pauli basis as

for complex coefficients $a,b,c,d$. Here $X$ is a bit flip, $Z$ is a phase flip, and $Y = iXZ$ is both at once. This is the crucial fact that makes discrete error correction possible for a continuous space of errors: if a code can correct arbitrary $X$ and $Z$ errors on each qubit, it can correct any error at all, because correction is linear and the measurement of the syndrome forces the error into one definite Pauli component even if the physical noise was a continuous rotation. The Three-Qubit Code corrects a single bit flip by encoding $|0\rangle \mapsto |000\rangle$, $|1\rangle \mapsto |111\rangle$, and detecting disagreement among the three qubits via parity checks $Z_1Z_2$ and $Z_2Z_3$. Applying a Hadamard transform to every qubit converts this into a code that corrects a single phase flip instead, since $H X H = Z$: it encodes $|0\rangle \mapsto |{+}{+}{+}\rangle$, $|1\rangle \mapsto |{-}{-}{-}\rangle$, with $|\pm\rangle = (|0\rangle \pm |1\rangle)/\sqrt2$. The Shor code concatenates these two ideas. First, encode the logical qubit against phase flips using the three-block structure

written more explicitly as sums of $|000\rangle$ and $|111\rangle$ states. Then encode each of the three qubits in that expression using the bit-flip code, replacing every $|0\rangle$ by $|000\rangle$ and every $|1\rangle$ by $|111\rangle$. This gives the full nine-qubit codewords:

Each of the three parenthesized triples is a block. Bit flips are detected and corrected within a block by comparing the three qubits of that block. Phase flips are detected by comparing the overall sign (relative phase) between blocks, which is a property of triples of qubits, not individual ones — this is why phase-flip protection needs three blocks, giving $3 \times 3 = 9$ qubits in total.

Step 1 — Outer (phase) encoding. Take the input qubit $\alpha|0\rangle + \beta|1\rangle$ and apply the phase-flip code: $CNOT$ into two ancillas, then Hadamard all three, producing

Step 2 — Inner (bit-flip) encoding. Encode each of the three qubits above using the bit-flip code: for each qubit, introduce two fresh ancillas in $|0\rangle$ and apply two $CNOT$s so that $|0\rangle \to |000\rangle$ and $|1\rangle \to |111\rangle$. Since $|\pm\rangle = (|0\rangle \pm |1\rangle)/\sqrt2$, this turns each $|\pm\rangle$ into $(|000\rangle \pm |111\rangle)/\sqrt2$.

Step 3 — Noise. The channel acts on one (or more, for intuition) of the nine physical qubits with some Pauli error (or an arbitrary unitary/decoherence, by linearity).

Step 4 — Bit-flip syndrome extraction, within each block. For each of the three blocks independently, measure the two stabilizer generators $Z_1Z_2$ and $Z_2Z_3$ (of that block) using ancilla qubits, exactly as in the three-qubit code. This identifies which qubit (if any) inside the block suffered a bit flip, without measuring the encoded data.

Step 5 — Bit-flip correction. Apply $X$ to the identified qubit in each block, restoring each block to a consistent superposition of $|000\rangle$ and $|111\rangle$.

Step 6 — Phase-flip syndrome extraction, across blocks. Decode each block back to a single qubit conceptually (or work with the collective parity operators $X_1X_2\cdots X_6$ and $X_4X_5\cdots X_9$, the two stabilizers comparing block signs). This determines whether a relative phase flip occurred between block 1 and block 2, or between block 2 and block 3.

Step 7 — Phase-flip correction. Apply $Z$ to any one qubit in the identified block, which flips the relative sign of that whole block and restores the correct global phase pattern. ``` // SHOR-9 ENCODE function ENCODE(alpha, beta): // qubit 0 holds alpha|0> + beta|1> // outer phase-flip encoding using 2 ancillas (qubits 3, 6) CNOT(0, 3) CNOT(0, 6) H(0); H(3); H(6) // inner bit-flip encoding: each of the 3 "block leaders" gets 2 more ancillas for leader in [0, 3, 6]: a, b = leader + 1, leader + 2 // fresh ancillas, initially |0> CNOT(leader, a) CNOT(leader, b) return qubits[0..8] // the 9-qubit codeword // SHOR-9 SYNDROME DECODE + CORRECT function DECODE_AND_CORRECT(qubits[0..8]): // --- Step A: bit-flip correction inside each block of 3 --- for block_start in [0, 3, 6]: q0, q1, q2 = qubits[block_start], qubits[block_start+1], qubits[block_start+2] s1 = MEASURE_STABILIZER(Z(q0) Z(q1)) // ancilla-assisted parity check s2 = MEASURE_STABILIZER(Z(q1) Z(q2)) flip_target = BIT_FLIP_TABLE[(s1, s2)] // -1 = none, else 0/1/2 (local index) if flip_target != -1: APPLY_X(qubits[block_start + flip_target]) // --- Step B: phase-flip correction across the 3 blocks --- p1 = MEASURE_STABILIZER( PRODUCT_X(qubits[0..5]) ) // X1..X6 compares block 1 vs 2 p2 = MEASURE_STABILIZER( PRODUCT_X(qubits[3..8]) ) // X4..X9 compares block 2 vs 3 phase_block = PHASE_FLIP_TABLE[(p1, p2)] // -1 = none, else 0/1/2 (block index) if phase_block != -1: APPLY_Z(qubits[phase_block * 3]) // Z on any one qubit in that block return qubits[0..8] // corrected codeword, logical state untouched ``` The two lookup tables are identical in structure to the three-qubit repetition-code decoder: syndrome $(0,0)$ means no error, $(1,0)$ localizes qubit/block 1, $(1,1)$ localizes the middle one, $(0,1)$ localizes the last one.

Resource counts. Encoding uses 9 physical qubits and 8 $CNOT$s plus 3 Hadamards ($O(1)$ gates, independent of any problem size, since this protects one logical qubit). Syndrome extraction requires 6 ancilla qubits for the six bit-flip stabilizer measurements (or these ancillas can be reused sequentially) plus 2 more for the two phase-flip stabilizer measurements, each requiring a constant number of $CNOT$/Hadamard gates. All operations are $O(1)$ in circuit depth and gate count — the Shor code is a fixed, constant-overhead code, not an asymptotic family. This is a strength for teaching, but a weakness for scaling: unlike the Surface Code, its overhead per logical qubit does not shrink relative to the target error rate.

Correctness argument. The proof rests on three facts: 1. Pauli decomposition. Any single-qubit error operator $E$ can be written as $E = aI + bX + cY + dZ$. If the code's correction procedure returns the state to the correct codeword whenever the actual error was $I$, $X$, $Y$, or $Z$ on any one physical qubit, then by linearity of quantum mechanics it corrects any superposition/mixture of such errors — the syndrome measurement projects the noisy state onto the subspace corresponding to one specific Pauli error, collapsing the continuous uncertainty into a discrete, correctable case. This is the reason a code built to handle just $\{I, X, Y, Z\}$ per qubit handles literally every possible single-qubit error, including small-angle rotations and amplitude damping. 2. Bit-flip correction within a block. Inside a block, $X_i$ on qubit $i$ anticommutes with exactly the stabilizer generators $Z_1Z_2$ or $Z_2Z_3$ that include qubit $i$, giving each of the three possible single-$X$ errors a distinct nontrivial syndrome — while $I$ gives the trivial syndrome. Since the block only ever holds a state in the 2-dimensional code space spanned by $|000\rangle,|111\rangle$, this syndrome uniquely diagnoses the error and correction is guaranteed by the same argument used for the Three-Qubit Code. Two simultaneous $X$ errors in the same block are misdiagnosed as a single flip on the third qubit — this is the code's actual failure mode, discussed below. 3. Phase-flip correction across blocks. A $Z$ error on any one qubit within a block flips the relative sign of that block's $|000\rangle/|111\rangle$ superposition — i.e., a $Z$ anywhere in block $k$ acts identically, up to the bit-flip code's own error correction, to a single logical $Z$ on that block considered as one unit. Comparing block signs via $X_1\cdots X_6$ and $X_4 \cdots X_9$ (the analogue of $Z_1Z_2, Z_2Z_3$ but in the Hadamard-conjugated frame) localizes which block suffered the sign flip, and applying $Z$ to any one qubit in that block restores it. Crucially, a $Y$ error on one qubit is $Y = iXZ$: the $X$ part is caught and fixed by step 4/5, and the same physical event's $Z$ part is caught and fixed by step 6/7 — the two correction stages act on the same photon-scale event but different aspects of it, and their order does not matter because bit-flip correction operates entirely within blocks while phase-flip correction operates entirely across blocks, so the two procedures commute.

Degeneracy. The Shor code is a degenerate code: several distinct physical errors (e.g. $Z$ on any of the three qubits in a block) produce the same syndrome and are corrected by the same recovery operation, because they act identically on the codespace. Degenerate codes can, in principle, correct more errors than a naive counting bound would suggest, and this is a preview of the richer structure exploited by general Stabilizer Codes.

Honest tradeoff. The Shor code corrects any single-qubit error but is not distance-optimal: it uses 9 qubits where later constructions (e.g. the 5-qubit code) achieve the same single-error-correcting guarantee with fewer physical qubits, at the cost of a less intuitive derivation. The Shor code's virtue is conceptual clarity and historical priority, not efficiency.

Take the logical state $|\psi\rangle_L$ encoding $\alpha|0\rangle + \beta|1\rangle$, and suppose physical qubit q5 (the middle qubit of Block 2) suffers a $Y$ error, i.e. the channel applies $Y_5 = iX_5Z_5$.

Notice the key point that makes this a genuine correctness demonstration rather than a toy case: the single physical event $Y_5$ triggered two separate, independently diagnosed syndromes (a bit-flip syndrome localized to a specific qubit within a block, and a phase-flip syndrome localized to a specific block), and fixing each independently fixed the whole error — exactly the linear-decomposition argument from the correctness section, now traced through concrete syndrome bits rather than asserted abstractly.

The Shor code itself is rarely used in production hardware today because its 9-qubit overhead is inefficient compared to more modern codes, but its conceptual DNA is everywhere. Every leading quantum computing effort — Google's and IBM's superconducting processors, IonQ's and Quantinuum's trapped-ion systems, and photonic approaches — relies on the same core idea: encode a logical qubit redundantly, measure stabilizers via ancillas without touching the encoded data, and correct. The Surface Code, the workhorse of most current large-scale hardware roadmaps, is a two-dimensional descendant of exactly this bit-flip/phase-flip separation, using local stabilizer checks arranged on a lattice instead of Shor's flat concatenation. The broader framework of Stabilizer Codes that Daniel Gottesman built to describe Shor's code and its relatives underlies essentially all of modern Fault-Tolerant Quantum Computing theory, including magic-state distillation and logical gate synthesis. Understanding the Shor code is the cleanest way to internalize why discretizing continuous quantum errors into Pauli components is always possible — a fact quietly assumed in every subsequent, more sophisticated code.

Ask the tutor: How would you adapt the Shor code's decoding circuit if you only had ancilla qubits available for two stabilizer measurements at a time, instead of all eight at once?