amplitude amplification and quantum counting — one Grover rotation, two algorithms
Theorem.amplitude amplification and quantum counting — one Grover rotation, two algorithms — the search & factoring wave: in the 2D subspace {|good⟩, |bad⟩} the Grover operator (oracle · diffusion) is a rotation by 2θ with sin θ = √(M/N)..
Proof.the search & factoring wave: in the 2D subspace {|good⟩, |bad⟩} the Grover operator (oracle · diffusion) is a rotation by 2θ with sin θ = √(M/N). AMPLITUDE AMPLIFICATION uses the rotation to drive the success probability from M/N to ~1 in O(√(N/M)) steps — the state-vector Grover matches sin((2k+1)θ)² exactly at the optimal step count, generalising Grover search to any oracle. QUANTUM COUNTING measures the rotation — the operator's eigenphase is 2θ, so M = N sin²θ, and estimating the phase counts the solutions (counts 1, 2, 4 recovered from the simulated rotation). One rotation, two algorithms — one concentrates probability, the other measures the angle. Amplitude amplification overshoots if over-iterated (the O(√(N/M)) stopping point matters); the full counting reads 2θ by phase estimation; deterministic simulation, no physical speedup.
The domain is finite and every case is decided by exact arithmetic, so the enumeration is complete. ∎
src/2/8/index.ts#amplitudeAmplificationAndQuantumCounting
1 · Classification
finite-complete — 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
"amplitude amplification and quantum counting — one Grover rotation, two algorithms" 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 amplitudeAmplificationAndQuantumCounting.
- 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 (amplitudeAmplificationAndQuantumCounting @ src/2/8) 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 amplitudeAmplificationAndQuantumCounting (src/2/8/index.ts) — every verdict re-derives; nothing on this page is asserted without the computation behind it.