Big Step in Quantum Searching

Penguin_99 writes "Wired.com has an article about a Lucent Technologies' Bell Labs researcher (Lov Grover) who came up with a quantum algorithm that is able to instantly search a massive database (of websites or whatever you might have) and return amazingly precise results even if the input is vague or incomplete. This particular algorithm can be used for other things besides searching for instance solving equations. Apperently this algorithm is only one of a handful of quantum algorithms in existance. The down side is that it requires a quantum computer so you are not likely to see Yahoo! using it anytime soon. Imagine a day when you do not have to wade through pages of usless websites after performing a search. "

Comments

Ahhhh....

[True ChAoS]

But if it gives out quantum results, will it mean we can know the title of a site or the URL of a site but never both at once... ;)

ChAoS

Analysis of the algorithm's uses

[Brand X]

From the Paper's Abstract:

This paper extends the quantum search class of algorithms to the multiple solution case. It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space. This yields new applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(N)) steps. By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(sqrt(N)) steps. A classical algorithm would need O(N) steps.

This is not the instant set-em-up-and-let-em-fall answer of quantum computing mythology. The algorithm is substantially faster than a linear algorithm - it would really show this in a case with a database of such size as to be unsearchable with a classic algorithm, say a very partial retinal scan against a database including every retinal print in the world - but what isn't clear is the cost in setup. I scanned the paper, but couldn't figure out how many qbits this would require. If the number grows with the database size, which is possible, this search might not be doable on a real scale. I'm sure when quantum coprocessors are commonplace, the algorithm will be widely used... I just wonder what it would take to create a situation where the quantum solution to the vague search is faster than a smarter solution on a classical computer... one that restricts enough to dump most of the searchable steps before it starts, then broadens criteria as required.