Chapter 40 Exercises: Capstone — Quantum Computing: From Qubits to Algorithms

Part A: Conceptual Questions (*)

These questions test your understanding of the core synthesis ideas. No calculations required.

A.1 Explain why a classical computer cannot efficiently simulate a quantum computer with $n$ qubits. Specifically, how does the memory requirement scale, and at approximately what value of $n$ does it exceed the capacity of any existing supercomputer?

A.2 The Hadamard gate creates superposition, and the CNOT gate creates entanglement. Explain why both are necessary for universal quantum computation. What types of computation would be impossible with only one of the two?

A.3 A friend claims: "Grover's algorithm gives an exponential speedup for search problems." Correct this claim. Why does the distinction between quadratic and exponential speedups matter for the practical impact of quantum computing?

A.4 Explain the "arms race" between quantum advantage claims and classical simulation algorithms. Why is it so difficult to prove that a quantum computer has done something no classical computer can do?

A.5 The no-cloning theorem forbids copying quantum states. Yet quantum error correction "protects" quantum information by spreading it across multiple physical qubits. How is this not a contradiction? What exactly is being encoded — the state itself, or the information about the state?

A.6 Why is the surface code considered the most practical error correction code for current hardware? What physical constraint does it satisfy that other codes (Shor, Steane) do not?

A.7 Trapped-ion quantum computers have far fewer qubits than superconducting quantum computers but often achieve much higher quantum volume. Explain how this is possible and what quantum volume measures.

A.8 Post-quantum cryptographic standards were published in 2024, even though fault-tolerant quantum computers capable of running Shor's algorithm are likely a decade or more away. What threat model justifies this urgency?

Part B: Applied Problems (**)

B.1: Statevector Algebra

(a) Write out the full 4-component statevector for the 2-qubit state obtained by applying $H$ to qubit 0 and then CNOT(0,1) to $|00\rangle$. Verify it is the Bell state $|\Phi^+\rangle = (|00\rangle + |11\rangle)/\sqrt{2}$.

(b) Apply $Z$ to qubit 0 of $|\Phi^+\rangle$. Write the resulting statevector and identify which Bell state it is.

(c) Apply $X$ to qubit 1 of $|\Phi^+\rangle$. Write the resulting statevector. Is this a Bell state?

(d) Compute the reduced density matrix $\rho_A = \text{Tr}_B(|\Phi^+\rangle\langle\Phi^+|)$. Verify that it equals $I/2$ — the maximally mixed state — confirming that the Bell state is maximally entangled.

B.2: Gate Identities and Algebra

(a) Verify algebraically that $HXH = Z$ and $HZH = X$. What does this mean geometrically on the Bloch sphere?

(b) Show that CNOT$_{01}$ $\cdot$ CNOT$_{10}$ $\cdot$ CNOT$_{01}$ = SWAP by explicit $4 \times 4$ matrix multiplication.

(c) Prove that $CZ = (I \otimes H) \cdot \text{CNOT} \cdot (I \otimes H)$. Why does this imply that CZ is symmetric in the two qubits, even though CNOT is not?

(d) The $\sqrt{\text{SWAP}}$ gate is defined as the matrix square root of SWAP. Find $\sqrt{\text{SWAP}}$ and verify that applying it twice gives SWAP. Is $\sqrt{\text{SWAP}}$ an entangling gate?

B.3: Grover's Algorithm by Hand

(a) For $N = 4$ ($n = 2$ qubits) with marked state $|11\rangle$, work through the algorithm step by step. Write the state vector after: (i) Hadamard initialization, (ii) oracle application, (iii) diffusion operator. Compute the probability of measuring $|11\rangle$.

(b) For this $N = 4$ case, compute the success probability after 0, 1, 2, and 3 iterations. What happens if you apply too many iterations?

(c) Repeat part (a) with two marked states: $|01\rangle$ and $|11\rangle$. What is the optimal number of iterations now?

(d) For a search space of $N = 2^{20} \approx 10^6$ items, how many Grover iterations are needed? How many classical queries would a brute-force search require? Express the speedup factor.

B.4: Quantum Phase Estimation

(a) The $Z$ gate has eigenvalue $-1$ for eigenstate $|1\rangle$. Write $-1 = e^{2\pi i\varphi}$ and determine $\varphi$. If you use QPE with $t = 3$ counting qubits, what measurement outcome do you expect?

(b) The $T$ gate has eigenvalue $e^{i\pi/4}$ for eigenstate $|1\rangle$. Determine $\varphi$ and the expected QPE outcome with $t = 4$ bits.

(c) Consider $R_z(2\pi/3)$, which gives $\varphi = 1/6$ for $|1\rangle$. This is not a $t$-bit fraction for any finite $t$. With $t = 3$, what are the most likely measurement outcomes, and what are their probabilities?

(d) Explain why QPE with $t$ counting qubits and $m$ eigenstate qubits requires $O(t)$ applications of controlled-$U$ gates but $O(2^t)$ applications of $U$ itself. Why is this not a problem for Shor's algorithm?

B.5: Shor's Algorithm

(a) For $N = 15$ and $a = 2$, compute $a^k \bmod N$ for $k = 1, 2, \ldots, 8$. Determine the period $r$. Find the factors using $\gcd(a^{r/2} \pm 1, N)$.

(b) For $N = 15$ and $a = 4$, what is the period $r$? Does the algorithm succeed in this case? Why or why not?

(c) For $N = 21$ and $a = 2$, compute $a^k \bmod N$ and find $r$. Find the factors.

(d) Estimate the resources needed to factor a 2048-bit RSA key: how many logical qubits, how many T-gates (approximately), and how many physical qubits at a surface code distance of $d = 17$?

B.6: Error Correction

(a) In the 3-qubit bit-flip code, the state $\alpha|000\rangle + \beta|111\rangle$ suffers a bit-flip on qubit 2, giving $\alpha|001\rangle + \beta|110\rangle$. Compute the syndrome by evaluating the parity operators $Z_1 Z_2$ and $Z_2 Z_3$. Identify the error.

(b) Explain why measuring the syndrome does not collapse the superposition $\alpha|0\rangle_L + \beta|1\rangle_L$. Specifically, what information does the syndrome contain and what information does it NOT contain?

(c) A general single-qubit error can be written $E = aI + bX + cY + dZ$. The Shor code corrects $X$, $Y$, and $Z$ errors individually. Explain why this suffices to correct $E$, despite $E$ being a continuous operator.

(d) If the physical error rate is $p = 0.001$ per gate, the surface code threshold is $p_{\text{th}} = 0.01$, and the logical error rate scales as $(p/p_{\text{th}})^{d/2}$, what code distance $d$ is needed for a logical error rate of $10^{-15}$?

B.7: Architecture Analysis

(a) A quantum algorithm requires 100 two-qubit gates. The superconducting platform has $T_2 = 100\,\mu$s and gate time $50$ ns. The trapped-ion platform has $T_2 = 1$ s and gate time $100\,\mu$s. Compute the fraction of the coherence budget used on each platform. Which has more headroom?

(b) The same algorithm on a nearest-neighbor architecture (superconducting) requires additional SWAP gates for long-range interactions. If each long-range interaction requires 3 SWAP gates (each SWAP = 3 CNOTs = 9 additional two-qubit gates), and 30% of the 100 gates are long-range, how many total two-qubit gates are needed? Recompute the coherence budget fraction.

(c) A quantum volume of $V_Q = 2^{12}$ means the device can reliably execute a circuit of width 12 and depth 12. If an algorithm requires a circuit of width 10 and depth 50, can this device run it? What metric would better capture the device's capability?

(d) Compare the energy cost of operating a dilution refrigerator (typically $\sim 25$ kW) for a superconducting quantum computer versus the electrical power for a trapped-ion system ($\sim 5$ kW). If a quantum computation takes 1 hour on the superconducting platform and 10 hours on the trapped-ion platform (due to slower gates), which uses more total energy?

Part C: Computational Problems (***)

These problems require writing and running code. Use the simulator from this chapter.

C.1: Bell State Circuit

(a) Build the four Bell state preparation circuits: $|\Phi^+\rangle$, $|\Phi^-\rangle$, $|\Psi^+\rangle$, $|\Psi^-\rangle$. Verify each by checking the statevector.

(b) Implement a Bell state measurement circuit that determines which of the four Bell states an unknown 2-qubit state is in.

(c) Combine (a) and (b) to implement superdense coding: encode two classical bits into a single qubit using a shared Bell pair.

C.2: Grover Benchmarking

(a) Implement Grover's algorithm in your simulator for $n = 3$ to $n = 12$ qubits. For each, find the optimal iteration count empirically and compare to $\lfloor\pi\sqrt{N}/4\rfloor$.

(b) Plot the success probability as a function of iteration count for $n = 6$. Verify the oscillatory behavior and identify the over-rotation point.

(c) Extend to multiple marked items ($M = 1, 2, 4, 8$ for $n = 8$). Verify that the optimal iterations scale as $\sqrt{N/M}$.

(d) Implement quantum counting: use QPE applied to the Grover iterate to estimate $M$ without knowing it in advance.

C.3: QPE Implementation

(a) Implement QPE in your simulator. Test it on the $Z$ gate ($\varphi = 1/2$), $S$ gate ($\varphi = 1/4$), and $T$ gate ($\varphi = 1/8$) with $t = 4$ counting qubits. Verify exact results.

(b) Test QPE on $R_z(2\pi/5)$ (phase $\varphi = 1/10$, not a power-of-2 fraction) with $t = 4, 6, 8, 10$. Plot the probability distribution over outcomes for each $t$ and show the distribution narrowing.

(c) Compute the phase estimation error as a function of $t$ over 1000 repeated measurements. Verify $O(1/2^t)$ scaling.

C.4: Shor's Algorithm for Small Numbers

(a) Implement the modular exponentiation unitary $U_a|x\rangle = |ax \bmod N\rangle$ for $N = 15$. Verify it is unitary.

(b) Implement the full Shor's algorithm (QPE + classical post-processing) for $N = 15$, $a = 7$. Run it 100 times and report the success rate.

(c) Extend to $N = 21$ and $N = 35$. Determine appropriate values of $a$ and the number of counting qubits.

(d) For each factored number, compare the number of quantum operations to the classical brute-force trial division.

C.5: Error Correction Simulation

(a) Implement the full 3-qubit bit-flip code: encoding, error injection, syndrome extraction, correction, decoding. Test with all possible single-qubit errors on all three qubits.

(b) Add a noise model: after encoding, each qubit suffers an independent $X$ error with probability $p$. Run 10,000 trials for $p = 0.01, 0.05, 0.1, 0.15, 0.2$. Plot the logical error rate versus $p$ and find the break-even point (where the code starts helping).

(c) Implement the Shor 9-qubit code with a depolarizing noise model ($X$, $Y$, or $Z$ error, each with probability $p/3$). Compare its performance to the 3-qubit code.

(d) For the 3-qubit code, plot the logical vs. physical error rate on a log-log scale and verify the expected scaling $p_L \propto p^2$ (since the code corrects 1 error, the logical error rate is dominated by 2-error events).

Part D: Challenge Problems (****)

D.1: The Bernstein-Vazirani Algorithm

Implement the Bernstein-Vazirani algorithm, which determines a secret string $s \in \{0,1\}^n$ from a single quantum query of the function $f(x) = s \cdot x \pmod{2}$. Test for $n = 2, 4, 6, 8, 10$. Verify that the quantum algorithm uses 1 query while the classical lower bound is $n$ queries.

D.2: Variational Quantum Eigensolver (VQE)

Implement a simple VQE for the 1-qubit Hamiltonian $H = \cos\alpha\, Z + \sin\alpha\, X$ (for various $\alpha$). Use a parameterized circuit $R_y(\theta)$ as the ansatz. Optimize $\theta$ classically to minimize $\langle\psi(\theta)|H|\psi(\theta)\rangle$. Verify that the result matches the exact ground state energy $E_0 = -1$.

D.3: Quantum Walk Search

Implement a quantum walk on a cycle graph of $N$ nodes. Show that a coined quantum walk spreads as $\sigma \propto t$ (ballistic) compared to the classical random walk's $\sigma \propto \sqrt{t}$ (diffusive). Verify by plotting position variance versus time steps.

D.4: The Quantum Approximate Optimization Algorithm (QAOA)

Implement QAOA for the MaxCut problem on a small graph (5 vertices, 6 edges). Use $p = 1, 2, 3$ layers and optimize the variational parameters. Compare the approximation ratio to the best classical cut.

D.5: Resource Estimation

Using the results from Section 40.5, build a resource estimator that takes as input a target RSA key size (512, 1024, 2048, 4096 bits) and outputs: (i) the number of logical qubits needed, (ii) the number of T-gates, (iii) the number of physical qubits at surface code distance $d = 17$, and (iv) the estimated wall-clock time at a gate speed of 1 $\mu$s per logical gate cycle.