Exercises: Chapter 16 — Quantum Phase Estimation — The Subroutine That Powers Shor's, Simulation, and Half of Quantum Computing

Exercise 16.1 (Phase Kickback by Hand). Let $U = Z$ (the Pauli-$Z$ gate) and $|\psi\rangle = |1\rangle$. Compute the state after applying controlled-$Z$ with control qubit in state $|+\rangle$. What phase is kicked back? Repeat for $|\psi\rangle = |0\rangle$ and verify that no phase is kicked back.

Exercise 16.2 (QPE Precision). You want to estimate an eigenvalue to 8 bits of precision with 95% success probability. How many estimation qubits $t$ are needed? What if the success probability requirement is tightened to 99.9%?

Exercise 16.3 (Non-Eigenstate Input). Suppose the input to QPE is $|\psi_{\text{in}}\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ and $U = Z$. What are the eigenstates and eigenvalues of $Z$? What distribution of phase estimates do you expect, and with what probabilities? Verify by computing $P(k = 0)$ and $P(k = 2^{t-1})$ explicitly.

Exercise 16.4 (Qiskit: Two-Qubit Unitary). Implement QPE for the two-qubit unitary $U = \text{CNOT} \cdot (H \otimes I)$. Find one eigenstate and its eigenvalue. Use $t = 6$ estimation qubits. Compare the estimated phase with the exact eigenvalue.

Exercise 16.5 (Iterative Phase Estimation). Modify the Qiskit code from Section 16.6.2 to implement iterative phase estimation for the $R_z$ unitary from Section 16.3. Compare the qubit count and circuit depth with the standard QPE approach.

Exercise 16.6 (Probability Derivation). Derive the probability formula $P(k) = \frac{1}{2^{2t}} \frac{\sin^2(\pi(2^t \phi - k))}{\sin^2(\pi(\phi - k/2^t))}$ from first principles. Show that for $\phi = j/2^t$ (an exact $t$-bit fraction), $P(j) = 1$.

Exercise 16.7 (Shor's Connection). Show explicitly that applying QPE to $U_a |y\rangle = |ay \bmod N\rangle$ with the initial state $\frac{1}{\sqrt{N}} \sum_y |y\rangle$ on the target register yields the same measurement distribution as Shor's period-finding circuit. Why does the eigenstate requirement seem to be violated?

Exercise 16.8 (Error Scaling). For QPE with $t$ estimation qubits and a phase $\phi$ that is not an exact $t$-bit fraction, show that the probability of obtaining an estimate within distance $\epsilon$ of the true phase satisfies $P(|\hat{\phi} - \phi| < \epsilon) \geq 1 - \frac{1}{2(2^t \epsilon - 1)}$ for $\epsilon > 1/2^t$.

Exercise 16.9 (Hamiltonian Simulation Connection). Consider a Hamiltonian $H = \sigma_z$ (single qubit). (a) Compute the eigenvalues and eigenstates. (b) Implement QPE with $U = e^{-iHt}$ for $t = 1$. (c) What phase do you measure if the input is $|0\rangle$? $|1\rangle$? (d) How many estimation qubits are needed to resolve the energy splitting to chemical accuracy (1.6 mHartree)?

Exercise 16.10 (Circuit Depth). For QPE with $t$ estimation qubits, if each controlled-$U^{2^j}$ requires $2^j \cdot d$ gates (where $d$ is the depth of a single controlled-$U$), compute the total circuit depth. Compare this with the depth of IPE using $t$ rounds of $d$ gates each. For what values of $t$ and $d$ does IPE have lower total depth?

Exercise 16.11 (Phase Kickback for Multi-Qubit Unitaries). Consider $U = \text{CNOT} \cdot (H \otimes I)$. (a) Compute the eigenvalues and eigenvectors of $U$. (b) For each eigenvector, compute the phase $\phi$ that QPE would return. (c) If the input is $|0\rangle|0\rangle$ (which is NOT an eigenstate), what phases would you expect to measure, and with what probabilities?

Exercise 16.12 (QPE Precision for Irrational Phases). The phase $\phi = 1/\sqrt{2}$ is irrational. Using the formula $P(k) = \frac{1}{2^{2t}} \cdot \frac{\sin^2(\pi(2^t \phi - k))}{\sin^2(\pi(\phi - k/2^t))}$, compute the probability distribution over measurement outcomes for $t = 4$ estimation qubits. What are the three most likely outcomes? What is the total probability of measuring one of these three?

Exercise 16.13 (Comparing QPE and IPE). Implement both standard QPE and iterative QPE in Qiskit for the unitary $U = R_z(2\pi \cdot 0.412)$ with eigenstate $|1\rangle$. Use $t = 6$ estimation qubits for QPE and 6 rounds for IPE. Compare: (a) the total number of qubits required, (b) the circuit depth, (c) the accuracy of the phase estimate, and (d) the robustness to depolarizing noise with error rate $p = 0.01$ per gate.