How does Grover's Quantum Sorting avoid reading the list?

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?

• 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. Sep 19, 2013 at 15:38
• @VitalijZadneprovskij My question is different. How does Grover avoid reading the list? Sep 19, 2013 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).

• Hmmm could you delve into the the oracle please? Can it be described classically and intuitively and if possible formally and mathematically? Sep 19, 2013 at 18:42
• The oracle is an arbitrary function. When you run Grover's algorithm, you plug in the code of your oracle function into the algorithm. Sep 19, 2013 at 22:20
• 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. Sep 20, 2013 at 0:14
• The Wikipedia article on Grover's algorithm. Sep 20, 2013 at 2:01
• For a popular discussion of oracles for Grover's search, see web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf Sep 25, 2013 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.

• I got that from Yuval's answer. Sep 22, 2013 at 11:37
• Do you know how long does it take to sort? Sep 22, 2013 at 11:37
• @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.
– D.W.
Sep 22, 2013 at 15:25