Quiz: Grover's Algorithm

Answers with explanations at the end.

1. What does Grover require of its input that Chapter 20's algorithms did not — and what does it give up in exchange?

2. Is the quadratic speedup a limitation of Grover's construction or something more fundamental?

3. Write the two operators making up a Grover iteration, and say what each one reflects about.

4. Why does the diffuser cost about as much as the oracle?

5. State the exact success probability after $k$ iterations, and define $\theta$.

6. Give the optimal iteration count. Why is the resulting probability not exactly 1?

7. At $N = 16$ with one marked state, $P(3) = 0.9613$. What is $P(6)$, and why is that number alarming?

8. Explain why running Grover longer does not converge.

9. $k = 9$ gives $P = 0.9922$, beating $k = 3$'s 0.9613. Should you use $k = 9$?

10. How does the optimal iteration count change as the number of solutions increases? Give the values for $M = 1$ and $M = 4$ at $N = 16$.

11. You assume one solution, there are three, and you run $k = 3$. What is the success probability?

12. Show that the answer to question 11 is exact rather than merely small.

13. At what value of $M/N$ can Grover not help at all, and why?

14. A Grover implementation returns no successes at all across thousands of shots. Is a broken oracle or a wrong $M$ more likely? Explain the reasoning.

15. Give the two-run diagnostic that distinguishes those two failures.

16. A 20-bit Grover search costs how many T gates? What does that assume about the oracle?

17. Write the inequality determining when Grover beats classical brute force, and state the $N$ required for realistic constants.

18. Why is "Grover searches an unsorted database in $\sqrt N$ steps" false?

19. Give the criterion distinguishing problems Grover helps with from problems it does not, and two examples of each.

20. State what Grover does to symmetric-key security, and three qualifications on that claim.

Answers

1. Grover requires no promise — any predicate, any input — where Chapter 20's algorithms all needed special structure (constant-or-balanced, linear, two-to-one). In exchange the speedup is only quadratic rather than exponential.

2. Something more fundamental. Grover is optimal: no quantum algorithm does unstructured search in $o(\sqrt N)$ queries. And Aaronson–Ambainis proved that exponential speedups require promise structure, so for a total function the gap can be at most polynomial. The quadratic bound is the price of dropping the promise, not a flaw in the construction.

3. The oracle $O_f|x\rangle = (-1)^{f(x)}|x\rangle$ reflects about the solutions. The diffuser $D = 2|s\rangle\langle s| - I$ reflects about the uniform superposition. A product of two reflections is a rotation, which is the source of every behaviour in this chapter.

4. Because the diffuser is a phase oracle: $D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}$ — a multi-controlled phase flip marking $|0\dots0\rangle$, conjugated into the Hadamard basis. Both are multi-controlled operations on $n$ qubits, so both carry the same order of gate cost.

5. $P(k) = \sin^2\!\big((2k+1)\theta\big)$ with $\sin\theta = \sqrt{M/N}$, where $M$ is the number of marked states and $N = 2^n$. This is exact, verified against simulation to $10^{-15}$.

6. $k_{\text{opt}} = \lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$. It is not 1 because $k$ must be an integer, so $(2k+1)\theta$ lands near $\pi/2$ rather than on it. At $N=16$, $M=1$: $P = 0.9613$. You get a high probability and repeat if unlucky — and verifying a candidate is one classical predicate call.

7. $P(6) = 0.0204$. Alarming because it is below the $0.0625$ you started with — six iterations is worse than not running the algorithm at all.

8. Because the algorithm is a rotation, and rotations are periodic. Past the first peak you are rotating away from the marked subspace. There is no attractor and no "close enough that improves with effort" — the success probability oscillates with period set by $\theta$.

9. No. $k = 9$ lands closer to its peak (peaks occur at $(2k+1)\theta = \pi/2 + m\pi$) and gives 0.03 more probability at three times the cost. Use the first peak; $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$ is the practical rule.

10. More solutions means fewer iterations, since $k_{\text{opt}} \propto \sqrt{N/M}$. At $N = 16$: $M = 1$ needs $k = 3$; $M = 4$ needs $k = 1$ (and reaches $P = 1.0000$).

11. Exactly zero — $P = 0.0000$. Not degraded; zero.

12. With $M = 3$, $N = 16$: $\theta = \arcsin\sqrt{3/16} = 0.447832$. At $k = 3$, $(2k+1)\theta = 3.134827 = 0.9978\pi$ — almost exactly $\pi$. The state has rotated onto the unmarked axis, so $\sin^2 = 0.000046$ and every solution's amplitude is essentially zero.

13. At $M/N = 1/2$. There $\theta = \pi/4$, so reaching the peak requires $(2k+1)\theta = \pi/2$, i.e. $k = 0.5$ — and no integer number of iterations lands on it. You are stuck at the 50% you already had.

14. A wrong $M$ is far more likely. A broken oracle still marks something, and Grover amplifies whatever it marked — you get a confident wrong answer, not an empty one. A wrong $M$ rotates the state onto the unmarked axis, producing no successes at all with a distribution that looks uniform over non-solutions.

15. Run with $k = 1$ and $k = 2$. If a small $k$ succeeds and your computed $k$ does not, the oracle is fine and the iteration count is wrong. Two runs, and it eliminates the most expensive hypotheses immediately.

16. About 229,944 T gates — 804 iterations, each containing an oracle (143 T) and a diffuser (143 T). It assumes the oracle marks a single state — the cheapest possible predicate — and uses Chapter 19's favourable ancilla-based accounting. A real constraint checker is substantially larger.

17. $c_q\sqrt N < c_c N$, i.e. $\sqrt N > c_q/c_c$. With fault-tolerant T gates against classical clock cycles, $c_q/c_c \approx 10^9$–$10^{12}$, requiring $N > 10^{18}$ — a quintillion. Such problems exist (a 128-bit key space is $2^{128}$), which is why Grover's practical significance is cryptographic.

18. Because the oracle is a circuit, not a lookup. To search real data, that data must be encoded into the circuit — which means touching all $N$ records at cost $\mathcal{O}(N)$ before the $\mathcal{O}(\sqrt N)$ search begins. Total: $\mathcal{O}(N)$, and the speedup vanishes. QRAM does not rescue it: it does not exist, building it is $\mathcal{O}(N)$, and it must remain coherent for all $\sqrt N$ iterations.

19. Grover helps when the oracle is small relative to the space: $|\text{oracle}| \ll N$. Helps: hash preimage search ($2^n$ inputs, a hash circuit), symmetric key recovery ($2^k$ keys, one decryption). Does not help: database search (the oracle would be as large as the data), and any problem with exploitable structure — a B-tree gives $\mathcal{O}(\log N)$, which beats $\mathcal{O}(\sqrt N)$ exponentially.

20. It takes symmetric key strength from $2^k$ to about $2^{k/2}$ — AES-128 to roughly 64 bits, AES-256 to roughly 128 — which is the standard argument for doubling key lengths. Qualifications: (a) it parallelizes poorly, giving $\sqrt p$ from $p$ machines where classical brute force gives $p$; (b) it requires one enormous coherent computation — $2^{64}$ iterations with an AES circuit inside each; (c) it does not break AES the way Shor breaks RSA — doubling key sizes answers it completely. Use AES-256 and worry about Shor.