= Solution
Now try only $k_i=2^i$. Since $n^*=2^N=\Theta(1/\theta)$, the total work through trial $N$ is the <geometric series>
$$
\sum_{i=0}^N2^i=2^{N+1}-1=\Theta(n^*).
$$
For $i<N$, the success probabilities scale as
$$
p_i=\sin^2((2^{i+1}+1)\theta)
=O\left(\frac{4^i}{(n^*)^2}\right).
$$
Their 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^*$. At that trial, the defining property of $n^*$ gives
$$
p_N=\sin^2((2n^*+1)\theta)=1-O(\theta^2),
$$
so almost all surviving runs stop there. Therefore
$$
\boxed{\mathbb E C=\Theta(n^*)=\Theta(1/\theta)}.
$$
The <geometric amplitude-amplification schedule> is asymptotically better than the sequential schedule's $\Theta((n^*)^{4/3})$ calls and matches the usual Grover scaling up to a constant factor.
Back to article page
