Questions: Grover's Search Algorithm

Question 1

If Grover's algorithm is applied to a search space of N = 1,000,000 items, approximately how many oracle calls are needed?

• A. 1,000,000
• B. 500,000
• C. 1,000
• D. 785

Answer: (D)

Grover's algorithm requires approximately (pi/4)*sqrt(N) iterations. For N = 1,000,000: sqrt(1,000,000) = 1,000, and (pi/4)*1,000 ≈ 785. So roughly 785 oracle calls suffice, compared to 500,000 on average (or 1,000,000 worst case) classically. The answer '785' is the closest to the exact value.

Question 2

Applying more Grover iterations always increases the probability of finding the target — you should run as many iterations as possible.

• T. True
• F. False

Answer: False

Grover's algorithm exhibits periodic behavior. The target amplitude increases with each iteration until it reaches a maximum near 1 after approximately (pi/4)*sqrt(N) iterations, then decreases. If you overshoot and apply too many iterations, the amplitude decreases and the success probability drops. The optimal number of iterations is approximately (pi/4)*sqrt(N), and going beyond this is counterproductive. This is a crucial difference from classical search, where more work always helps.

Question 3

What are the two reflections in each Grover iteration, and how do they geometrically amplify the target state's amplitude?

Model answer: The first reflection is the oracle O, which flips the phase of the target state: O|w> = -|w> while leaving all other states unchanged. The second is the diffusion operator D = 2|s><s| - I, which reflects the state about the uniform superposition |s>. Geometrically, in the two-dimensional plane spanned by |w> (target) and |w_perp> (non-target superposition), each Grover iteration rotates the state vector by an angle of 2*arcsin(1/sqrt(N)) toward |w>. After (pi/4)*sqrt(N) iterations, the state has rotated from nearly |w_perp> to nearly |w>.

The geometric picture in the {|w>, |w_perp>} plane makes Grover's algorithm transparent. The initial state |s> makes an angle arcsin(1/sqrt(N)) with |w_perp>. Each iteration is a rotation by 2*arcsin(1/sqrt(N)). After k iterations, the angle from |w_perp> is (2k+1)*arcsin(1/sqrt(N)). Setting this equal to pi/2 gives k ≈ (pi/4)*sqrt(N). The rotation picture also explains why overshooting is harmful: past the optimal iteration count, the state rotates away from |w>.

Question 4

Grover's algorithm provides a quadratic speedup for unstructured search. Can any quantum algorithm do better for this problem?

• A. Yes — with more qubits, an exponential speedup is possible
• B. No — the BBBV theorem proves that any quantum algorithm needs Omega(sqrt(N)) queries for unstructured search
• C. Yes — using quantum error correction enables sub-quadratic query complexity
• D. It depends on the specific structure of the search space

Answer: (B)

The Bennett-Bernstein-Brassard-Vazirani (BBBV) lower bound proves that any quantum algorithm for unstructured search requires Omega(sqrt(N)) oracle queries. Grover's algorithm matches this bound and is therefore optimal. This contrasts with structured problems like factoring (Shor's algorithm) where the structure enables exponential speedups. For truly unstructured search, the best any physical theory can offer is a quadratic speedup over classical.