Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 324 / 3 / iv / Solution

Now try only $k_i=2^i$. Since $n^{\ast }=2^N=\Theta (1/\theta )$, the total work through trial $N$ is the geometric seriesFor $i<N$, the success probabilities scale asTheir sum is $O(1)$, so the product of their failure probabilities stays bounded away from zero: there is a constant probability of reaching the scale $k_N=n^{\ast }$. At that trial, the defining property of $n^{\ast }$ givesso almost all surviving runs stop there. ThereforeThe geometric amplitude-amplification schedule is asymptotically better than the sequential schedule's $\Theta ((n^{\ast }{)}^{4/3})$ calls and matches the usual Grover scaling up to a constant factor.