Exercises: Chapter 23 — Classical Error Correction Review: Repetition Codes, Hamming Codes, and Why Quantum Is Harder (No-Cloning Theorem)

Exercise 23.1 — Repetition Code Analysis. For the 3-bit repetition code, compute the exact probability of decoding error as a function of $p$. Plot this against the uncoded error probability for $p \in [0, 0.5]$. At what value of $p$ does the repetition code become worse than no coding? Explain why.

Exercise 23.2 — Hamming Code Weight Distribution. Compute the weight distribution (number of codewords of each Hamming weight) for the $[7, 4, 3]$ Hamming code. Verify that the minimum distance is indeed 3. How many correctable error patterns are there? Compute the probability of undetected error for a BSC with $p = 0.01$.

Exercise 23.3 — Parity-Check Matrix Construction. Construct the parity-check matrix for a general $[2^r - 1, 2^r - 1 - r, 3]$ Hamming code. Write a Python function hamming_code(r) that returns $G$ and $H$. Test it for $r = 2, 3, 4$. Verify that $GH^T = 0$ in each case.

Exercise 23.4 — No-Cloning Theorem Proof. Provide a detailed proof of the no-cloning theorem using both the inner product argument and the linearity argument. Then show that the approximate cloning of quantum states is possible: find the optimal fidelity $F$ for a universal $1 \to 2$ cloning machine (the Buzek–Hillery quantum copier). What is the maximum achievable fidelity? (Answer: $F = 5/6$.)

Exercise 23.5 — Quantum Repetition Code with Phase Errors. Modify the quantum repetition code simulation to introduce a phase-flip ($Z$) error instead of a bit-flip error. Show that the code fails to detect or correct the phase flip. Explain why, in terms of the stabilizer generators $Z_1 Z_2$ and $Z_2 Z_3$ commuting with $Z$ errors. Then construct a phase-flip repetition code using Hadamard-conjugated stabilizers.

Exercise 23.6 — Syndrome-Based Decoding for Hamming Codes. Implement a complete Hamming $[7,4,3]$ encoder/decoder in Python. Simulate the code on a binary symmetric channel for $p = 0.001, 0.01, 0.1$ and compare the logical error rates to the theoretical predictions. What fraction of errors are miscorrected (2 or more bit errors decoded as a single-bit error)?

Exercise 23.7 — Dual of the Hamming Code. Compute the dual code of the $[7, 4, 3]$ Hamming code. What are its parameters $[n, k^\perp, d^\perp]$? Show that the dual is the $[7, 3, 4]$ simplex code. What is the relationship between the weight distributions of a code and its dual (MacWilliams identity)?

Exercise 23.8 — Generalized Repetition Code. For the $n$-bit repetition code (odd $n$), derive the exact error probability $P_{\text{error}}^{(n)}$ as a function of $p$. Show that $P_{\text{error}}^{(n)} \to 0$ as $n \to \infty$ for $p < 1/2$. Prove that the code rate $R = 1/n \to 0$ as $n \to \infty$. Compare this with Shannon's capacity $C = 1 - H_2(p)$ for the BSC. How "far" is the repetition code from the Shannon limit?

Exercise 23.9 — Error Discretization Derivation. Consider an arbitrary single-qubit error $E = e_0 I + e_1 X + e_2 Y + e_3 Z$ applied to the state $|\psi_L\rangle = \alpha|0_L\rangle + \beta|1_L\rangle$ of the 3-qubit bit-flip code. Show explicitly that measuring the stabilizers $Z_1 Z_2$ and $Z_2 Z_3$ projects the error onto one of $\{I, X_1, X_2, X_3\}$, and compute the probabilities of each outcome in terms of $e_0, e_1, e_2, e_3$.

Exercise 23.10 — Concatenation of Classical Codes. Consider a concatenated code where the outer code is the $[7,4,3]$ Hamming code and the inner code is the 3-bit repetition code. What are the parameters of the resulting code? Compute its error-correcting capability. How does the complexity of decoding scale with the number of concatenation levels?