Chapter 14

Error correction without reading the logical state

Measuring a qubit to see whether an error has occurred would disturb the amplitudes it holds, and no-cloning rules out keeping a backup copy. How can an error be detected and undone without learning the encoded state?

Before you start: Parity measurements that keep a superposition (Chapter 2); controlled-NOT and the identity $HZH=X$ (Chapter 4); encoding is not copying (Chapter 6). The last section uses channels (Chapter 13). Notation guide.

Encode amplitudes rather than independent copies

The three-qubit repetition code has logical basis states $|0_L\rangle=|000\rangle$ and $|1_L\rangle=|111\rangle$. Two CNOTs from an input qubit to two blank qubits encode

This is not three copies of the input. Its information is stored jointly. A bit flip on the first qubit gives $X_1|\psi_L\rangle=\alpha|100\rangle+\beta|011\rangle$. We want to locate the flip without determining whether the logical component was zero or one.

Read parities with two commuting checks

Choose $S_1=Z_1Z_2$ and $S_2=Z_2Z_3$. They commute, square to $I$, and have eigenvalue $+1$ throughout the code space, the two-dimensional subspace spanned by $|0_L\rangle=|000\rangle$ and $|1_L\rangle=|111\rangle$ in which the logical qubit lives. The ordered pair of check outcomes is called the syndrome. It records which joint eigenspace the state occupies. To derive the table, suppose a check $S$ fixes every code state: $S|\psi_L\rangle=|\psi_L\rangle$. If an error $E$ commutes with that check, then

$$S(E|\psi_L\rangle)=ES|\psi_L\rangle=E|\psi_L\rangle,$$

so the check still returns $+1$. If the error anticommutes with it, $SE=-ES$, and instead

$$S(E|\psi_L\rangle)=-ES|\psi_L\rangle=-E|\psi_L\rangle,$$

so the outcome becomes $-1$. These are statements about the entire logical superposition, not just one basis vector.

For $E=X_1$, check $Z_1Z_2$ has one overlapping site where $Z$ and $X$ anticommute. Moving $X_1$ through that check introduces one minus sign. Check $Z_2Z_3$ acts on different sites and introduces none. Thus $X_1$ has syndrome $(-1,+1)$. Error $X_2$ anticommutes with both checks, giving $(-1,-1)$; $X_3$ only anticommutes with the second, giving $(+1,-1)$. This produces the syndromes in the figure.

The syndrome table with the corrupted states written out. Each check is read as a bit, 0 for eigenvalue $+1$ and 1 for $-1$: the parity of qubits 1 and 2, and of qubits 2 and 3. In every row the two terms, the one carrying $\alpha$ and the one carrying $\beta$, give the same bits, so a reading reveals which qubit flipped and nothing about $\alpha$ or $\beta$. Applying $X$ to that qubit restores $\alpha|000\rangle+\beta|111\rangle$.

For example, both $|100\rangle$ and $|011\rangle$ have syndrome $(-1,+1)$. Reading it cannot distinguish their amplitudes. Applying $X_1$ then restores $|\psi_L\rangle$.

To measure $Z_1Z_2$, prepare an ancilla $|0\rangle$, apply CNOTs from data qubits 1 and 2 to it, then measure the ancilla in the computational basis. Its bit is $q_1\oplus q_2$: zero denotes eigenvalue $+1$, one denotes $-1$. The ancilla records only parity. This circuit assumes ideal gates and readout; faulty syndrome extraction is a separate fault-tolerance problem.

A coherent small error is corrected too

Suppose the first physical qubit undergoes $e^{-i\epsilon X_1/2}=cI-isX_1$, with $c=\cos(\epsilon/2)$ and $s=\sin(\epsilon/2)$. The encoded state becomes

$$c|\psi_L\rangle-isX_1|\psi_L\rangle.$$

The two terms occupy orthogonal syndrome subspaces. Measuring the checks selects the no-error branch with probability $c^2$ or the $X_1$ branch with probability $s^2$, independently of $\alpha,\beta$. The corresponding recovery restores the original state in either case, up to an irrelevant branch phase. The rotation angle need not be estimated.

This conclusion depends on the error set the code corrects. A $Z_1$ error stays in the code space and changes $\alpha|000\rangle+\beta|111\rangle$ to $\alpha|000\rangle-\beta|111\rangle$. Both parity checks still return $+1$. The three-qubit repetition code does not correct arbitrary one-qubit errors.

Protect both bit and phase information

Define $|g_\pm\rangle=(|000\rangle\pm|111\rangle)/\sqrt2$. These are three-qubit Greenberger–Horne–Zeilinger (GHZ) states: coherent superpositions of all-zero and all-one strings, with a specified relative sign. Shor's nine-qubit code uses

$$|0_L\rangle=|g_+\rangle^{\otimes3},\qquad |1_L\rangle=|g_-\rangle^{\otimes3}.$$

Within each block, adjacent $ZZ$ checks diagnose bit flips. Across blocks, the two checks $X_1X_2X_3X_4X_5X_6$ and $X_4X_5X_6X_7X_8X_9$ compare the signs of the three GHZ blocks. A $Z$ on any qubit flips the sign of its block, so these outer checks locate the affected block. Since $Y=iXZ$, correcting both components also handles $Y$ errors.

There is a crucial degeneracy: $Z_1,Z_2,Z_3$ act identically on the code space. The syndrome cannot distinguish these three errors and does not need to. Applying $Z$ to any qubit in the identified block restores its sign. A syndrome identifies what recovery is needed; it need not identify the unique microscopic error.

The general recovery condition

Let $P$ project onto a code, and let $\{E_a\}$ be the errors to correct. The Knill–Laflamme criterion states that perfect recovery is possible exactly when

$$PE_a^\dagger E_bP=c_{ab}P$$

for scalars $c_{ab}$. In a logical orthonormal basis this says $\langle i_L|E_a^\dagger E_b|j_L\rangle=c_{ab}\delta_{ij}$.

Checking the criterion on the repetition code

Check it on the repetition code with the error set $\{I,X_1,X_2,X_3\}$: for $a\ne b$ the product $E_a^\dagger E_b$ flips one or two qubits, so it maps $|000\rangle$ and $|111\rangle$ to strings outside the code space and every matrix element vanishes, giving $c_{ab}=0$; for $a=b$ the product is $I$, giving $c_{aa}=1$ with no dependence on $i,j$ beyond $\delta_{ij}$. The criterion holds with $c_{ab}=\delta_{ab}$, which is the orthogonal-syndrome case.

Error overlaps must not distinguish or mix logical basis labels in an input-dependent way. Orthogonal syndrome spaces are one way to satisfy the condition, but degenerate errors can satisfy it too. The full necessity-and-sufficiency proof is a cited theorem; our repetition-code recovery above is explicit.

If a code corrects an error basis, the same recovery corrects its linear span. Every operator on one qubit expands as $aI+bX+cY+dZ$, so a code satisfying the criterion for all single-site Pauli errors corrects arbitrary noise supported on one site, including coupling to an environment. This does not imply that a code corrects arbitrarily many simultaneous errors.

Where this leaves us

An error is detected without reading the encoded state by measuring only parities, $Z_1Z_2$ and $Z_2Z_3$. Every code state gives $+1$ for both, whatever $\alpha$ and $\beta$ are, so the readings carry no information about the amplitudes; after a single flip, both terms of the corrupted state give the same readings, which point to the flipped qubit. Applying $X$ there restores $\alpha|000\rangle+\beta|111\rangle$ exactly. Because recovery works on an error basis, it also corrects a small coherent rotation. The limits stay part of the answer: the repetition code misses phase errors, the Shor code handles any single-qubit error but not arbitrary two-qubit errors, and faulty checks need fault-tolerant constructions.

The book has now followed a qubit through preparation, measurement, gates, entanglement, communication, algorithms and noise. The last chapter asks the question underneath the communication protocols: how much classical information one qubit can carry, and what shared entanglement adds.

Problems

1. In the three-qubit code, apply $X_1X_2$ and then the recovery indicated by its syndrome. What logical operation remains?

Worked answer

For error $X_1X_2$, commuting it through $Z_1Z_2$ produces two minus signs, which cancel. Commuting it through $Z_2Z_3$ produces only one minus sign. The syndrome is therefore $(+1,-1)$, the same as for the single error $X_3$.

$$\alpha|000\rangle+\beta|111\rangle\xrightarrow{X_1X_2}\alpha|110\rangle+\beta|001\rangle\xrightarrow{X_3}\alpha|111\rangle+\beta|000\rangle.$$

The prescribed recovery leaves the amplitudes attached to the opposite logical basis states: a logical $X$. Two different error patterns share this syndrome, and the code’s single-flip assumption selects the wrong recovery for the two-flip case.

2. Each physical qubit flips independently with probability $p$, and recovery is ideal. What is the logical error probability?

Worked answer

Under the assumed independent error model, a specified pattern with two flips has probability $p^2(1-p)$. There are three such patterns, according to which qubit did not flip. The all-three pattern has probability $p^3$. Zero and one flip are corrected, so

$$p_L=3p^2(1-p)+p^3=3p^2-2p^3.$$

For instance, $p=0.01$ gives $p_L=0.000298$, about three errors per ten thousand encoded trials under these assumptions. The leading term is proportional to $p^2$ because one error is correctable. Correlated errors or faulty recovery change this calculation and must be modelled separately.

References and further reading

Nielsen & Chuang, §10.1–10.3 (repetition, Shor code, recovery conditions, degeneracy), and §10.6 (fault tolerance). For the general criterion, see Knill & Laflamme, A Theory of Quantum Error-Correcting Codes.