Exercises: Chapter 25 — Surface Codes and Fault-Tolerant Computation: The Path from Noisy Qubits to Reliable Quantum Computers

Exercise 25.1 — Toric Code Ground State. For a $2 \times 2$ toric code (8 qubits on a torus), write down all stabilizer generators. Compute the dimension of the code space. Construct the logical $X$ and $Z$ operators for both logical qubits. Verify that $\bar{X}_1$ anticommutes with $\bar{Z}_1$ but commutes with $\bar{X}_2$ and $\bar{Z}_2$.

Exercise 25.2 — Anyon Braiding. Explain how moving an $e$-anyon around an $m$-anyon produces a phase of $-1$ (mutual statistics). Show that this implies the logical operators on the torus satisfy the correct commutation relations. What does this have to do with topological protection?

Exercise 25.3 — Surface Code Overhead. For physical error rates $p = 10^{-3}, 10^{-4}, 10^{-5}$, compute the required code distance $d$ to achieve a logical error rate of $10^{-15}$. Estimate the number of physical qubits per logical qubit for each case. Plot the overhead as a function of physical error rate.

Exercise 25.4 — Magic State Distillation Efficiency. The Bravyi-Kitaev 15-to-1 distillation protocol reduces the error rate from $\epsilon$ to $35\epsilon^3$. If the initial magic state error rate is $\epsilon = 10^{-2}$, how many rounds of distillation are needed to achieve $\epsilon < 10^{-10}$? What is the total number of input magic states required? Repeat for the 5-to-1 distillation protocol ($\epsilon \to 6\epsilon^2$, lower overhead but lower yield).

Exercise 25.5 — Decoding Simulation. Write a Python simulation of the surface code under a depolarizing noise model. Implement a simple MWPM decoder (or use the union-find algorithm). For a distance-3 code, compute the logical error rate as a function of physical error rate and verify that it crosses below the physical error rate at some point (indicating the code is beneficial).

Exercise 25.6 — Threshold Calculation. Using the mapping to the random-bond Ising model, estimate the surface code threshold under a phenomenological noise model (perfect stabilizer measurements with data qubit error rate $p$). Show that the critical error rate is approximately $p_c \approx 10.9\%$ for perfect measurements.

Exercise 25.7 — Lattice Surgery. Describe in detail how to implement a logical CNOT gate between two surface code patches using lattice surgery. How many surface code cycles does it take? What is the logical error rate per CNOT as a function of the physical error rate and code distance?

Exercise 25.8 — Eastin-Knill Theorem. Prove that no stabilizer code can have a universal set of transversal gates. (Hint: Show that the set of transversal gates for a stabilizer code is contained in the normalizer of the Pauli group, which is the Clifford group. Then show that the Clifford group is not universal.)

Exercise 25.9 — Error Propagation in Syndrome Extraction. Consider a plaquette measurement circuit with a single $X$ error on the ancilla qubit between the second and third CNOT gates. Show that this error propagates to $X$ errors on two data qubits. Explain why this "hook error" does not cause a logical error for a distance-$d$ code if $d \geq 3$.

Exercise 25.10 — Resource Estimate for Shor's Algorithm. Estimate the total number of physical qubits required to factor a 2048-bit RSA number using Shor's algorithm on a surface code with physical error rate $p = 10^{-3}$. Use the following assumptions: $10^4$ logical qubits, $d = 27$, 5 magic state factories, and $10^{10}$ logical gate operations. How does the estimate change if $p = 10^{-4}$?