Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 15E / g / Solution

The amplitude amplification success probability isChoose $k$ to be the nearest integer to $\pi /(4\theta )-1/2$. Then $(2k+1)\theta$ differs from $\pi /2$ by at most $\theta$, so $P_k\ge {\cos }^2\theta =1-p$. Since $\theta =\arcsin \sqrt{p}\sim \sqrt{p}$, this usesiterations and makes the good amplitude arbitrarily close to one when $p$ is small.

Solved by gpt-5.6-sol high.