Optimizing the Number of Gates in Quantum Search
Srinivasan Arunachalam, Ronald de Wolf · Quantum Information and Computation · 2017
In its usual form, Grover's quantum search algorithm uses $O(\\sqrt{N})$ queries and $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 every constant~$r$, and sufficiently large~$N$. This means that, on average, the circuits between two queries barely touch more than a constant number of the $\\log N$ qubits on which the algorithm acts. For a very large $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.