Optimizing the Number of Gates in Quantum Search

$ $Initsusualform,Grove{r}^{\mathrm{\prime }}squantumsearchalgorithmuses$O(\sqrt{N})$queriesand$O(\sqrt{N} \log N)$ other elementary gates to find a solution in an $N$-bit database. Grover in 2002 showed how to reduce the number of other gates to $O(\sqrt{N}\log \log N)$ for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to $O(\sqrt{N}{\log }^{(r)}N)$ gates for any constant $r$, and sufficiently large $N$. This means that, on average, the gates between two queries barely touch more than a constant number of the $\log N$qubitsonwhichthealgorithmacts\mathrm{.}Foraverylarge$N$ that is a power of 2, we can choose $r$ such that the algorithm uses essentially the minimal number $\frac{\pi }{4}\sqrt{N}$ of queries, and only $O(\sqrt{N}\log ({\log }^{\star }N))$ other gates.