Self-Assessment Quiz: Grover's Algorithm

Twenty questions on amplitude amplification, the diffusion operator, iteration counts, optimality, and the limits of the quadratic speedup. Aim for 16+.

Question 1

Grover's algorithm searches $N$ unstructured items in:

A) $O(\log N)$ B) $O(\sqrt N)$ C) $O(N)$ D) $O(1)$ queries

Question 2

The optimal iteration count for $M$ marked items among $N$ is:

A) $\lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$ B) $\sqrt{NM}$ C) $N/M$ D) $\frac{\pi}{2}\sqrt N$

Question 3

For $N = 1024$, $M = 1$, the optimal count is about:

A) 10 B) 25 C) 32 D) 512

Question 4

The oracle in Grover marks the solution by:

A) Setting a flag bit B) Flipping the sign of the marked state's amplitude C) Measuring it D) Removing it from the superposition

Question 5

The diffusion operator is:

A) $2|s\rangle\langle s| - I$, a reflection about the uniform superposition B) A measurement C) A Hadamard on one qubit D) $I$

Question 6

Together, oracle and diffusion perform:

A) A rotation in the 2D plane spanned by the marked and unmarked states B) A projection C) A random walk D) A measurement

Question 7

Running too many iterations causes:

A) Nothing — it saturates B) The success probability to decrease (over-rotation) C) An error D) Faster convergence

Question 8

Success probability after $k$ iterations is:

A) $k/N$ B) $\sin^2((2k+1)\theta/2)$ with $\sin(\theta/2)=\sqrt{M/N}$ C) $1-1/k$ D) Constant

Question 9

If $M$ is unknown, a standard fix is:

A) Guess $M=1$ B) Exponentially increasing guesses for the iteration count, or quantum counting C) Measure all qubits first D) It is impossible

Question 10

The BBBV theorem establishes that:

A) Grover is optimal — no quantum algorithm beats $\Omega(\sqrt N)$ for unstructured search B) Grover can be improved C) Grover is classical D) Search is in P

Question 11

When $M = N/2$, Grover:

A) Works best B) Provides no advantage over random guessing C) Needs one iteration D) Fails to terminate

Question 12

Applied to AES-128 key search, Grover reduces the effective security to about:

A) 128 bits B) 64 bits C) 32 bits D) 0 bits

Question 13

The standard response to that is:

A) Abandon AES B) Use AES-256, restoring ~128-bit quantum security C) Add more rounds D) Nothing is needed

Question 14

Grover's speedup is hard to realize in practice mainly because:

A) The oracle circuit and the $\sqrt N$ sequential iterations require enormous coherent depth B) The math is wrong C) It needs too many qubits D) It cannot be simulated

Question 15

Grover's iterations must be applied:

A) In parallel B) Sequentially — each depends on the previous state C) In any order D) Once only

Question 16

True or false: Grover can be parallelized across $p$ machines for a factor-$p$ speedup.

Question 17

True or false: Grover solves NP-complete problems in polynomial time.

Question 18

True or false: Amplitude amplification generalizes Grover to boost any algorithm with success probability $p$ using $O(1/\sqrt p)$ repetitions.

Question 19

Short answer. Explain geometrically why the success probability oscillates rather than saturating.

Question 20

Short answer. A vendor claims Grover will "crack passwords instantly." Give the strongest technical rebuttal.

Answer Key

Q Ans Note
1 B Quadratic, not exponential — the most frequently overstated result in the field.
2 A Optimal iterations scale with $\sqrt{N/M}$.
3 B $\frac{\pi}{4}\sqrt{1024} = \frac{\pi}{4}\cdot 32 \approx 25.1$.
4 B A phase oracle: $|x\rangle \mapsto (-1)^{f(x)}|x\rangle$.
5 A Inversion about the mean.
6 A Two reflections compose into a rotation — the geometric heart of the algorithm.
7 B The state rotates past the target and back toward the unmarked subspace. Knowing when to stop is essential.
8 B The rotation angle grows linearly in $k$; the probability is the squared sine.
9 B Quantum counting estimates $M$ via phase estimation; alternatively, try iteration counts $1, 2, 4, 8,\ldots$ — expected cost stays $O(\sqrt{N/M})$.
10 A Proved by Bennett, Bernstein, Brassard, and Vazirani. Unstructured search admits no better than quadratic.
11 B With $\theta$ large, one iteration overshoots; you are already finding a solution half the time by guessing.
12 B $\sqrt{2^{128}} = 2^{64}$.
13 B Doubling the key length restores the margin — the reason NIST recommends AES-256 rather than a new symmetric cipher.
14 A $\sqrt N$ iterations must run coherently in sequence, each containing a full oracle. For cryptographically interesting $N$ this is an astronomically deep circuit.
15 B Strictly sequential; this is what makes the depth requirement unavoidable.
16 False Splitting the space across $p$ machines gives only $\sqrt p$ improvement, since each searches $N/p$ items in $\sqrt{N/p}$ time. Grover parallelizes badly — a serious practical disadvantage against classical brute force, which parallelizes perfectly.
17 False It gives a quadratic speedup on the search, so $2^n$ becomes $2^{n/2}$ — still exponential.
18 True Amplitude amplification is the general form; Grover is the special case with $p = 1/N$.
19 — The oracle reflects the state about the unmarked subspace; the diffusion operator reflects about the uniform superposition. The composition of two reflections is a rotation by a fixed angle $\theta$ in the plane spanned by the marked and unmarked states. Repeated application keeps rotating at a constant rate, so the component along the marked axis grows as $\sin((2k+1)\theta/2)$ — rising to 1 and then continuing past it, hence oscillation rather than saturation.
20 — Several points, in order of force: (1) the speedup is quadratic, so a 128-bit key takes $2^{64}$ sequential quantum iterations — not instant by any measure; (2) those iterations cannot be parallelized effectively, unlike classical cracking; (3) each iteration contains a full reversible implementation of the hash or cipher, costing tens of thousands of gates, so the total is ~$10^{20}$ coherent operations requiring error correction throughout; (4) doubling key length restores the original security margin at negligible cost. Grover is a real result and a poor password-cracking tool.