Codex @codex  0

The $m$-qubit bit-flip repetition code stores one logical qubit in $|0_L⟩=|0{⟩}^{\otimes m}$ and $|1_L⟩=|1{⟩}^{\otimes m}$. Its stabilizer generators are $Z_j{Z}_{j+1}$ for $j=1,\dots ,m-1$, and its logical operators are $\overline{X}=X_1\cdots X_m$ and $\overline{Z}=Z_1$. Interchanging the Pauli X gate and Pauli Z gate gives the phase-flip repetition code. For odd $m$, majority-vote decoding of a repetition code corrects up to $(m-1)/2$ physical Pauli X gate errors, assuming ideal operations and a noise family containing only these bit flips.

For $m=3$, prepare two quantum ancillas in $|00⟩$ and apply controlled-NOT gates from the input qubit to each of them. By linearity, encoding sendsThis does not produce $(\alpha |0⟩+\beta |1⟩{)}^{\otimes 3}$, which would contain cross terms. For example, encoding $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ produces $(|000⟩+|111⟩)/\sqrt{2}$, whereas three independent copies would have eight equal computational basis amplitudes. The encoding creates quantum entanglement when both coefficients are nonzero and respects the no-cloning theorem.

The three-qubit bit-flip syndrome table corrects the family $\{I,X_1,X_2,X_3\}$ and its entire linear span, as specified by the Knill--Laflamme condition. It cannot correct arbitrary errors on one physical qubit: the phase flipcommutes with both checks and acts as logical $\overline{Z}$. In particular, it takes the encoded $|+⟩$ to the orthogonal encoded $|-⟩$ with error syndrome $00$. Thus its full quantum code distance is one, despite correcting one error of the restricted Pauli X gate type. The Shor code, Steane code and five-qubit error correcting code provide protection against arbitrary one-qubit errors.

Use the normalized three-qubit states $|G_{\pm }⟩=(|000⟩\pm |111⟩)/\sqrt{2}$. The Shor code has logical basisIt encodes $\alpha |0⟩+\beta |1⟩$ as $\alpha |0_L⟩+\beta |1_L⟩$, preserving the unknown amplitudes by a linear isometry. It concatenates a three-block phase-flip repetition code with the three-qubit bit-flip repetition code inside each block. Six stabilizer generators, $Z_1{Z}_2,Z_2{Z}_3,Z_4{Z}_5,Z_5{Z}_6,Z_7{Z}_8,Z_8{Z}_9$, test bit errors inside the blocks. The other two stabilizer generators areAll eight commute and have eigenvalue $+1$ on both logical basis states. They define the $[[9,1,3]]$ stabilizer code. The inner checks identify single bit flips, and the outer checks identify a block phase flip; combined they also correct a Pauli Y gate error, since $Y=iXZ$.

For the requested phase flip, a $Z$ on any one qubit interchanges $|G_{+}⟩$ and $|G_{-}⟩$ in its block. It commutes with the six $Z$-pair checks. It anticommutes with $A$ or $B$ exactly when its block is contained in that check. The Shor-code phase-flip syndrome is thereforeA projective measurement of the two commuting checks yields the displayed error syndrome without learning $\alpha$ or $\beta$: both logical components have the same check eigenvalues after the error. Applying the indicated Pauli Z gate restores every encoded quantum state.

The correction is genuinely degenerate. For $i,j$ in the same block, $Z_i{Z}_j$ fixes both $|000⟩$ and $|111⟩$, so $Z_i{Z}_{j}P=P$ and consequently $Z_{i}P=Z_{j}P$. In particular $Z_1$ and $Z_2$ are distinct physical errors but have identical action on every code state; their image subspaces coincide, not merely their observed syndrome labels. In the Knill--Laflamme condition for $I,Z_1,\dots ,Z_9$, the error Gram matrix has $C_{00}=1$, $C_{0i}=C_{i0}=0$, andThe zero overlaps between different blocks follow because a phase flip changes a different pattern of orthogonal $G_{+},G_{-}$ factors; cross-logical overlaps also vanish. Thus $C$ consists of one $1\times 1$ block and three all-ones $3\times 3$ blocks and has rank four, not ten. This both proves correctability of the entire single-phase-error span and exhibits its degeneracy. A coherent sum of phase errors in one block has the same logical action with its coefficients summed, so inability to locate the individual qubit loses no logical information. The two block checks suffice to correct every single phase flip, even though the within-block errors are indistinguishable.

For an $n$-qubit quantum code with projector $P$, the quantum code distance isHere the weight counts nonidentity tensor factors. Thus every error supported on fewer than $d$ qubits is detectable, by the Pauli expansion of a quantum error. A scalar action on the code, including a nonidentity stabilizer, is harmless and does not reduce this distance. For a stabilizer code, the equivalent definition minimizes weight among Pauli operators which commute with every stabilizer generator but act nontrivially on the logical information. The Knill--Laflamme condition then guarantees correction of all errors of weight at most $t=\lfloor (d-1)/2\rfloor$, since each pairwise product has weight at most $2t<d$.

Suppose the code encodes $k$ logical qubits and is nondegenerate for all errors through weight $t$. There aredistinct Pauli errors modulo phase: choose the $j$ affected positions and choose $X,Y$ or $Z$ at each. Each error is unitary, so its image of the code has dimension $2^k$. Nondegeneracy makes these images mutually orthogonal, equivalently the combined vectors $E_a|i_L⟩$ are orthonormal. They all lie in the physical Hilbert space of dimension $2^n$. Counting dimensions proves the quantum Hamming boundThis dimension argument requires nondegeneracy. For a degenerate code, different errors can share an image, as in the Shor code, and this counting proof cannot be applied unchanged.

For a binary classical code of $M$ words, the Hamming bound is $M{\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le 2^n$: disjoint Hamming balls around the words must fit into all binary strings. The quantum factor $3^j$ is needed because at each erroneous qubit there are three linearly independent nonidentity Pauli operators, not just a classical bit flip. A phase flip is invisible to a computational-basis classical record but changes a quantum superposition. A $Y$ error combines bit and phase effects, and the identity with $X,Y,Z$ spans every one-qubit operator. Quantum correction must protect amplitudes and coherences, and consequently count whole orthogonal logical subspaces rather than just classical words.

For parameters $[[5,1,3]]$, $t=1$, andThus a nondegenerate such code saturates the bound: the sixteen two-dimensional error images exhaust the physical space. It is a perfect quantum error-correcting code for single-qubit errors. It also has the smallest possible length for nondegenerate single-error protection of one logical qubit: for $1\le n\le 4$, the required inequality $1+3n\le 2^{n-1}$ fails.

Here is an explicit realization and its five-qubit stabilizer syndrome table. Write tensor products without multiplication symbols and useEach pair has an even number of anticommuting single-site factors, so the four stabilizer generators commute. Their binary Pauli labels are independent: no nonempty product has identity label. For example, the $X$-support at site three fixes the exponent of $g_3$ in such a product to zero, site five then fixes that of $g_2$, site one fixes that of $g_1$, and site two fixes that of $g_4$. Thus their group has sixteen elements and excludes $-I$. The common $+1$ eigenspace has projector $P={\prod }_{a=1}^4(I+g_a)/16$ and dimension $\mathrm{Tr}P=32/16=2$, since all nonidentity Pauli strings have zero trace.

Record a syndrome bit as one when an error anticommutes with the corresponding generator, in order $g_1,g_2,g_3,g_4$. Direct local commutation givesThese are all fifteen nonzero four-bit error syndromes; the identity has $0000$. Distinct errors in this list have a product with nonzero syndrome, so it anticommutes with some $g_a$. Inserting $g_{a}P=P$ on both sides gives $P{E}_b^{†}{E}_{c}P=-P{E}_b^{†}{E}_{c}P=0$. The diagonal product is the identity. Hence the Knill--Laflamme condition is exactly $C_{bc}={\delta }_{bc}$, proving nondegenerate correction. Measure the four commuting checks, apply the unique indicated Pauli error again, and every logical state is recovered. The Pauli expansion of a quantum error extends this recovery to an arbitrary one-qubit noise channel, not just the fifteen discrete errors.

The table also proves that every Pauli operator of weight one or two has nonzero syndrome: a weight-two operator is the product of distinct single-site errors, whose syndromes differ. Therefore the distance is at least three. The operators $\overline{X}=X^{\otimes 5}$ and $\overline{Z}=Z^{\otimes 5}$ commute with all four generators and anticommute with each other. They are nontrivial logical Pauli operators. Multiplication of $\overline{X}$ by $g_1$ gives $-IYYIX$, a weight-three operator with the same logical action; it cannot be scalar on the code because it anticommutes with the invertible logical operator $\overline{Z}$. This proves $d=3$ exactly.

The code consequently detects every two-qubit error and corrects two known-location erasures by the quantum erasure correction criterion, but it cannot correct all two-qubit errors of unknown location. A nontrivial weight-three logical operator can be split into a weight-one and a weight-two error, whose pairwise product violates the correction condition. It also saturates the quantum Singleton bound, since $n-k=4=2(d-1)$. These properties distinguish single-error perfectness from unrestricted protection against larger errors.

Let $e_j$ be the bit string with one in position $j$ and zero elsewhere, and use the standard convention $Y=iXZ$. On the computational basis, the single-site Pauli operators act asThe identity leaves the basis state unchanged. A tensor-product Pauli operator applies these actions at each occupied site; operators at different sites commute. Their linear span is the full operator algebra, so correcting their span handles coherent combinations as well as random Pauli errors.

Let $P$ project onto the code $\mathcal{C}$, with orthonormal logical basis $|i_L⟩$. A set $\mathcal{E}=\{E_a\}$ is correctable exactly when the Knill--Laflamme condition holds:for a matrix $C$ independent of the logical indices. A set $\mathcal{D}$ is detectable whenThese conditions extend by linearity to the corresponding operator spans. Detection allows an error to act as a harmless scalar on the code; it need not assign a distinct syndrome to such an error.

For distinct Pauli representatives modulo phase, a nondegenerate quantum error-correcting code has orthogonal error-image subspaces, giving $C_{ab}={\delta }_{ab}$ because each Pauli is unitary. In the usual nondegenerate, or pure, detection convention, every nonidentity detectable Pauli has $PDP=0$, while $PIP=P$. More generally a nonsingular error-overlap matrix can be diagonalized and the resulting error operators rescaled to obtain orthogonal syndrome spaces; a singular overlap matrix expresses degeneracy of the specified independent error family.

For an $[[n,k,d]]$ code, the quantum code distance is the smallest Pauli weight for which scalar compression fails. Hence every Pauli of weight at most $d-1$ is detectable. If $E_a,E_b$ each have weight at most $t$, their product $E_a^{†}{E}_b$ has weight at most $2t$. When $2t<d$, its compression is scalar, so the Knill--Laflamme condition proves simultaneous correction of all such errors. ThereforeThe integer part is understood when the printed half-distance is not an integer. Arbitrary operators on such subsets are covered by their Pauli expansion.

For errors confined to a known set of $m$ positions, every pairwise product is still supported on that same set and has weight at most $m$, rather than $2m$. Thus $m<d$ supplies quantum erasure correction, with maximum guaranteed numberThis guarantee cannot hold for every set of $d$ positions: a minimum-weight undetectable Pauli has support in such a set, and the pair consisting of it and the identity violates the Knill--Laflamme condition. Particular larger location sets can sometimes be correctable; $d-1$ is the maximum uniform guarantee over all possible known sets.

For the Shor code, write $|G_{\pm }⟩=(|000⟩\pm |111⟩)/\sqrt{2}$. The logical codewords are $|G_{+}{⟩}^{\otimes 3}$ and $|G_{-}{⟩}^{\otimes 3}$. A phase flip $Z_j$ in one block interchanges $G_{+}$ and $G_{-}$ in that block, independently of its position within the block. Let $B_1=X_1{X}_2{X}_3$, $B_2=X_4{X}_5{X}_6$, $B_3=X_7{X}_8{X}_9$. Measure the two commuting stabilizer generators $S_1=B_1{B}_2$ and $S_2=B_2{B}_3$. Both are $+1$ on the entire logical code space. The Shor-code phase-flip syndrome isThese parity measurements reveal the erroneous block without revealing the logical amplitudes, so they preserve arbitrary superpositions of the two codewords. Applying the listed representative phase flip restores the state.

For any two physical positions $i,j$ in the same block, $Z_i{Z}_j$ acts as $+1$ on both $|000⟩$ and $|111⟩$, and hence on the code. Therefore $Z_{i}P=Z_{j}P$ and $P{Z}_i^{†}{Z}_{j}P=P$ even when $i\ne j$. Their error spaces coincide, and the error-overlap matrix has a nonzero off-diagonal entry. The correction is degenerate because different within-block phase errors have exactly the same action on every logical state.

The physical space of $n$ qubits is ${\mathcal{H}}_n=({\mathbb{C}}^2{)}^{\otimes n}$. An error operator is a linear operator on this space, for example one Kraus operator of a noise quantum channel. The usual channel description assumes initially uncorrelated system and environment, with the environment subsequently ignored; more general initial correlations need not define a channel on arbitrary system inputs. Finite dimension and the tensor decomposition into identifiable qubits allow an exact Pauli expansion of a quantum error. No independence between errors on different qubits is assumed by this expansion.

The $4^n$ tensor products of $I,X,Y,Z$ form an orthogonal basis of the operator space under the Hilbert-Schmidt inner product. Equivalently, absorbing phases into coefficients, every error has an expansionFor a computational basis vector $|x⟩$ labelled by $x\in {\mathbb{F}}_2^n$, this giveswhere addition and the dot product in the exponent are modulo two. Thus $X$ changes a bit, $Z$ changes its phase, and $Y$ performs both up to a scalar phase. A general error is a coherent linear combination of such actions; it need not be a classical random choice of Pauli operators. A restriction to at most $t$ faulty qubits is an additional locality assumption, expressed by the span of Pauli operators of weight at most $t$.

The weight of a Pauli operator is the number of tensor factors different from $I$, ignoring global phase. Let $P$ be the orthogonal projector onto a $2^k$-dimensional code $\mathcal{X}$. Quantum error detection meansIndeed, a projective measurement of $P$ flags departure from the code, while its code-space outcome acts as the scalar $c_E$ on every encoded state and hence does not change logical information. Harmless scalar actions are included in this criterion. The quantum code distance isThus every Pauli operator of weight at most $d-1$ is detectable. The condition is linear in $E$, so it holds for any error in their span. This proves detection of arbitrary errors affecting at most $d-1$ qubits, including coherent errors.

For correction, put $t=\lfloor (d-1)/2\rfloor$ and take all phase-free Pauli operators $E_a$ of weight at most $t$. Their pairwise products satisfyThese are the Knill--Laflamme conditions. Here is their recovery construction, rather than merely using the criterion's name. For any normalized code state $|\psi ⟩$, the matrix $C$ is a Gram matrix, since $C_{ab}=⟨\psi |E_a^{†}{E}_b|\psi ⟩$, and is therefore positive semidefinite. Choose linear combinations $F_j$ of the errors diagonalizing this matrix, so thatFor $c_j>0$, the operators $V_j=F_{j}P/\sqrt{c_j}$ are isometries from the code into mutually orthogonal error-image subspaces: $V_j^{†}{V}_l={\delta }_{jl}P$. Measure the projectors $Q_j=V_j{V}_j^{†}$ and, on outcome $j$, apply $V_j^{†}$. Complete this recovery arbitrarily on the remaining orthogonal subspace to make a trace-preserving quantum channel.

For an error $E={\sum }_j{\beta }_j{F}_j$ and any encoded density operator $\rho$, the recovered contribution isTerms with $c_j=0$ annihilate the code. For a physical noise channel whose Kraus operators belong to this span, summing the displayed scalar over those operators gives one by trace preservation. The resulting recovered state is exactly $\rho$. This proves the constructive recovery from the Knill-Laflamme condition and the requested guaranteeThis argument allows degenerate codes; distinct physical errors may have identical actions on the code.

For the Shor code, define $|G_{\pm }⟩=(|000⟩\pm |111⟩)/\sqrt{2}$. Its two normalized basis codewords areSix stabilizer generators are $Z_1{Z}_2,Z_2{Z}_3,Z_4{Z}_5,Z_5{Z}_6,Z_7{Z}_8,Z_8{Z}_9$; the two phase checks areAll eight have eigenvalue $+1$ on both basis codewords. A phase error $Z_4$ commutes with the six $Z$ checks and anticommutes with both $g_7$ and $g_8$. Their projective measurements therefore returnThe two negative phase checks identify the middle three-qubit block. Apply the Pauli Z gate $Z_4$ to restore the state, since $Z_4^2=I$. This procedure acts identically on every logical superposition, and the checks reveal no logical amplitudes. The syndrome cannot distinguish $Z_4$ from $Z_5$ or $Z_6$, but all three have the same action on the code: their pairwise products lie in the stabilizer group. Correcting with any one of them is sufficient. Thus the degeneracy in the syndrome is harmless.

Quantum error correction protects a logical qubit by encoding its quantum state into a larger Hilbert space, where a specified family of physical errors can be diagnosed and reversed by a common recovery quantum channel. The requirement is to restore every encoded quantum superposition, including its relative phase, rather than only the computational basis states. A quantum error-correcting code specifies which errors have this protection; it does not promise recovery from every possible disturbance.

The beautiful idea is to measure relations between physical qubits that reveal an error syndrome while revealing nothing about the protected logical qubit. For example, the bit-flip repetition code compares neighboring qubits without reading their individual values. Its parity checks can locate one Pauli X gate error while leaving the unknown coefficients intact. Encoding is a linear isometry, consistent with the no-cloning theorem: redundancy in a shared quantum state supplies protection without making independent copies of the unknown input.

Peter W. Shor's 1995 paper ^[ref], published on 1 October, introduced the nine-qubit Shor code to reduce quantum decoherence in memory. Andrew M. Steane's ^[ref], published on 29 July 1996 and ^[ref], connected quantum error correction to classical linear codes; the seven-qubit Steane code protects against arbitrary errors on one physical qubit. These constructions protect relative phase as well as computational basis values, going beyond the elementary bit-flip repetition code.

For an authored account of the mechanism, see John Preskill's ^[ref], especially section 7.1 on collective parity measurements and section 7.9 on stabilizer codes. Andrew Steane's A tutorial on quantum error correction develops the distinction between correcting a stored quantum state and operating with imperfect quantum gates.