Home Page Overview Site Map Index Appendix Illustration About Contact Update FAQ


Quantum Computing


Searching

Searching is another hard problem that quantum computers are potentially good at solving. Only 10 quantum searches are required for searching something that could be in 100 possible places, whereas it needs 50 classical searches to find the object. In general, the number of quantum searches required to locate something is the square root of the number of places in which it could be found. This is the Grover's algorithm for searching an unsorted database with N entries in N1/2 time and using log N storage space. It was invented by Lov Grover of Bell Laboratories in 1996.

In order to exploit the symphonic nature of quantum parallelism, all parts of the quantum computation must be allowed to interfere with one another. But like writing a symphony, arranging the necessary quantum interference is tricky, so much so that there are only a few quantum algorithms, such as factoring and searching, are currently better than their classical analogs.

Go to Next Section
 or to Top of Page to Select
 or to Main Menu

.