Grover search is Θ(√N) optimal
Theorem.Grover search is Θ(√N) optimal — T = Θ(√N) — ≈ (π/4)√N amplitude-amplification iterations reach the marked state.
Proof.Grover reaches the marked state only near (π/4)√N iterations of amplitude amplification (grover) (a tenth of that fails) — a QUADRATIC speedup with no O(log N) shortcut (BBBV); quantum search does not collapse NP.
Checked by exact arithmetic over the stated finite range — a verified witness, evidence toward the claim, not a ∀-proof.
src/9/1/index.ts#discoveredTheoremsWaveTwentySeven
1 · Classification
bounded-witness — self-contained computation, no external lean
2 · Provenance
Documented theorem re-derived by exhaustive computation (humanityNovel=false); first-in-this-registry is the only sense of discovered.
Acknowledgment
"Grover search is Θ(√N) optimal" is a re-derivation, acknowledged to documented mathematics — the original proof is the prior art this re-derivation acknowledges; not new to humanity — the contribution is the reproducible computation discoveredTheoremsWaveTwentySeven.
- Prior art
- documented mathematics — the original proof is the prior art this re-derivation acknowledges
- Novelty
- not new to humanity — a re-derivation (humanityNovel = false)
- Contribution
- a reproducible computation (discoveredTheoremsWaveTwentySeven @ src/9/1) that re-derives the result at zero tokens — the contribution is the verifiable recomputation, NOT the theorem
3 · Reproducibility
Recompute from source: npm run theorems:verify recomputes discoveredTheoremsWaveTwentySeven (src/9/1/index.ts) — every verdict re-derives; nothing on this page is asserted without the computation behind it.