Exercises: Grover's Algorithm

All of these run on a simulator. Solutions to starred exercises are in Answers to Selected Exercises.

Warm-up

21.1 ★ Build the phase oracle and diffuser for $n = 3$ and print both circuits. Identify the multi-controlled $Z$ inside each.

21.2 ★ Verify the diffuser implements $2|s\rangle\langle s| - I$ by comparing Operator(diffuser(3)) against the matrix built directly from $|s\rangle$.

21.3 Run Grover for $n = 4$ with one marked state at $k = 0, 1, 2, 3$ and report $P(\text{marked})$ each time. Which $k$ is best?

21.4 ★ Compute $\theta = \arcsin\sqrt{M/N}$ and $k_{\text{opt}} = \lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$ for $N = 16, 64, 256, 1024$ with $M = 1$. Confirm $k_{\text{opt}}$ grows as $\sqrt N$.

21.5 Why is the optimal success probability 0.9613 rather than 1.0? What would have to be true for it to be exactly 1?

The rotation

21.6 ★ Verify $P(k) = \sin^2((2k+1)\theta)$ against simulation for $k = 0 \dots 7$ at $N = 16$. Report the worst disagreement.

21.7 ★ Reproduce §21.4's over-rotation table. At what $k$ does the success probability first drop below the uniform $1/N$?

21.8 ★★ Plot (or tabulate) $P(k)$ for $k = 0 \dots 40$ at $N = 64$, $M = 1$. Identify every peak and confirm they occur at $(2k+1)\theta \approx \pi/2 + m\pi$.

21.9 ★★ For $N = 16$, $M = 1$, compute the ideal (non-integer) $k$ for the first three peaks and the probability at the nearest integer. Explain why later peaks give higher probability.

21.10 ★★ Write over_rotated(k, N, M) returning True when some smaller $k$ would have done better. Test it at $k = 3$ and $k = 6$ for $N = 16$, $M = 1$.

21.11 ★★★ Derive $P(k) = \sin^2((2k+1)\theta)$ from the two-reflection picture. Show that the product of the two reflections is a rotation by $2\theta$ in the plane spanned by $|\text{marked}\rangle$ and $|\text{unmarked}\rangle$.

Multiple solutions

21.12 ★ Run Grover for $M = 1, 2, 4, 8$ at $N = 16$ and report $k_{\text{opt}}$ and $P(k_{\text{opt}})$ for each. Why do more solutions need fewer iterations?

21.13 ★ Reproduce §21.5's zero-success failure: three solutions, assume $M = 1$, run $k = 3$. Report $P(\text{any marked})$.

21.14 ★★ Show the failure is exact: compute $(2k+1)\theta$ for $M = 3$, $N = 16$, $k = 3$ and express it as a multiple of $\pi$.

21.15 ★★ For $M = 3$, $N = 16$, tabulate $P(k)$ for $k = 0 \dots 6$. Which $k$ values give essentially zero, and what do they have in common?

21.16 ★★ Implement the two-run diagnostic from §21.5: run $k = 1$ and $k = 2$, and decide whether a failing search has a wrong $M$ or a broken oracle. Test it against both failure modes.

21.17 ★★ Confirm Grover cannot help at $M/N = 1/2$: tabulate $P(k)$ for $k = 0 \dots 8$ at $N = 16$, $M = 8$, and show no $k$ beats 0.5.

21.18 ★★★ Implement estimate_marked_count(n, oracle) using the $k = 1$ success probability. Test it for $M = 1 \dots 6$ at $N = 16$. Where does it become ambiguous, and why?

21.19 ★★★ Implement exponential search: try $k = 1, 2, 4, 8, \dots$, verifying each result classically, and stop on success. Show it finds a solution without knowing $M$, and measure the constant-factor overhead against knowing $M$ exactly.

The cost

21.20 ★ Using Chapter 19's oracle_cost, compute the Clifford+T cost of one Grover iteration (oracle and diffuser) at $n = 8, 12, 16$.

21.21 ★★ Reproduce §21.6's total-cost table. Then recompute it without giving the transpiler spare qubits (Chapter 19 §19.6) and report how much worse it gets.

21.22 ★★ Feed the totals to Chapter 15's resource estimator and report physical qubits and runtime for $n = 8, 12, 16$. Compare each to a classical brute-force estimate at 1 ns per check.

21.23 ★★ Solve $c_q\sqrt N = c_c N$ for $N$ given $c_q/c_c = 10^6, 10^9, 10^{12}$. Express each answer as $2^n$ and comment on which correspond to real problems.

21.24 ★★★ Estimate the fault-tolerant cost of Grover against AES-128: $2^{64}$ iterations, each containing an AES circuit. Look up a published AES T-count and report the total. Compare with Chapter 15 Case Study 1's RSA-2048 figure.

Project

21.25 ★★ (Project Checkpoint) Build vqelab/grover.py with phase_oracle, diffuser, grover_circuit, success_probability, optimal_iterations, can_succeed, run_grover returning a GroverResult, estimate_marked_count, and grover_cost. Write tests asserting:

  1. Measured probability matches $\sin^2((2k+1)\theta)$ to $10^{-9}$ for $k = 0 \dots 7$.
  2. optimal_iterations(16, 1) == 3 and optimal_iterations(16, 4) == 1.
  3. The optimal $k$ is the argmax over the first period.
  4. The optimum is not probability 1.
  5. Six iterations at $N = 16$ is below the uniform $1/16$.
  6. Over-rotation is detected, and the summary says SUSPECT.
  7. Assuming $M = 1$ when $M = 3$ gives $P < 0.001$.
  8. The correct $M$ gives $P > 0.94$.
  9. A wrong $M$ is flagged, with a warning naming the unmarked axis.
  10. estimate_marked_count recovers $M = 3$ and avoids the failure.
  11. can_succeed(16, 8) is False; can_succeed(16, M) is True for $M = 1, 2, 4$.
  12. Cost counts both oracle and diffuser.

Tests 5–7 and 9 encode this chapter's two case studies.

21.26 ★★★ Extend grover.py with amplitude_amplification(prepare, oracle, iterations), the generalization where the initial state is an arbitrary $A|0\rangle$ rather than uniform. Verify it reduces to Grover when $A = H^{\otimes n}$, and use it to boost a subroutine with success probability 0.1 to above 0.99.

Going further

21.27 ★★★ Grover is optimal: no quantum algorithm does unstructured search in $o(\sqrt N)$ queries. Read the BBBV lower-bound argument and summarize why. What assumption about the oracle does the proof require?

21.28 ★★★ Case Study 2 argues a B-tree beats Grover on sortable data. Construct a problem where the data genuinely has no exploitable structure, and verify that no classical approach beats $\mathcal{O}(N)$. How hard was it to construct?

21.29 ★★★ Quantum counting determines $M$ by running phase estimation on the Grover operator. After reading Chapter 22, implement it for $n = 4$ and compare its accuracy against estimate_marked_count's single-probability heuristic.