Suppose you had a really stupid friend, who can remember your phone number but not your name. How long would it take him to search the phone book database, comprised of n entries, before he found you? If he were really unlucky, it would take n - 1 queries. But on average, it would take him n/2 queries, which is clearly still a demanding task. Of course, I have assumed that the search was done with classical devices. But what would happen if you exploited a quantum device to make the search? Grover of AT&T showed in 1997 that, if you took advantage of the massive parallelism within quantum mechanics, you could reduce the search to on the order of n~(1/2) queries on average. The Grover algorithm, along with remarkably few other algorithms—including Shor's famous algorithm for factoring numbers —is what has attracted so much attention to the newly emerging field of quantum computing.
展开▼
