19
$\begingroup$

What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration requires use of the reflection operation which in turn takes time $\Omega(\log(N))$ using any standard set of universal gates.

The problem is, I can't find even a single reference which says the time complexity of Grover's algorithm is $\Omega(\log(N) \sqrt{N})$. Wikipedia, and several other web pages, say $O(\sqrt{N})$ time complexity. Grover's paper claims $O(\sqrt{N})$ "steps".

Am I missing something? Perhaps people define the reflection operation to take unit time. But that doesn't make sense to me because if we can play the game of allowing arbitrary unitaries to take unit time then there would be no difference between query complexity and time complexity.

Improve this question
$\endgroup$
1
  • 11
    $\begingroup$ I can't think of a reference that talks about the time complexity of Grover's algorithm, but what you wrote is true. In fact, over any finite gate set, the operations performed between queries in Grover's algorithm require at least $\Omega(\log N)$ gates, since each gate has finite width but we need to perform a gate that affects all $\log N$ qubits. $\endgroup$
    – Robin Kothari
    Mar 29, 2013 at 22:26

2 Answers 2

Reset to default
11
$\begingroup$

The question is usually taken to be moot, for the following reason. Grover's algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate. While, yes, $\Theta(\log N)$ is the quantum gate complexity in each stage of the black-box algorithm, the predicate needs to be computed too. The quantum gate complexity of that is $\Omega(\log N)$, because otherwise it wouldn't read the whole input and you could discard some of the input bits from the search. On the other hand, an interesting predicate could take a lot more time than that. Hence, the number of calls to the predicate is taken to be the standard coin, just as it is for the classical analogue of Grover's algorithm, namely random guessing.

Improve this answer
$\endgroup$
8
$\begingroup$

Turns out that there is a way to implement Grover's algorithm with fewer than $O(\sqrt{N}\log N)$ gates! That's why you were not able to find a reference claiming that $\Omega(\sqrt{N}\log N)$ gates are needed. At least in the case where there is one marked item it is possible to do better.

A recent preprint by Arunachalam and de Wolf provides a new algorithm to solve the search problem with one marked item with query complexity $O(\sqrt{N})$ and only $O(\sqrt{N}\log(\log^* N))$ gates (from the gate set Toffoli + all one-qubit gates).

Note that the function $\log(\log^* N)$ grows so slowly that even if $N$ is the number of atoms in the universe, $\log(\log^* N)$ is at most 3.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.