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.

The matrix $C$ in the Knill--Laflamme condition is positive semidefinite, since $v^{†}Cv$ is the squared norm of ${\sum }_a{v}_a{E}_a|\psi ⟩$ for any normalized code state. Diagonalizing it gives linear combinations $F_j$ with $P{F}_j^{†}{F}_{l}P=c_j{\delta }_{jl}P$. For $c_j>0$, $V_j=F_{j}P/\sqrt{c_j}$ is an isometry of the code into an error-image subspace, and these subspaces are orthogonal. Measuring their projectors and applying $V_j^{†}$ recovers the logical state. Complete the operation arbitrarily on the orthogonal complement to obtain a quantum channel. This construction corrects every noise map whose Kraus operators lie in the specified error span, including coherent superpositions of error operators.

The guaranteed radius is the largest integer $t$ for which all unknown-location Pauli operators of weight at most $t$ can be corrected together. Pairwise products have weight at most $2t$, so $2t<d$ suffices by the Knill--Laflamme condition. Conversely, split a minimum-weight undetectable Pauli operator between two subsets of its support. If $d\le 2t$, this gives two errors of weight at most $t$ whose pairwise product violates that condition. Consequently $d$ is either $2t+1$ or $2t+2$; parity cannot be recovered from $t$ alone.

Split the support of a Pauli operator of weight at most $2t$ into two sets of size at most $t$. It is, up to a scalar phase, $E_a^{†}{E}_b$ for two errors in the correctable family. The Knill--Laflamme condition makes its compression to the code scalar, which is quantum error detection. Expansion in the Pauli basis extends the assertion to every operator supported on at most $2t$ qubits. The number $t$ counts affected qubits, not the cardinality of an arbitrary selected family of errors.

If a common recovery quantum channel with Kraus operators $R_{\mu }$ restores every pure code state after each error $E_a$, then each vector $R_{\mu }{E}_a|\psi ⟩$ is parallel to $|\psi ⟩$. Linearity on basis vectors and their pairwise superpositions forces $R_{\mu }{E}_{a}P=c_{\mu a}P$, with the scalar independent of the logical state. Insert ${\sum }_{\mu }{R}_{\mu }^{†}{R}_{\mu }=I$ between two error operators to obtain the displayed Knill--Laflamme condition. This proves necessity without presuming an orthogonal syndrome description of recovery.

For binary linear codes $C\subseteq C^{\prime }$, the coset superpositions of the CSS code have $X$ checks labelled by $C$ and $Z$ checks by $(C^{\prime }{)}^{\perp }$. A bit-error pattern $a$ gives the classical syndrome for $C^{\prime }$, and a phase-error pattern $b$ gives the syndrome for the dual code $C^{\perp }$. Errors with $2t_X<{\min }_{a\in C^{\prime }\setminus C}\mathrm{wt}(a)$ and $2t_Z<{\min }_{b\in C^{\perp }\setminus (C^{\prime }{)}^{\perp }}\mathrm{wt}(b)$ are jointly correctable. Every pairwise Pauli-error product either anticommutes with a check, giving zero code compression, or its low-weight components belong to the stabilizer and give scalar compression. Thus the Knill--Laflamme condition covers coherent superpositions and quantum channels as well as definite bit and phase errors.

For a specified correctable set of distinct Pauli operators modulo phase, a nondegenerate code has mutually orthogonal error images $E\mathcal{X}$. Equivalently, the matrix in the Knill--Laflamme condition is diagonal for that Pauli error set. Each error therefore requires a separate syndrome subspace of dimension equal to the logical code dimension. Degenerate codes can have distinct errors with the same action on the code and do not satisfy this orthogonality counting argument.

Use binary linear codes $C\subseteq C^{\prime }\subseteq {\mathbb{F}}_2^N$, with dimensions $k,k^{\prime }$. For each coset $u+C$ in $C^{\prime }/C$, defineRepresentatives of one coset give the same vector, and distinct cosets have disjoint computational supports, so these vectors are orthonormal. Their span is the CSS code $\mathcal{X}$, encoding $\boxed{k^{\prime }-k\text{ logical qubits in }N\text{ physical qubits}}$.

For $a,b\in {\mathbb{F}}_2^N$, write $X^a={⨂}_j{X}_j^{a_j}$ and $Z^b={⨂}_j{Z}_j^{b_j}$. The code is stabilized by $X^c$ for $c\in C$, because it permutes the sum, and by $Z^z$ for $z\in (C^{\prime }{)}^{\perp }$, because $z\cdot (u+c)=0$. These Pauli operators commute: $c\cdot z=0$. There are $k+N-k^{\prime }$ independent stabilizer generators, so their common positive eigenspace has dimension $2^{N-(k+N-k^{\prime })}=2^{k^{\prime }-k}$; it is exactly the span above.

The commuting check measurements separate the two types of error. A bit error $X^a$ changes the signs of the $Z$ checks by $(-1{)}^{z\cdot a}$, giving the ordinary syndrome of $a$ for $C^{\prime }$. A phase error $Z^b$ changes the $X$ checks by $(-1{)}^{c\cdot b}$, giving the syndrome of $b$ for the dual code $C^{\perp }$. If $C^{\prime }$ corrects $t_X$ bit errors and $C^{\perp }$ corrects $t_Z$ bit errors, these checks identify the respective patterns, and inverse Pauli operations recover the state without revealing the logical coset. This is the nested-code CSS syndrome recovery procedure.

The sharper distances account for harmless stabilizer errors. A Pauli $X^a{Z}^b$ commutes with every check precisely when $a\in C^{\prime }$ and $b\in C^{\perp }$. Among these, it acts as a stabilizer, up to a phase, precisely when $a\in C$ and $b\in (C^{\prime }{)}^{\perp }$. To justify the latter assertion, $X^a$ with $a\in C^{\prime }\setminus C$ permutes distinct logical cosets, while $Z^b$ with $b\in C^{\perp }\setminus (C^{\prime }{)}^{\perp }$ has unequal signs on two such cosets. Neither can act as a scalar, and a combined operator has the same nontrivial permutation or phase distinction. For positive logical dimension setThe quantum code distance is $\boxed{d=\min (d_X,d_Z)}$: a nontrivial logical Pauli has at least one nonstabilizer component of weight at least the corresponding distance, while a pure $X$ or pure $Z$ logical operator attains the minimum. The weight of $X^a{Z}^b$ counts the union of its supports, so this argument also includes $Y$ errors.

Here is the correction proof for coherent errors, not only a classical decoding argument. Let $P$ be the code projector and let $E,F$ have bit-component weights at most $t_X$ and phase-component weights at most $t_Z$. If $2t_X<d_X$ and $2t_Z<d_Z$, the corresponding components of $E^{†}F$ have weights below $d_X,d_Z$. If this product anticommutes with a stabilizer $S$, then $P(E^{†}F)P=-P(E^{†}F)P=0$, using $SP=P$. If it commutes with all stabilizers, the weight bounds force its two components into $C$ and $(C^{\prime }{)}^{\perp }$, so its code compression is a scalar multiple of $P$. Thus the Knill--Laflamme condition holds for the entire error family.

To see directly why this gives a common recovery, diagonalize its positive Gram matrix $c_{EF}$ and form the corresponding error combinations $F_j$. Their restrictions obey $P{F}_j^{†}{F}_{l}P=c_j{\delta }_{jl}P$. For $c_j>0$, $F_{j}P/\sqrt{c_j}$ is an isometry onto a syndrome subspace, and the different images are orthogonal. Measure these subspaces and apply the inverse isometry; zero-$c_j$ combinations annihilate the code. This recovers every quantum channel whose Kraus operators lie in the error span. Arbitrary operators supported on at most $t$ qubits expand in Pauli operators with the same support. Consequently the CSS code corrects all errors on up to $\boxed{t=\lfloor (d-1)/2\rfloor }$ qubits, and more generally the asymmetric family just described. The sufficient classical bound is obtained by replacing $d_X,d_Z$ by the minimum distances of $C^{\prime }$ and $C^{\perp }$, respectively; degeneracy can improve it.

Let $P$ be the orthogonal projector onto the quantum code $\mathcal{X}$, and choose an orthonormal basis $|i_L⟩$ for it. The necessary and sufficient Knill--Laflamme condition is that one matrix $C$, independent of the logical labels, satisfiesEquivalently, $⟨i_L|E_a^{†}{E}_b|j_L⟩=C_{ab}{\delta }_{ij}$. This makes the information in the error label independent of the encoded quantum state. It applies to the whole linear span of the errors, and hence to every noise quantum channel with Kraus operators in that span.

Here is a proof of both directions. For necessity of the Knill-Laflamme condition, let $R_{\mu }$ be Kraus operators of a common recovery, so ${\sum }_{\mu }{R}_{\mu }^{†}{R}_{\mu }=I$. Since recovery after $E_a$ must return the pure input state, every vector $R_{\mu }{E}_a|\psi ⟩$ is parallel to $|\psi ⟩$. A linear operator on the code which sends every vector to a multiple of itself is scalar: apply it to two basis vectors and their sum to force the two multipliers to agree. Therefore $R_{\mu }{E}_{a}P=c_{\mu a}P$ with no dependence on $|\psi ⟩$. It follows thatThis proves necessity without assuming in advance that the physical errors have orthogonal syndromes.

For sufficiency, $C$ is positive semidefinite: for any normalized code state and coefficients $v_a$, $v^{†}Cv=\Vert {\sum }_a{v}_a{E}_a|\psi ⟩{\Vert }^2\ge 0$. Diagonalize $C$ by a unitary change of the error basis to get operators $F_j$ with $P{F}_j^{†}{F}_{l}P=c_j{\delta }_{jl}P$. If $c_j>0$, $V_j=F_{j}P/\sqrt{c_j}$ is a linear isometry from the code to an error-image subspace, and distinct such images are orthogonal. If $c_j=0$, then $F_{j}P=0$. A projective measurement of these image subspaces followed by $V_j^{†}$ recovers every logical state. Complete the recovery on the unused orthogonal complement in any trace-preserving manner. For a coherent error ${\sum }_j{v}_j{F}_j$, the measurement branch $j$ contains $v_j\sqrt{c_j}|\psi ⟩$; the branch probability is independent of the logical state, and discarding the syndrome leaves the original state. This is constructive recovery from the Knill-Laflamme condition.

For the usual family of distinct unitary Pauli errors modulo scalar phase, nondegenerate quantum code correction means that different physical errors have orthogonal image subspaces. The precise condition isFor nonunitary errors, replace the unit diagonal by positive norm factors. In an arbitrary error basis the Gram matrix need not initially be diagonal; its positive-eigenvalue modes give the independent syndrome spaces just constructed. A kernel of $C$ exhibits a linear combination of errors acting as zero on the code. In particular two distinct physical errors with the same action on the code cannot be distinguished and give degenerate correction, as in part (c).

Here the number of errors means the number of affected physical qubits: assume that all errors supported on at most $t$ qubits are jointly correctable. It does not mean the cardinality of an arbitrary selected error list. Let $F$ be any Pauli operator of weight at most $2t$. Split its support into disjoint sets $A,B$, each of size at most $t$, and write $F=F_A{F}_B$. Each Pauli factor is Hermitian, so take $E_a=F_A$, $E_b=F_B$ to get $F=E_a^{†}{E}_b$, up to an irrelevant scalar phase if different Pauli representatives are used. The Knill--Laflamme condition givesThis is precisely quantum error detection: a projective measurement with outcomes $P,I-P$ either detects departure from the code or leaves the accepted logical state unchanged up to a scalar. Some errors can be harmless scalars on the code, particularly for degenerate correction; detection is not required to flag such an error with certainty.

Any linear operator supported on at most $2t$ qubits is a linear combination of Pauli operators on those qubits, so its code compression is scalar by linearity. ThusThis is correction implies detection at twice the weight. The premise about all locations and all error types is essential: merely correcting one selected operator gives no universal statement about every operator of twice its weight.

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.

The Pauli group includes scalar phases $\mathcal{Z}=\{\pm I,\pm iI\}$. For a nonzero stabilizer code, its Abelian subgroup must satisfy $-I\notin S$. Otherwise a common positive eigenvector would satisfy $-|\psi ⟩=|\psi ⟩$ and vanish; for example $S=\{I,-I\}$ is Abelian but yields no nonzero stabilizer code. We impose this standard admissibility condition.

Every element of such a stabilizer group is Hermitian and squares to $I$: an imaginary-phase Pauli with square $-I$ is excluded. The associated stabilizer code and its orthogonal projector areThe group multiplication proves $P^2=P$, Hermiticity gives $P^{†}=P$, and its range is exactly the common positive eigenspace. If $S$ has $r$ independent generators, $|S|=2^r$. Every nonidentity element has trace zero, while $\mathrm{tr}I=2^n$, soThus it encodes $k=n-r$ logical qubits.

For the symplectic representation of a stabilizer code, label $i^t{X}^a{Z}^b$ by $(a,b)\in {\mathbb{F}}_2^{2n}$, ignoring scalar phase. Products add labels, andThis is the nondegenerate alternating form $\omega ((a,b),(a^{\prime },b^{\prime }))=a\cdot b^{\prime }+b\cdot a^{\prime }$ on the binary symplectic space of Pauli labels. The image $L$ of $S$ is an r-dimensional isotropic subspace of a binary symplectic space, since the generators commute and no nontrivial scalar lies in $S$. Consequently $L\subseteq L^{\perp }$ and $r\le n$. A binary generator matrix $(A\mid B)$ satisfies $A{B}^T+B{A}^T=0$. Conversely an isotropic subspace can be lifted by choosing commuting Hermitian generators with independent labels; their products cannot equal $-I$, and the orthogonal projector formula supplies the stabilizer code. The labels of the centralizer of a stabilizer group are $L^{\perp }$, with nontrivial logical actions represented by $L^{\perp }\setminus L$.

For an example, the three-qubit bit-flip repetition code has $S=⟨Z_1{Z}_2,Z_2{Z}_3⟩$ and ${\mathcal{C}}_S=\mathrm{span}\{|000⟩,|111⟩\}$. Its two binary rows have zero X part and Z parts $110,011$. The errors $I,X_1,X_2,X_3$ have respective error syndromes $00,10,11,01$, so all single bit flips can be corrected. This is not a stabilizer code correcting every single-qubit error: $Z_1$ acts as a nontrivial logical phase error.

Let $C(S)$ denote the Pauli centralizer. The exact Pauli error criterion for a stabilizer code isEquivalently, no difference of error labels lies in $L^{\perp }\setminus L$. The scalar phases in $\mathcal{Z}S$ are essential: an error product $-I$ is harmless even though it is not in $S$.

We prove the criterion. For $T=E_a^{†}{E}_b$ outside $C(S)$, some $s\in S$ anticommutes with $T$. Since $sP=Ps=P$, we have $PTP=PsTsP=-PTP$, hence $PTP=0$. If $T=\lambda s\in \mathcal{Z}S$, then $PTP=\lambda P$. If $T\in C(S)\setminus \mathcal{Z}S$, it restricts to a unitary operator on the stabilizer code, butno $sT$ is scalar. A scalar restriction would have scalar coefficient zero by this trace equation, contradicting unitarity. Thus this third case is not scalar.

To justify why scalar compressions are exactly what correction requires, suppose one recovery corrects every $E_a$. Dilate that recovery to an isometry $W$ including its auxiliary system. Correct recovery of every pure stabilizer code state gives $W{E}_a|\psi ⟩=|\psi ⟩\otimes |{\eta }_a⟩$. The auxiliary state is independent of $\psi$: linearity on basis states and their superpositions forces their auxiliary vectors to coincide. Preservation of inner products then giveswhich is the Knill--Laflamme condition $P{E}_a^{†}{E}_{b}P=c_{ab}P$. The three cases above prove necessity of the boxed criterion.

For sufficiency, put errors in the same class when $E_a^{†}{E}_b\in \mathcal{Z}S$. They act identically on the stabilizer code up to scalar phase, so give the same error-image subspace. Under the criterion, different classes give mutually orthogonal subspaces $E_a{\mathcal{C}}_S$, because their cross-compressions vanish. Measure which of these subspaces is occupied and apply the inverse of a representative error. This returns every stabilizer code state unchanged; extend the recovery on the orthogonal complement by preparing any fixed stabilizer code state. Linearity also corrects any valid noise channel whose Kraus operators are linear combinations of the specified errors: within each syndrome all amplitudes multiply the same logical state, and trace preservation normalizes the recovered state. This proves sufficiency, including degenerate error classes.

Over a finite field ${\mathbb{F}}_q$, a linear code of length $N$ and dimension $k$ is a $k$-dimensional subspace $C\subseteq {\mathbb{F}}_q^N$. A full-row-rank generator matrix $G\in {\mathbb{F}}_q^{k\times N}$ gives $C=\{mG:m\in {\mathbb{F}}_q^k\}$, using row-vector messages. A full-row-rank parity-check matrix $H\in {\mathbb{F}}_q^{(N-k)\times N}$ gives $C=\{x:H{x}^T=0\}$. The dual code is $C^{\perp }=\{y:x\cdot y=0\text{ for all }x\in C\}$, of dimension $N-k$. Thus the rows of $H$ span $C^{\perp }$, andConversely the rank conditions and $H{G}^T=0$ imply that the row space of $G$ equals the kernel of $H$, by inclusion and equality of dimensions.

For a CSS code, specialize to binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, of dimensions $k_2,k_1$. Define orthonormal encoded statesDifferent cosets have disjoint computational-basis support. Their span has dimension $2^{k_1-k_2}$, so it encodes $K=k_1-k_2$ logical qubits. For binary vectors write $X(u)={⨂}_j{X}_j^{u_j}$ and $Z(v)={⨂}_j{Z}_j^{v_j}$. The stabilizer generators are $X(u)$ for a basis of $C_2$, and $Z(v)$ for a basis of $C_1^{\perp }$. They fix each encoded state: the former permute its coset terms and the latter contribute phases $(-1{)}^{v\cdot (x+y)}=1$. Their commutation relation is $X(u)Z(v)=(-1{)}^{u\cdot v}Z(v)X(u)$, so the classical dual inclusion $C_1^{\perp }\subseteq C_2^{\perp }$ makes them commute. There are $k_2+N-k_1=N-K$ independent checks, giving precisely this encoded space.

For a Pauli error $X(e)Z(f)$, the Z checks give bit-error syndrome $H_1{e}^T$, where $H_1$ checks $C_1$, and the X checks give phase-error syndrome $G_2{f}^T$, where $G_2$ generates $C_2$ and hence checks $C_2^{\perp }$. Classical decoders therefore correct up to $t_X$ bit flips and $t_Z$ phase flips if $d(C_1)>2t_X$ and $d(C_2^{\perp })>2t_Z$. A Y error has both components; it is not omitted from this correction scheme.

For the precise quantum code distance, harmless stabilizer errors must be excluded. A pure-X error preserves the code exactly when $e\in C_1$, and is a stabilizer when $e\in C_2$; a pure-Z error preserves it when $f\in C_2^{\perp }$, and is a stabilizer when $f\in C_1^{\perp }$. Consequently, for $K>0$,A mixed Pauli error has weight equal to the size of the union of its X and Z supports. If it is a nontrivial logical operator, at least one component is nontrivial, so its weight is at least $\min (d_X,d_Z)$; pure-X or pure-Z operators attain that minimum. Thus $t=\lfloor (d-1)/2\rfloor$ arbitrary-qubit errors are correctable: products of two such Pauli errors have weight below $d$ and act scalarly on the code, or take it to an orthogonal syndrome sector. This is the Knill--Laflamme condition. Expanding arbitrary errors in the Pauli basis extends correction to their coherent linear span.

An explicit example is the Steane code. Take $C_1$ to be the binary Hamming code withThe distinct nonzero columns show that $C_1$ has no weight-one or weight-two word, while three dependent columns give a weight-three word. Hence its classical distance is three. Direct multiplication gives $H{H}^T=0$, proving $C_2\subseteq C_1$. Every nonzero word of $C_2$ has weight four, so the logical X and Z distances are both three. Its six stabilizer checks are the X and Z strings given by the three rows of $H$. A logical basis is the uniform superposition over $C_2$ and over $1+C_2$, since $1=(1,\dots ,1)\in C_1\setminus C_2$. The resulting $[[7,1,3]]$ CSS code corrects every single-qubit error.

Let $D={\mathcal{C}}_{\mathrm{ev}}$, and write ${\mathcal{C}}_{\mathrm{odd}}=t+D$ for any odd-weight word $t\in {\mathcal{C}}_H$. The parity functional on the four-dimensional binary linear code ${\mathcal{C}}_H$ is nonzero, so its kernel $D$ has dimension three and its other fibre is the coset $t+D$. For example $t=(1,\dots ,1)$ belongs to the standard length-seven Hamming code and has odd Hamming weight. Denote the two logical basis states by $|{\psi }_0⟩$ and $|{\psi }_1⟩$, corresponding to these two cosets. The eight computational orthonormal basis vectors in each sum are distinct, so both logical states have norm one; their disjoint supports make them orthogonal.

For a binary vector $w\in {\mathbb{F}}_2^7$, define the product of Pauli Z gateswhere the dot product is computed modulo two. The key diagonal overlap, with $t_0=0$ and $t_1=t$, isIf $w\in D^{\perp }$, every summand is one. If $w\notin D^{\perp }$, choose $x_0\in D$ with $w\cdot x_0=1$. Translation $x\mapsto x+x_0$ permutes $D$ and negates every summand. The sum must then be zero. ThusOff-diagonal logical overlaps vanish for every $w$:because a diagonal Pauli operator cannot move a computational basis word from one coset to the disjoint other coset.

The possible errors are $E_0=I$ and $E_j=Z(e_j)$ for $j=1,\dots ,7$. Set $e_0=0$. Each phase flip is its own adjoint and inverse, soIf $i\ne j$, the vector $e_i+e_j$ is nonzero and has Hamming weight one or two. By the given dual code identity $D^{\perp }={\mathcal{C}}_H$ and the minimum Hamming distance three of the Hamming code, it cannot belong to $D^{\perp }$. Hence all its diagonal logical overlaps vanish. If $i=j$, the product is the identity and its logical overlaps are ${\delta }_{ab}$. Combining both cases givesThis proves the Knill--Laflamme condition with an identity error-overlap matrix, not merely a possibly degenerate scalar matrix. In particular the eight two-dimensional error subspaces $E_i{\mathcal{X}}_{\mathrm{Steane}}$ are mutually orthogonal. This is precisely nondegenerate phase-flip correction in the Steane code.

To exhibit recovery rather than only the criterion, let $P$ be the orthogonal projector onto the code and $P_i=E_{i}P{E}_i^{†}$. The projective measurement consisting of these eight mutually orthogonal projectors, completed by $I-{\sum }_i{P}_i$, determines which error occurred. For an arbitrary encoded pure state $|\chi ⟩=\alpha |{\psi }_0⟩+\beta |{\psi }_1⟩$ affected by $E_j$, outcome $j$ occurs with certainty and leaves $E_j|\chi ⟩$ unchanged. Applying $E_j$ again recovers $|\chi ⟩$. The outcome gives the error syndrome and does not reveal $\alpha$ or $\beta$, so recovery preserves logical quantum superpositions.

An equivalent explicit error syndrome uses three commuting X-type stabilizer generators. Choose a parity-check matrix for ${\mathcal{C}}_H$ with the seven different nonzero binary columns:Its rows span ${\mathcal{C}}_H^{\perp }=D$. For a row $h_l$, the operator $X(h_l)={⨂}_j{X}_j^{(h_l{)}_j}$ permutes each of $D$ and $t+D$, and therefore has eigenvalue $+1$ on both logical states. A phase flip at position $j$ changes its eigenvalue to $(-1{)}^{H_{lj}}$, since $X(h_l)Z_j=(-1{)}^{H_{lj}}{Z}_{j}X(h_l)$. Measuring the three commuting stabilizer generators gives the $j$th column of $H$ as a binary syndrome; no error gives the zero column. All eight outcomes are different, and applying the identified $Z_j$ restores the code state. Measuring these stabilizer generators never distinguishes the two logical states.

Finally, if a noise Kraus operator is a coherent linear combination $F={\sum }_j{c}_j{E}_j$, the same syndrome measurement separates its mutually orthogonal components $c_j{E}_j|\chi ⟩$. Conditional recovery returns $|\chi ⟩$ in every nonzero branch. Linearity then also corrects any quantum channel whose Kraus operators lie in this span. The argument therefore corrects arbitrary unknown single-site phase flips nondegenerately, including coherent phase-error amplitudes, rather than only a known error on a basis codeword.

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.