Repetition, Bit-Flip, Phase-Flip, and Shor Codes

The repetition code promises one X error#

State codewords, correctable error set, stabilizers, and failure for two flips before presenting recovery.

Small codes are teaching instruments. They show redundancy, syndrome extraction, and recovery working against a limited error set — concretely enough to simulate in your head. They cannot prove a scalable machine, but they make the logic of quantum error correction mechanical instead of mystical.

The three-qubit repetition construction corrects a single bit flip but not arbitrary single-qubit errors. [nielsen-chuang][preskill-notes]

The three-qubit promise is deliberately narrow#

The bit-flip code uses $|0_L\rangle=|000\rangle$ and $|1_L\rangle=|111\rangle$, with stabilizers Z0Z1 and Z1Z2. Its ideal recovery contract covers I and one X on any physical qubit. It also preserves an arbitrary encoded superposition because parity checks reveal only which block parity changed, not whether the logical component was zero or one.

This is not cloning. Encoding maps one input qubit plus initialized ancillas through a unitary into $\alpha|000\rangle+\beta|111\rangle$. It does not create $(\alpha|0\rangle+\beta|1\rangle)^{\otimes3}$, whose expansion contains six additional basis terms. The encoded state has one logical degree of freedom distributed nonlocally.

Enumerate the eight promised basis cases#

For logical zero, no error and X0, X1, X2 produce 000, 100, 010, and 001. Their syndromes 00, 10, 11, and 01 select no correction, X0, X1, and X2, returning 000. For logical one, the corresponding words 111, 011, 101, and 110 produce the same syndrome sequence and return 111. Recovery is independent of the logical value.

Generate those rows rather than hand-copying them. The executable fixture computes parity bits, chooses a correction, applies it, and asserts equality with the original codeword. A second assertion checks that syndrome labels agree with the operator derivation from Chapter 47. This catches a decoder table that is self-consistent but wired to reversed check order.

Eight truth-table rows verify the promise#

Generate no-error and every single-flip case for logical zero and one from the companion model.

The three-qubit bit-flip code encodes $\lvert0_L\rangle=\lvert000\rangle$ and $\lvert1_L\rangle=\lvert111\rangle$. An arbitrary logical state becomes $\alpha\lvert000\rangle+\beta\lvert111\rangle$. Note what this is not: three copies of $\alpha\lvert0\rangle+\beta\lvert1\rangle$, which the no-cloning theorem forbids. It is a single entangled state spread across the register. A single bit flip moves the state out of the code space in a way a syndrome can identify.

Phase-flip protection follows from changing basis with Hadamard operations around a repetition construction. [nielsen-chuang]

Make the uncorrectable case visible#

Start with logical zero and apply X0X1, producing 110. Its syndrome is 01, the same signature that a single X2 creates on a valid codeword. The minimum-weight decoder therefore applies X2 and obtains 111: a valid codeword carrying the wrong logical value. The recovery did exactly what its error model prescribed; the actual error lay outside that model.

Every weight-two bit-flip pattern has the same ambiguity with the complementary weight-one pattern. Majority decoding expresses the result classically, but the operator statement is more precise: the product of actual error and chosen recovery is X0X1X2, the logical X operator. A wrong decode can return to the code space, so “all checks are +1” after recovery does not prove the logical state is correct.

Hadamards rotate phase errors into bit errors#

Trace the basis change and preserve the distinction between X and Z channels.

The error model comes first. The bit-flip channel $\mathcal{E}(\rho)=(1-p)\rho+pX\rho X$ is what the repetition code is built against, and the syndrome map $s=H_e e\pmod 2$ turns each error pattern into a diagnostic signature.

Shor's nine-qubit scheme was an early code capable of correcting arbitrary single-qubit errors under its model. [shor-code-1995]

Hadamard conjugation builds phase-flip protection#

Hadamard exchanges X and Z: $HXH=Z$ and $HZH=X$. Conjugating the repetition construction by H on all three qubits therefore turns a physical Z error in the original basis into an X error in the rotated basis. Run the same parity diagnosis there, apply the correction, and rotate back. The basis changes are part of the code definition, not optional visualization.

The phase-flip codewords can be written $|0_L\rangle=|+ + +\rangle$ and $|1_L\rangle=|- - -\rangle$ under this convention. Measuring physical qubits directly in the X basis would reveal logical information; the extraction circuit instead measures the appropriate commuting X-type parities with ancillas.

A Y error is proportional to XZ and therefore carries both bit- and phase-error components. The three-qubit bit-flip code alone does not correct it, and the phase-flip code alone does not correct it. Correcting an arbitrary single-qubit Pauli requires a construction whose syndrome information distinguishes both components.

Shor concatenates protection in two directions#

Describe the nine-qubit block structure and why X, Z, and Y single-qubit errors fit its ideal correctable set.

Bit-flip codes handle X -like errors. Phase-flip codes handle Z -like errors by the same construction in a rotated basis: Hadamard gates turn phase flips into bit flips, the repetition machinery catches them, and Hadamards turn back. Shor's nine-qubit code nests the two — a phase-flip triplet whose three branches are each bit-flip triplets — so any single-qubit error, X , Z , or Y (which acts as both), lands in a distinct syndrome. That nesting, not a bigger majority vote, is the idea that scales.

The Steane code provides a distinct seven-qubit stabilizer construction and should not be presented as a variant of Shor concatenation. [steane-code-1996][gottesman-stabilizer]

Shor concatenation separates both components#

Shor’s code uses three GHZ-like blocks. One conventional expression is $|0_L\rangle=(|000\rangle+|111\rangle)^{\otimes3}/(2\sqrt2)$ and $|1_L\rangle=(|000\rangle-|111\rangle)^{\otimes3}/(2\sqrt2)$. Within each block, Z-parity checks locate one X component. Comparisons across blocks diagnose the Z component through the outer phase-flip repetition structure.

An arbitrary single-qubit operator is a linear combination of I, X, Y, and Z. If the code corrects those Pauli actions on each location and the error-correction conditions hold, linearity extends correction to that arbitrary one-qubit error. The decoder does not need to know a continuous rotation angle; syndrome projection separates the relevant discrete error subspaces.

Y is not a third independent mystery: up to phase, Y=XZ. Its syndrome combines the bit- and phase-component signatures. The global phase attached to the Pauli product is unobservable, while the two syndrome components determine the recovery class.

Distance three sets the exact boundary#

Connect correctable weight, distance, and the failure of ambiguous weight-two patterns.

Encode logical zero as $\lvert000\rangle$. A bit flip strikes the second physical qubit, so the register reads $\lvert010\rangle$. The parity checks report $(s_0,s_1)=(1,1)$, the signature of a middle-qubit flip, and applying $X$ to that qubit returns the word to $\lvert000\rangle$.

Code definitions alone do not satisfy the additional conditions required for fault-tolerant computation. [fault-tolerant-roads]

Distance three is the exact algebraic boundary#

A distance-three code detects up to two errors in the operator sense and corrects an arbitrary error on at most $\lfloor(d-1)/2\rfloor=1$ location. Detection and correction are different promises. The selected weight-two repetition-code example is detectable relative to some codeword transitions but not uniquely correctable; the syndrome aliases a more likely single fault.

Error degeneracy can make different physical operators equivalent on the code space when they differ by a stabilizer. A decoder should reason about equivalence classes, not insist on reconstructing the literal microscopic fault. Success means the combined error and recovery acts trivially on logical information, not that every physical event was identified.

From code definition to fault-tolerant extraction#

List ancilla, propagation, measurement, and repeated-cycle requirements intentionally absent here.

Now the important case: the superposition $\alpha\lvert000\rangle+\beta\lvert111\rangle$ suffers the same flip and becomes $\alpha\lvert010\rangle+\beta\lvert101\rangle$ . The same syndrome logic identifies the middle qubit, the same X repairs it, and α and β were never read. The correction acted on the error, not the data — which is the only way it can work.

The three-qubit repetition construction corrects a single bit flip but not arbitrary single-qubit errors. [nielsen-chuang][preskill-notes]

Ideal correction is not fault-tolerant extraction#

The truth tables assume perfect encoding, ancillas, check gates, measurement, decoder, and recovery. In hardware, one ancilla fault can propagate through several data interactions; measurement errors can mimic data syndromes; and recovery pulses add faults. Repeated rounds and verified or carefully scheduled ancillas are needed to bound propagation.

Logical gates add another obligation. An operation must preserve the encoded computation and prevent one fault from spreading into an uncorrectable pattern within a block. The Shor code demonstrates that an arbitrary single physical-qubit error is correctable under ideal extraction; it does not by itself demonstrate a scalable gate set, threshold, useful logical lifetime, or competitive overhead.

The publishable small-code matrix therefore contains both green and red rows: every no-error and single-error case must recover, the chosen weight-two input must decode to the wrong logical value exactly as predicted, and phase cases must show both Hadamard layers. Hiding the red row would erase the code’s most important specification.

The matrix should separate detection, chosen recovery, final stabilizer signs, and logical outcome. The weight-two row is instructive because its final stabilizers return to +1 while its logical outcome flips. A pass/fail column based only on code-space membership would misclassify that row as corrected.

For phase protection, test more than basis labels. Start with $\alpha|+++\rangle+\beta|---\rangle$, inject one Z, conjugate by H on all data qubits, run the bit-flip syndrome and recovery, then conjugate back. The output must match the encoded input up to a global phase for several analytic α,β choices. Testing only $\lvert +++ \rangle$ can conceal a relative-phase defect.

The Shor symbolic table should list, for each of nine locations, the syndrome class of X, Z, and Y rather than materializing a 512-amplitude state for every row. An independent small-state or stabilizer calculation can sample rows to verify the table. This keeps the artifact inspectable while still demonstrating that both error components are represented.

Error correction succeeds on spans of correctable errors, not merely a menu of named Paulis. If coherent error $aI+bX+cY+dZ$ acts on one physical qubit, syndrome measurement projects the state into corresponding error subspaces and the conditioned recovery restores logical information when the code-correction conditions are satisfied. That is why discrete syndrome logic can address continuous small rotations without estimating their angle.

Recovery verification should compare logical states, not demand that every physical ancilla return to its initial value. Ancillas may be measured and reset, and stabilizer-equivalent physical states encode the same logical information. The contract names which registers are outputs, which are disposable syndrome workspace, and whether equality is exact or up to global phase.