Starting point: Joint states, CNOT, measurement with ancillas and no-cloning; code spaces and syndrome measurements are developed through circuits.
Keep in view: Encode a qubit into a three-qubit code and correct a single bit flip.
Noise destroys quantum information by letting an environment keep a record: dephasing turned a Bell pair into a classical mixture, and no local operation could undo it. Classically we protected bits against noise by repeating them, sending 000 for 0 and 111 for 1.
Two obstacles stand in the way of doing the same for a qubit. We cannot copy an unknown state, and we cannot read it to check for errors without disturbing it. Can redundancy still exist? We encode one qubit into a joint state of three, which is not three copies. A bit flip then moves the state into a subspace that tells us where the error is but nothing about the encoded amplitudes. Measuring parities finds that subspace, and a conditional flip repairs it. Asking which errors this works for leads to a general condition, and the same condition shows what the three-qubit code cannot do.
14.1 Encoding
An unknown qubit cannot be copied into three independent qubits. Can it be spread over three qubits in some other way that still allows errors to be found? We build the encoding with two CNOTs and check that no single qubit holds a copy. Then we apply errors to the encoded state and see that each bit flip lands in its own orthogonal subspace.
Imitate classical repetition. Take \(\alpha\ket0+\beta\ket1\) and two ancillas in \(\ket0\), and apply a CNOT from the input to each ancilla. On \(\ket0\) nothing flips, and on \(\ket1\) both ancillas flip. By linearity the result is
\[\alpha\ket{000}+\beta\ket{111},\]
not \((\alpha\ket0+\beta\ket1)^{\otimes3}\). This is the same effect we saw when a CNOT on plus made a Bell pair instead of two copies of plus.
Is any single qubit a copy of the input? Its reduced state is \(\mathrm{diag}(|\alpha|^2,|\beta|^2)\), which lacks the off-diagonal entry \(\alpha\beta^*\) of the input. So no. The coherence is stored only in the relation between the two configurations 000 and 111, and no-cloning is respected.
The two-dimensional span of \(\ket{000}\) and \(\ket{111}\) is the code space. It stores one logical qubit in three physical qubits, with \(\ket{000}\) and \(\ket{111}\) playing the roles of logical 0 and 1.
Three-qubit repetition encoding produces α|000⟩+β|111⟩. This is joint encoding, not three independent copies.
What does a single error do to the encoded state? Number the qubits 1, 2, 3 from left to right, and write \(X_1\) for \(X\) on qubit 1 with nothing done to the others, that is \(X\otimes I\otimes I\). Similarly for \(X_2\), \(Z_1\) and so on.
A flip on qubit 1 gives \(\alpha\ket{100}+\beta\ket{011}\). Both terms changed in the same way, so the error has not measured \(\alpha\) or \(\beta\). Try a complex input, \((\ket0+i\ket1)/\sqrt2\). Its encoding \((\ket{000}+i\ket{111})/\sqrt2\) becomes \((\ket{010}+i\ket{101})/\sqrt2\) after \(X_2\). The relative phase \(i\) has survived, and a correct recovery must keep it, not only the two probabilities.
Where do the errors take the state? No error leaves it in the span of \(\{000,111\}\). \(X_1\) moves it into the span of \(\{100,011\}\), \(X_2\) into \(\{010,101\}\), and \(X_3\) into \(\{001,110\}\). These four subspaces use disjoint configurations, so they are mutually orthogonal. If we could ask which subspace the state is in, we would learn the error without learning the amplitudes.
A phase flip behaves differently. \(Z_1\) gives \(\alpha\ket{000}-\beta\ket{111}\), which is still in the code space. Nothing about the subspace reveals it.
Problems
Problem 14.1. Write the encoded state after a bit flip on the third qubit. Does this reveal either logical amplitude?
Worked solution
It is α|001〉+β|110〉. The same flip acts on both components and does not measure α or β. Diagnosing the error without learning the logical value is the next task.
14.2 Detection and Recovery
Each single bit flip sends the code into its own orthogonal subspace. How can we find out which one without measuring the qubits themselves? We build a measurement of whether two bits agree, using an ancilla, and see that it reveals the error and nothing else. Two such parities identify any single flip, and a conditional correction then restores the logical state.
How can we learn whether bits 1 and 2 agree without learning either bit? Bring in an ancilla in \(\ket0\) and apply CNOTs from qubit 1 and from qubit 2 into it. The ancilla then holds \(x_1\oplus x_2\), the parity of the two bits.
Apply this to \(\alpha\ket{100}+\beta\ket{011}\). In both terms bits 1 and 2 disagree, so the ancilla becomes \(\ket1\) in both: the state is \((\alpha\ket{100}+\beta\ket{011})\ket1\). The ancilla factors out. Measuring it gives 1 with certainty and leaves the data untouched. The outcome depends on the error, not on \(\alpha\) or \(\beta\), because both codewords have the same parities.
A Z-parity measurement. The auxiliary records the XOR of two data bits, revealing agreement without reading either logical basis value separately.
A second ancilla records the parity of bits 2 and 3. The pair of results is the syndrome. No error gives (0,0), \(X_1\) gives (1,0), \(X_2\) gives (1,1), and \(X_3\) gives (0,1). Each single flip has its own syndrome.
These parity measurements are often described with signs. The operator \(Z_1Z_2=Z\otimes Z\otimes I\) multiplies a configuration by \(+1\) when bits 1 and 2 agree and by \(-1\) when they disagree. So the two parity outcomes are its eigenvalues, \(+1\) for parity 0 and \(-1\) for parity 1, and the ancilla circuit is a projective measurement onto its two eigenspaces. A Hermitian operator used this way, to name the outcomes of the projective measurement onto its eigenspaces, is called an observable. In this language the syndrome measures the observables \(Z_1Z_2\) and \(Z_2Z_3\): no error gives \((+,+)\), \(X_1\) gives \((-,+)\), \(X_2\) gives \((-,-)\) and \(X_3\) gives \((+,-)\). Both observables are diagonal, so they commute, and measuring one does not disturb the result of the other. The signs are eigenvalues, not signs of the logical amplitudes.
Once the syndrome names the flipped qubit, what remains? Take \(\alpha\ket{010}+\beta\ket{101}\). Bits 1 and 2 disagree in both terms, and so do bits 2 and 3, so the syndrome is \((-,-)\) with certainty, whatever \(\alpha\) and \(\beta\) are. Applying \(X_2\) restores \(\alpha\ket{000}+\beta\ket{111}\). If the logical qubit is needed on one wire, the two encoding CNOTs, applied again, give \((\alpha\ket0+\beta\ket1)\ket{00}\).
What if the error is not a definite flip but a superposition of possibilities, such as \((I+iX_2)/\sqrt2\)? The syndrome measurement separates the branches. In one branch the state is the untouched codeword, and in the other it is the \(X_2\) image, each with probability \(1/2\). The correction for each branch restores the same logical state. So correcting a few definite errors also corrects any linear combination of them.
The measurement is allowed to learn the error. It must not learn the encoded amplitudes. This recovery assumes ideal ancillas, gates and measurements. Real syndrome circuits are themselves faulty, and keeping their faults from spreading is the further subject of fault tolerance.
Problems
Problem 14.2. Why not measure all three data bits and take a majority?
Worked solution
That would distinguish 000 from 111 and collapse the logical superposition. Parity measurements reveal only the relative disagreement, leaving α and β coherent.
14.3 Correction Conditions
The code corrects single bit flips. What exactly makes a set of errors correctable, and which errors defeat this code? We start from the phase flip, which the syndrome could not see, and find what goes wrong. That leads to a general criterion, which the bit-flip set satisfies and the phase flip violates. Then we look at what happens when more errors occur than the code was built for.
Why can the code not correct \(Z_1\)? Compare its effect on the two codewords: \(\bra{000}Z_1\ket{000}=1\) but \(\bra{111}Z_1\ket{111}=-1\). The error acts differently on logical 0 and logical 1. An environment that applied \(Z_1\) or did nothing has, in effect, interacted with the logical value, and no syndrome can undo that without knowing the value.
For a correctable set, then, each pair of errors should act on all codewords alike once we look only inside the code space. We quote the precise statement, the Knill–Laflamme condition (1997). Let \(P\) project onto the code space and let \(\{E_a\}\) be the error set. Exact correction of every error in the set, and of their linear combinations, is possible exactly when
\[PE_a^\dagger E_bP=c_{ab}P\]
for some numbers \(c_{ab}\) that do not depend on the logical state.
Check the bit-flip set \(\{I,X_1,X_2,X_3\}\). Different errors send the code space into orthogonal subspaces, so \(PE_a^\dagger E_bP=0\) for \(a\neq b\). Each \(X_j\) satisfies \(X_j^\dagger X_j=I\), so the diagonal terms give \(P\). The condition holds. For the set \(\{I,Z_1\}\), \(PZ_1P=\ket{000}\bra{000}-\ket{111}\bra{111}\), which is not a multiple of \(P\). The condition fails, as our calculation showed.
What would general single-qubit noise require? Define \(Y=iXZ\), so that \(Y\ket0=i\ket1\) and \(Y\ket1=-i\ket0\). Every \(2\times2\) matrix is a combination of \(I,X,Y,Z\), so a code that corrects \(X\), \(Y\) and \(Z\) on each qubit corrects every single-qubit error. The three-qubit repetition code corrects only \(X\). Codes for the larger set need more qubits, such as Shor's nine-qubit code or the five-qubit code.
What happens when two bits flip? Apply \(X_1X_2\) to a codeword. The configuration 000 becomes 110, whose syndrome is \((+,-)\). A single \(X_3\) gives the same syndrome, so the decoder applies \(X_3\). The total action is \(X_1X_2X_3\), which exchanges 000 with 111 and sends the logical amplitudes \((\alpha,\beta)\) to \((\beta,\alpha)\). Two faults have become a logical bit flip.
With independent flips of probability \(p\) on each qubit, recovery fails on two or three flips. Counting the cases exactly as for the classical repetition code gives \(3p^2-2p^3\). The formula is the same, but what is recovered is a coherent logical qubit.
Phase errors are worse. A single \(Z_1\) acts as a logical \(Z\), changing \(\alpha\ket{000}+\beta\ket{111}\) into \(\alpha\ket{000}-\beta\ket{111}\) without changing any parity. So this code offers no protection at all against phase noise, and a single phase error on any qubit corrupts the logical state. Any claim about a code must name the error set it corrects and the assumptions about the recovery hardware.
A code spends several physical qubits on one logical qubit, so it lowers the rate. For a given noisy channel, what is the best rate at which information can be sent through it reliably?
Problem 14.3. Does Z1 satisfy the correction criterion together with identity?
Worked solution
No. PZ1P acts differently on the two logical basis states and is not a scalar multiple of P. The environment could distinguish a logical phase effect.
Transfer problem. A noise process applies \((I+iX_2)/\sqrt2\) to an encoded state. What syndrome probabilities and recovered state result?
Worked solution
The two orthogonal syndrome branches are the original codeword and its X2 image, each with probability one half. The first has syndrome (+,+), the second (−,−). Apply identity or X2 accordingly. Both recover the original logical state; the second branch’s factor i is an overall phase and has no effect on it.
Summary
Quantum error correction protects unknown superpositions by encoding \(k\) logical qubits into an entangled \(n\)-qubit subspace so local errors map the code space into mutually orthogonal syndrome subspaces.
Measuring stabilizer generators extracts a discrete classical error syndrome without collapsing the encoded logical superposition \(\alpha|0_L\rangle + \beta|1_L\rangle\).
By the Knill–Laflamme conditions \(P E_a^\dagger E_b P = c_{ab} P\), discretizing continuous Pauli errors into \(I, X, Z, Y\) suffices to correct arbitrary single-qubit channels.
Questions and worked problems
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
For the three-qubit bit-flip code, give the syndrome \((Z_1Z_2,Z_2Z_3)\) after (a) \(X_3\) and (b) \(X_1X_3\). What does the standard decoder do in case (b), and what is the net effect?
Hint 1
A parity is \(-\) when its two bits disagree.
Hint 2
\(X_1X_3\) turns \(000\) into \(101\).
Worked solution
(a) \(X_3\) gives \(\alpha\ket{001}+\beta\ket{110}\): \(Z_1Z_2=+\), \(Z_2Z_3=-\). (b) \(X_1X_3\) gives \(\alpha\ket{101}+\beta\ket{010}\): both parities are \(-\), the syndrome of a single \(X_2\). The decoder applies \(X_2\), so the total is \(X_1X_2X_3\), which exchanges \(\ket{000}\) and \(\ket{111}\): a logical bit flip \((\alpha,\beta)\to(\beta,\alpha)\) with no warning. Any two flips are decoded into a logical error.
Encode \(\ket+\) as \((\ket{000}+\ket{111})/\sqrt2\). Find the reduced state of physical qubit \(1\). Could a measurement on that one qubit reveal whether the logical state was \(\ket{+}\) or \(\ket-\)?
Hint 1
Tracing out qubits \(2,3\) removes the cross terms because their labels \(00\) and \(11\) differ.
Hint 2
Encode \(\ket-\) and compare.
Worked solution
Qubit \(1\) has reduced state \(\mathrm{diag}(\frac12,\frac12)=I/2\): the cross terms vanish because the other two qubits carry orthogonal labels. Encoding \(\ket-\) gives \((\ket{000}-\ket{111})/\sqrt2\), whose single-qubit reductions are also \(I/2\). No measurement on one physical qubit distinguishes them. The logical phase lives only in the joint state, which is why a local error on one qubit cannot read it, and also why a single-qubit phase error can still change it.
The phase-flip code encodes \(\alpha\ket0+\beta\ket1\) as \(\alpha\ket{+++}+\beta\ket{---}\). What does \(Z_2\) do to the encoded state? Which parities, \(X_1X_2\) and \(X_2X_3\), detect it, and with what results?
Hint 1
\(Z\ket\pm=\ket\mp\).
Hint 2
\(X\) has eigenvalue \(+1\) on \(\ket+\) and \(-1\) on \(\ket-\).
Worked solution
\(Z_2\) gives \(\alpha\ket{+-+}+\beta\ket{-+-}\). In the \(\pm\) labels this is exactly a “bit flip” on the middle position, so both \(X_1X_2\) and \(X_2X_3\) return \(-1\), in both branches, without revealing \(\alpha,\beta\). The phase-flip code is the bit-flip code written in the \(\pm\) basis: it corrects single \(Z\) errors.
Measure the parity \(Z_1Z_2\) of \(\alpha\ket{010}+\beta\ket{101}\) by computing \(q_1\oplus q_2\) into an ancilla \(\ket0\) with two CNOTs. (a) Write the joint state after the CNOTs. (b) Is the ancilla entangled with the data? (c) Compare with measuring qubit \(1\) directly.
Hint 1
In both branches, \(q_1\oplus q_2=1\).
Hint 2
A direct measurement of qubit \(1\) gives \(0\) in one branch and \(1\) in the other.
Worked solution
(a) Both terms have \(q_1\oplus q_2=1\), so the state becomes \((\alpha\ket{010}+\beta\ket{101})\otimes\ket1\). (b) The ancilla is in a product with the data: measuring it gives \(1\) with certainty and leaves the logical superposition untouched. (c) Measuring qubit \(1\) directly would give \(0\) (from the \(\alpha\) branch) or \(1\) (from the \(\beta\) branch) with probabilities \(|\alpha|^2,|\beta|^2\), collapsing the encoded qubit. The parity is the same for both branches, so learning it learns about the error and nothing about the logical state.
Each physical qubit independently suffers \(X\) with probability \(p\). After ideal syndrome measurement and correction, the logical qubit undergoes \(X_L\) with probability \(p_L\). (a) Show \(p_L=3p^2-2p^3\). (b) Write the resulting logical channel. (c) Evaluate at \(p=0.01\) and \(p=0.1\), and find the value of \(p\) above which encoding hurts.
Hint 1
A logical error occurs when two or three qubits flip.
Hint 2
Compare \(3p^2-2p^3\) with \(p\).
Worked solution
(a) Two flips occur with probability \(3p^2(1-p)\) and three with \(p^3\); both lead to \(X_L\), giving \(3p^2-2p^3\). (b) The logical channel is \(\rho_L\mapsto(1-p_L)\rho_L+p_LX_L\rho_LX_L\), a bit-flip channel with a smaller probability. (c) At \(p=0.01\), \(p_L\approx3.0\times10^{-4}\); at \(p=0.1\), \(p_L=0.028\). Encoding helps when \(3p^2-2p^3<p\), that is \(p<\frac12\). These figures assume perfect syndrome measurement and recovery and pure bit-flip noise.
Use the Knill–Laflamme condition \(PE_a^\dagger E_bP=c_{ab}P\) with \(P=\ket{000}\bra{000}+\ket{111}\bra{111}\). (a) Show that the error set \(\{I,Z_1Z_2\}\) satisfies it. (b) What does \(Z_1Z_2\) do to a codeword, and does it need correcting? (c) Contrast with \(\{I,Z_1\}\).
Hint 1
\(Z_1Z_2\) has eigenvalue \(+1\) on both \(\ket{000}\) and \(\ket{111}\).
Hint 2
\(PZ_1P=\ket{000}\bra{000}-\ket{111}\bra{111}\).
Worked solution
(a) \(Z_1Z_2\ket{000}=\ket{000}\) and \(Z_1Z_2\ket{111}=\ket{111}\), so \(PZ_1Z_2P=P\) and every pair satisfies the condition, with \(c_{ab}=1\). (b) \(Z_1Z_2\) acts as the identity on the code space, so it needs no correction at all: the logical qubit is unaffected. (c) \(PZ_1P=\ket{000}\bra{000}-\ket{111}\bra{111}\) is not a multiple of \(P\), so \(\{I,Z_1\}\) fails: \(Z_1\) acts as the logical \(Z\), and no recovery can tell whether it happened. Some physical errors are harmless to a code, and the condition recognizes them.
Apply \(X_1\) to the phase-flip-code state \(\alpha\ket{+++}+\beta\ket{---}\). (a) What is the new state? (b) Do the syndromes \(X_1X_2\), \(X_2X_3\) detect it? (c) What logical operation has occurred, and what does this say about protecting against both kinds of error?
Hint 1
\(X\ket+=\ket+\) and \(X\ket-=-\ket-\).
Hint 2
The \(X\) parities are unchanged by a sign.
Worked solution
(a) \(X_1\) gives \(\alpha\ket{+++}-\beta\ket{---}\). (b) The parities \(X_1X_2\), \(X_2X_3\) are still \(+1\) in both branches: the error is invisible. (c) It is a logical \(Z\), changing \(\alpha\ket0+\beta\ket1\) to \(\alpha\ket0-\beta\ket1\). Each three-qubit code corrects one kind of single-qubit error and is defenseless against the other. Protecting against arbitrary single-qubit errors requires a code that detects both, such as Shor’s nine-qubit code, which nests the two repetition codes.
A student objects: “Measuring \(Z_1Z_2\) and \(Z_2Z_3\) is a measurement of the encoded qubit, so it must collapse \(\alpha\ket{000}+\beta\ket{111}\) and destroy the superposition.” Take \(\alpha=\beta=1/\sqrt2\) and the error \(X_1\). Compute the syndrome probabilities and the state afterward.
Hint 1
\(X_1\) gives \((\ket{100}+\ket{011})/\sqrt2\).
Hint 2
Both terms have the same parity values.
Worked solution
After \(X_1\) the state is \((\ket{100}+\ket{011})/\sqrt2\). Both terms have \(Z_1Z_2=-1\) and \(Z_2Z_3=+1\), so the syndrome is \((-,+)\) with probability \(1\), and the measurement leaves the state unchanged. Applying \(X_1\) then restores \((\ket{000}+\ket{111})/\sqrt2\) exactly. The syndrome observables have the same value on every codeword (and on every codeword with the same error), so they distinguish error subspaces and nothing within them. A measurement collapses only the distinctions it resolves.
Concatenate the bit-flip code: encode each of the three physical qubits again with the same code (nine qubits), and correct at both levels. For small \(p\), use \(p_L\approx3p^2\) at each level. (a) Estimate the second-level logical error probability. (b) Evaluate for \(p=0.01\). (c) For which \(p\) does concatenation keep reducing the error, under this approximation, and what assumptions make the estimate optimistic?
Hint 1
The second level sees each first-level block as a qubit with error \(3p^2\).
Hint 2
Iterating \(p\mapsto3p^2\) shrinks \(p\) when \(3p<1\).
Worked solution
(a) Each level-one block fails with probability about \(3p^2\), and the level-two code fails when two of its three blocks fail: \(3(3p^2)^2=27p^4\). (b) At \(p=0.01\): level one gives \(3\times10^{-4}\), level two \(2.7\times10^{-7}\). (c) Iterating \(p\mapsto3p^2\) decreases the error when \(p<\frac13\) in this approximation: a threshold. The estimate assumes independent bit-flip noise only, perfect syndrome measurement, and perfect correction gates. Real fault-tolerant thresholds are much lower, because the recovery circuits themselves introduce errors.
A code storing one logical qubit in \(n\) physical qubits corrects every single-qubit error (\(X\), \(Y\), or \(Z\) on any qubit) and maps each such error, and the no-error case, to its own orthogonal two-dimensional subspace. (a) Show that this requires \(2(1+3n)\le2^n\). (b) Find the smallest \(n\). (c) What is special about that value, and why can the three-qubit codes not satisfy the bound?
Hint 1
Count the distinct error cases: no error plus three Paulis on each of \(n\) qubits.
Hint 2
The orthogonal subspaces must fit in the \(2^n\)-dimensional space.
Worked solution
(a) There are \(1+3n\) cases, each requiring an orthogonal two-dimensional subspace, so \(2(1+3n)\le2^n\). (b) \(n=3\): \(20>8\); \(n=4\): \(26>16\); \(n=5\): \(32\le32\). So \(n\ge5\). (c) At \(n=5\) the bound is met with equality: the subspaces fill the whole space, and the five-qubit code achieves this, so it is called perfect. Three qubits have room for only four orthogonal two-dimensional subspaces, enough for no error and three bit flips, but not for phase errors as well. (Degenerate codes, in which different errors act identically on the code, are not covered by this counting.)
