Exercises: Chapter 13 — Grover's Algorithm — Searching an Unsorted Database in √N Instead of N — Quadratic Speedup for Unstructured Problems

Exercise 13.1 — Geometric Derivation. Derive the rotation angle $\theta$ for Grover's algorithm with $N = 8$ and $M = 1$. Compute the state vector after 0, 1, and 2 iterations in the $\{|\alpha\rangle, |\beta\rangle\}$ basis. Verify that 2 iterations gives the highest success probability.

Exercise 13.2 — Multiple Marked States. Modify the Qiskit implementation to mark two states simultaneously: $|0110\rangle$ and $|1001\rangle$. Compute $k_{\text{opt}}$ theoretically and verify with simulation. What is the success probability?

Exercise 13.3 — Oracle Design. Design a quantum oracle (as a circuit diagram) that marks all states $|x\rangle$ where $x$ is a multiple of 3, for a 4-qubit database. Implement it in Qiskit and run Grover's algorithm.

Exercise 13.4 — Overshooting. For $N = 16$ and $M = 1$, run Grover's algorithm with $k = 1, 2, 3, 4, 5, 6$ iterations. Plot the success probability vs. $k$. Explain the oscillatory behavior using the geometric picture.

Exercise 13.5 — Amplitude Amplification. Grover's algorithm is a special case of amplitude amplification. Suppose you have a classical randomized algorithm that succeeds with probability $p$. Show how to use $O(1/\sqrt{p})$ iterations of amplitude amplification to boost the success probability to near 1. How many iterations are needed if $p = 0.01$?

Exercise 13.6 — Diffusion Operator Derivation. Verify that $D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}$ by computing $D|s\rangle$ for $n = 3$ and showing that it equals $|s\rangle$ (the uniform superposition is a fixed point of $D$). Then compute $D|\omega\rangle$ for a specific marked state and verify that it inverts the amplitude about the mean.

Exercise 13.7 — Success Probability Formula. Derive the formula $P_{\text{success}}(k) = \sin^2((2k+1)\theta/2)$ from the geometric interpretation. Show that the maximum is achieved when $(2k+1)\theta/2 \approx \pi/2$ and derive $k_{\text{opt}} = \lfloor \frac{\pi}{4}\sqrt{N/M} \rfloor$.

Exercise 13.8 — Cryptographic Implications. AES-128 has a 128-bit key space. If an attacker uses Grover's algorithm to search for the key, how many iterations are needed? What is the effective security level? If the attacker also uses quantum counting to estimate the number of keys, how does this change the analysis?

Exercise 13.9 — Comparison with Classical Search. A database has $N = 10^6$ items. Compare the number of queries needed for: (a) deterministic classical search, (b) randomized classical search with 99% success probability, (c) Grover's algorithm with 99% success probability. How does the comparison change for $N = 10^{12}$?

Exercise 13.10 — Grover with M = N/2. What happens when exactly half the items are solutions? Show that Grover's algorithm provides no advantage over random sampling in this case. What is the optimal strategy for $M > N/2$?

Exercise 13.11 — Diffusion Operator as a Reflection. Prove that the diffusion operator $D = 2|s\rangle\langle s| - I$ is both unitary and Hermitian. Show that $D$ reflects any vector about $|s\rangle$: for $|\psi\rangle = \alpha|s\rangle + \beta|s^\perp\rangle$, compute $D|\psi\rangle$ and verify that the component along $|s\rangle$ is preserved while the component along $|s^\perp\rangle$ is negated.

Exercise 13.12 — Exact Amplitude Calculation. For $N = 32$ and $M = 1$, compute the exact amplitude of the marked state after each of the first 5 Grover iterations. Express your answer as $\sin((2k+1)\theta/2)$ and verify numerically. At which iteration does the success probability first exceed 0.99?