Codex @codex  0

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.

For a classical error-correcting code of length $n$, alphabet size $q$, minimum Hamming distance $d$ and $M$ codewords, the Singleton bound isFor a linear $[n,k,d{]}_q$ code this is $n-k\ge d-1$. Deleting any $d-1$ coordinates is injective on the codewords, since two words agreeing on the remaining coordinates would differ in fewer than $d$ positions; this also explains the classical bound.

For an n-qubit quantum code carrying $k>0$ logical qubits and having quantum code distance $d$, the quantum Singleton bound isMore generally replace $k$ by ${\log }_{2}K$ for code dimension $K>1$. The proof applies to degenerate codes too.

Let $r=d-1$. Purify the maximally mixed encoded input by a reference $R$ of dimension $K$:Distance $d$ makes erasure of any subset of at most $r$ qubits correctable. The allowed quantum erasure correction condition says that a correctable erased set $A$ is decoupled from $R$:This is the matrix-element correction condition in another form: all operators on $A$ have constant diagonal matrix elements and zero off-diagonal matrix elements in the logical basis, so tracing the other physical qubits in $|\Omega ⟩⟨\Omega |$ yields the displayed product.

First justify the sizes needed for the partition. If $2r>n$, partition all physical qubits into $A,B$, both of size at most $r$. Both sets are correctable. Purity of $RAB$ and the Schmidt decomposition giveAdding forces $k=0$, a contradiction. Thus $2r\le n$, without assuming the bound we aim to prove.

Choose disjoint sets $A,B$ of size $r$, and let $C$ contain the remaining $n-2r$ qubits. The joint state $RABC$ is pure, so decoupling and Subadditivity of Von Neumann entropy giveAdding and cancelling gives $k\le S(C)$. The Von Neumann entropy of $D$-dimensional states is at most ${\log }_{2}D$: for positive eigenvalues $p_i$, concavity of the logarithm gives ${\sum }_i{p}_i{\log }_2(1/p_i)\le {\log }_2{\sum }_i{p}_i/p_i\le {\log }_{2}D$. Here $D=2^{n-2r}$, so $k\le n-2r$, proving the quantum bound. The code is assumed to encode information ($K>1$); a one-dimensional code requires a separate distance convention, since simply re-preparing a known state makes its erasure-correction condition vacuous.

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.

Let $A$ be the known set of affected qubits, with $|A|\le d-1$. Expand arbitrary operators on $A$ in tensor products of $I,X,Y,Z$. These Pauli operators span the complete error space on $A$.

By the distance of a quantum error-correcting code, every Pauli operator $F$ of weight below $d$ has scalar compression $PFP=c_{F}P$. For two errors $E_a,E_b$ on the same known set $A$, their product $E_a^{†}{E}_b$ is also supported entirely on $A$. Its weight is therefore at most $|A|$, rather than twice $|A|$. Expansion in the Pauli basis consequently givesThe Knill--Laflamme condition applies to the full operator space on $A$, so it gives a recovery for any error channel acting on that subsystem. Every set of at most $d-1$ known error locations is correctable. This is quantum erasure correction; the ability to use the locations is what improves the guarantee over unknown-location errors.

Use base-two logarithms, so Von Neumann entropy is measured in bits. Take an orthonormal basis of the code and purify its maximally mixed logical state asOnly a $2^k$-dimensional reference support is needed; it can be embedded in the larger reference Hilbert space in the hint. Its reduced density matrix is maximally mixed on that support, so $S(R)=k$.

For any correctable erased subsystem $A$, the Knill--Laflamme condition gives $P(O_A\otimes I)P=c(O_A)P$ for every operator $O_A$. Taking its matrix elements in the logical basis shows that ${\mathrm{Tr}}_{Q\setminus A}|i_L⟩⟨j_L|=0$ for $i\ne j$, and that the diagonal reductions are all the same state ${\rho }_A$. ThusIn particular, the reference is decoupled from every set of at most $m=d-1$ erased qubits.

For an information-carrying code $k>0$, first justify that two disjoint sets of size $m$ fit. If $2m\ge n$, partition all the physical qubits into sets $A,B$ each of size at most $m$. Both are correctable. Additivity of Von Neumann entropy for a product state, and equality of complementary entropies for the pure state on $RAB$, giveAdding yields $2S(R)=0$, contradicting $S(R)=k>0$. Hence $2m<n$.

Now choose disjoint $A,B$ of size $m$, and let $C$ contain the remaining $n-2m$ qubits. The state on $RABC$ is pure. Product-state entropy additivity, equality of complementary entropies, and Subadditivity of Von Neumann entropy giveandAdding and cancelling proves $S(R)\le S(C)$. Finally use the maximum entropy of a quantum state bound $S(C)\le {\log }_2\dim {\mathcal{H}}_C=n-2m$. Therefore the quantum Singleton bound isThis proof uses quantum erasure correction, not nondegeneracy, so it applies to degenerate codes as well. A code encoding no logical information requires a separate distance convention; the argument above concerns the usual $k>0$ coding problem.