There is a useful quantum algorithm for quantum computers discovered by Lov Grover which pertains to the problem of searching large unstructured databases. Think of this problem as having to search through a large list or table of entries (like names and phone numbers) trying to find one particular entry. Like the factoring problem, the best a classical computer can do in searching a large unstructured database for a particular item is to proceed by brute force and exhaust all the possibilities. Grover’s search algorithm, though it does not provide an exponential speedup as in the case of factoring large integers, offers a quadratic speedup in searching such databases. However, this still has practical benefits.

Consider a database consisting of N entries that needs to be searched through. It can be shown that the best known classical algorithms, on average, can find a given entry in N/2 computational steps. On the other hand, Grover’s algorithm allows this to be accomplished in √N steps on a quantum computer.

As an illustration, imagine some future quantum computer that is performing Grover’s search algorithm with a processing speed capable of performing 10⁸ computational steps per second—a realistic processing speed for classical computers. Suppose it is engaged in a particularly arduous search through a space of N = 10³⁰ entries looking for a single unique entry. How long will it take? Well, it would require √N = 10¹⁵ computational steps, which at a rate of 10⁸ steps per second, would take 10⁷ seconds, or about 4 months. Though this may seem like a long time, let us calculate how long it would take a classical computer to search through the same database with the same processing speed of 10⁸ computational steps per second. It would take N/2 = 5×10²⁹ steps and thus require 5 × 10²¹ seconds, or very nearly the age of the universe (13.7 billion years)! That is the size of the practical benefit of the quantum search algorithm over the classical. In general, the larger the search is, the larger the gain the quantum computer has over the classical.

The theoretical implications of these algorithms are even more mind-boggling, because of the way quantum computers work. In the example of Grover’s search algorithm, the quantum computer is not just doing 10¹⁵ computational steps in parallel, which can be mimicked classically by making all the computers on Earth work on nothing but this problem. The quantum computer is doing 10³⁰ possible computations in parallel every time a computational step is invoked. If all the silicon in the whole of our planet were made into microchips, and they were all set performing different computations, there would still be fewer distinct computations going on in that giant parallel computer than there would be in a single quantum computer performing Grover’s algorithm. That is a measure of the complexity, structure, and the process that exists in ordinary matter just beyond our perception since quantum processes are, of course, going on all the time everywhere. In a quantum computer, some small part of nature’s complexity is put to good use!