Sent: Thursday, May 25, 2000 9:11 PM
From: Jon Frisby ([email protected])
Subject: Quantum Leap in Searching
Your article on quantum computing is inaccurate and misses an important point (Quantum Leap in Computing, May 23, 2000). In the article you state that a conventional computer, when searching a 1,000,000 item database, would on average need to look at 500,000 items, whereas Grover's algorithm would only need to look at 1,000.
It is true that a linear search would result in an average of 500,000 items being looked at. But that is not how searches are conducted. If they were, Web searches – which look at billions of words within tens of millions of pages – would take hours or more for a simple search.
A more common algorithm is a binary search. This is taught to first-year computer science students in high school. A search using this technique must look at as many as 2 log n items. For 1,000,000 items, a binary search would look at no more than about 21 items.
Grover's algorithm is not fast because it looks at fewer elements. It is fast because it looks at those elements simultaneously. Assume, for thesake of simplicity, that the time necessary to look at an element is the same for a conventional computer and a quantum computer. If a computer must look at those 21 elements sequentially, but Grover's algorithm looks at 1,000 elements simultaneously, then Grover's algorithm will have completed its task in the time it took the conventional computer to look at 1 element.
However, even this is not what makes Grover's algorithm interesting. The interesting parts are the relevance factor, and the mere fact that this is a quantum algorithm.
