OPTIMIZING THE NUMBER OF GATES IN QUANTUM SEARCH

In its usual form, Grover's quantum search algorithm uses 0 (root N)queries and 0 (root 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 (root 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(root N log((r)) ) 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 pi/4 root N of queries, and only root N log(log* N)) other gates.