Exercise PLAN-514

The optimal iteration count bounds Grover's single-run failure probability by 4/N; detectable failure plus geometric repetition keeps the expected oracle-query cost at order sqrt(N).

1. Failure probability equals cosine squared of (2k+1) times the half-angle.
2. The chosen k forces (2k+1) half-angles into a right-angle neighborhood.
3. Bounding the cosine gives failure at most sine squared of the full angle.
4. This is 4 sine squared(half) cosine squared(half) at most 4/N.
5. Geometric repetition with success at least 1 - 4/N gives expected queries order sqrt(N).
6. All counts are oracle queries; gate conversion is not performed.

Let the half-angle be the arcsine of one over the square root of N, so the per-iteration rotation angle is twice the half-angle. After k iterations the marked-direction amplitude is the sine of (2k+1) times the half-angle, hence the failure probability is the cosine squared of (2k+1) times the half-angle. Choosing k as the floor of (a quarter of pi over the half-angle minus one half) guarantees that (2k+1) times the half-angle is at least a right angle minus the full rotation angle and at most a right angle. Therefore the cosine of (2k+1) half-angles is at most the cosine of (a right angle minus the full rotation angle) which equals the sine of the full rotation angle. So the failure probability is at most sine squared of the full angle = four times sine squared of the half-angle times cosine squared of the half-angle, which is at most four times sine squared of the half-angle = four over N (using sine of the half-angle = one over the square root of N and cosine squared at most one). This is the claimed bound. Why the scaling survives: a single run uses order square root of N queries to the marking oracle (k is of order square root of N) and succeeds with probability at least one minus four over N. If a run fails it can be detected by classically checking the returned candidate with one more oracle query, and the procedure is repeated; the number of runs until the first success is geometric with success probability at least one minus four over N, so the expected number of runs is one over that success probability, which is one plus a vanishing correction. The expected total queries are therefore order square root of N divided by (one minus four over N) = order square root of N. By a Markov-type argument the query count is also order square root of N with probability at least two thirds. Thus the residual failure of a single run only multiplies the query cost by a factor approaching one and does not change the square-root-of-N scaling. All counts here are oracle queries; translating to elementary gates would additionally require the cost of the diffusion and oracle circuits and is not performed.

1. Writes failure probability as cosine squared of (2k+1) half-angles and uses the k choice to bound the argument near a right angle (1 weight)
2. Derives the bound failure at most sine squared of the full angle = 4 sine squared(half) cosine squared(half) at most 4/N (1 weight)
3. Gives the expected-query argument: geometric repetition with success at least 1 - 4/N yields expected queries order sqrt(N) (1 weight)
4. Keeps the accounting in oracle queries and does not silently convert to gate cost (1 weight)

No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.

Read the Lean track and existing diagnostic warmups

• website/research/sources.json

  lin-wiebe-2026-qasc

  Source SHA-256: 9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae · MIT metadata only
• Primary source

Contract: f3bb526747059fac7bcd16af26c0001dc91c8db8ec797e25cf6587e56f1e33ba

Item digest: f8f0ce53cafa5cf44f72a178c5cf657a9a3d80928242702e3db089b8f6f7b21a

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 6. This is not measured graph distance or model difficulty.