 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.