It is well known now that Grover's quantum algorithm can SORT a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ operation. How does Grover's algorithm avoid reading the list? Is there a special representation that can be used classically as well? I understand any such representation will not help the classical case. However I am curious to understand how Grover avoids reading the list?

  • $\begingroup$ Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm. $\endgroup$ – Виталий Олегович Sep 19 '13 at 15:38
  • $\begingroup$ @VitalijZadneprovskij My question is different. How does Grover avoid reading the list? $\endgroup$ – 1.. Sep 19 '13 at 16:11

The list (or database) is given implicitly by an "oracle" function, which is called $\Theta(\sqrt{N})$ times throughout the algorithm. Suppose for example you're looking for a divisor of some number $N$. Then the function could map $k \leq \sqrt{N}$ to true if $k$ is a non-trivial divisor of $N$, and false otherwise. Grover's algorithm will then find a non-trivial divisor of $N$ in time $\tilde{O}(\sqrt[4]{N})$ instead of the usual $\tilde{O}(\sqrt{N})$ (note that better algorithms are available in this case, even for a classical computer).

  • $\begingroup$ Hmmm could you delve into the the oracle please? Can it be described classically and intuitively and if possible formally and mathematically? $\endgroup$ – 1.. Sep 19 '13 at 18:42
  • $\begingroup$ The oracle is an arbitrary function. When you run Grover's algorithm, you plug in the code of your oracle function into the algorithm. $\endgroup$ – Yuval Filmus Sep 19 '13 at 22:20
  • 2
    $\begingroup$ There is no quantum stuff at all. The "oracle" is just a function. Popular accounts could say that Grover's algorithm can "search a list" (certainly not sort it), but that's very misleading. It can find a solution for an equation $f(x) = 1$ for a boolean function with domain of size $N$ using $\Theta(\sqrt{N})$ applications of $f$. That's all. $\endgroup$ – Yuval Filmus Sep 20 '13 at 0:14
  • 2
    $\begingroup$ The Wikipedia article on Grover's algorithm. $\endgroup$ – Yuval Filmus Sep 20 '13 at 2:01
  • 1
    $\begingroup$ For a popular discussion of oracles for Grover's search, see web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf $\endgroup$ – Igor Markov Sep 25 '13 at 3:34

The premise of your question is faulty. Grover's algorithm can not sort a list in $O(\sqrt{N})$ time. Informally, Grover's algorithm is for searching a list, not sorting a list. Beware that "searching a list" is an informal description of what Grover's algorithm does, that should not be taken too seriously; what Grover's algorithm actually does is a little different, and you can find a good description on Wikipedia.

  • $\begingroup$ I got that from Yuval's answer. $\endgroup$ – 1.. Sep 22 '13 at 11:37
  • $\begingroup$ Do you know how long does it take to sort? $\endgroup$ – 1.. Sep 22 '13 at 11:37
  • $\begingroup$ @JAS, you should post a new question for that, as that's a totally different question. But make sure you read the help center first. $\endgroup$ – D.W. Sep 22 '13 at 15:25

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.