Behold the world's most feeble computer network: sitting in a classroom building at Caltech, it connects a grand total of two processors, crosses all of a basement corridor, and transmits a whopping single bit of information. Or would if it were working, which it isn't. "We think it would be nice if it were up and running by the new millennium," says Caltech researcher Jeff Kimble. Given the pathetic specs, it might seem just a little surprising to hear that Kimble's network is widely considered to be one of the most challenging projects in all of computer science. That's because the one bit of data his network is designed to transmit won't be an ordinary "1" or "0" of the sort that everyday networks traffic in. It will be a mixture of the two--a so-called quantum bit, or "qubit."
Kimble is trying to build the world's first quantum computer network. In a sense, he's getting a little ahead of himself, since neither he nor anyone else has yet come close to building a practical quantum computer--a computer, that is, that makes calculations on data in the weird multiple-reality state that is the hallmark of quantum mechanics. Still, the benefits of this stunningly radical approach to processing promise to be so great that the young field of quantum computing has been steadily attracting researchers not only from computer science but also from physics, math, and chemistry. Just a few years ago most computer scientists doubted that a quantum computer could ever be built. Now the tide of opinion seems to be turning, and the past year or two have seen some important advances. Neil Gershenfeld, for example, a physicist at MIT, has actually built a simple quantum computer. It can't do much--what it does is pick out one name from a list of four--but it does it faster than a conventional computer.
What's the big deal about quantum computing? Imagine you were in a large office building and you had to retrieve a briefcase left on a desk picked at random in one of hundreds of offices. In the same way that you'd have to walk through the building, opening doors one at a time to find the briefcase, an ordinary computer has to make its way more or less serially through long strings of 1's and 0's until it arrives at an answer. Of course, you could speed up the briefcase hunt by organizing a team, coordinating a floor-by-floor search, and then getting them all back together again to compare results. Ordinary computers can do this sort of thing, too, by breaking up a task and running the components in parallel on several processors. That sort of extra coordinating and communicating, however, exacts a huge toll in overhead.
But what if instead of having to search by yourself or put together and manage a team, you could instantly create as many copies of yourself as there were rooms in the building, all the versions of yourself could simultaneously peek in all the offices, and then--best of all--every copy of yourself would disappear except for the one that found the briefcase?
That's an example of how a quantum computer could work. Quantum computers would exploit the fact that under certain conditions the denizens of the atomic-scale world can exist in multiple realities--atoms and subatomic particles can be simultaneously here and there, fast and slow, pointing up and down. How? Not even physicists agree on that one, but countless experiments over the past seven decades have verified the bizarre phenomenon. By thinking of each of these different atomic states as representing different numbers or other types of data, a group of atoms with all their various combinations of potential states could be used to explore simultaneously all possible answers to a problem. And with some clever jiggling, the combination representing the correct answer could be made to stand out.
Conventional computer chips are getting so jammed with ever tinier components that they may soon hit their physical limits in power and speed; some researchers are hoping that quantum computers might break through those barriers. But although a number of research teams are struggling mightily, even the most optimistic among them don't expect to do more than demonstrate some almost uselessly simple devices within the next three years or so.
Even then, the quantum future is not guaranteed. Any computer--quantum or otherwise--can't do much good unless it can be programmed to perform a practical task. And many researchers have been wondering whether quantum computers will be able to tackle real-world computing problems--or at least run them significantly faster than conventional computers can.
Most applications actually won't lend themselves to quantum computing. That's because the typical computer task, like calculating the orbit of a satellite or rotating a graphic image, requires computer logic that proceeds in serial fashion, each step depending on the results of the preceding one. Quantum computing can't speed up that sort of task. There isn't much advantage in having multiple selves, for example, if instead of looking for a briefcase in a single room, you had to assemble a wristwatch out of parts scattered throughout all the rooms. Whether one person was to do the job or a thousand copies of that person, someone would still have to walk into each room, grab a component of the watch, and then add each piece, one at a time, in the correct order, to the wristwatch-in-progress. The desired result--in this case, a completed wristwatch--requires that every searcher does part of the job; no one's contribution can be discarded.
A suitable task for a quantum computer, in contrast, would be a problem in which one of the many possible combinations of quantum states can find and represent the answer all by itself. The other combinations, all chugging along toward wrong answers, must "collapse," as physicists put it, into the right answer. It's this selective collapsing that poses the challenge. After all, a large enough quantum computer could always be programmed to have its multiple-state atoms represent all possible answers. But what good would that do if there's no way of indicating which of the panoply of results is the right one?
Physicists have come up with a general strategy to winnow out the desired result. The approach is based on the ability of atoms to behave like waves rather than particles. Like two identical but opposite ocean waves colliding, atoms in multiple states can cancel each other out or reinforce each other, depending on how they're aligned.
Unfortunately, for a decade after the late physicist Richard Feynman first suggested the possibility of quantum computation in the early 1980s, no one could figure out a way to apply the phenomenon to a practical task. For all that time, physicists were convinced that quantum computers would be good for only one thing: making calculations about quantum mechanics. It was as if, when computer chips were first developed, their designers had announced that the only thing the chips could be used for was learning more about the electrical properties of silicon.
Then, in 1994, AT&T; researcher Peter Shor discovered the first practical chore a quantum computer might tackle. One of the more vexing problems in mathematics is the task of finding the prime-number factors of very large numbers. (Prime numbers, such as 1, 3, 5, 7, and so forth, cannot themselves be broken into smaller whole-number factors.) Shor found that this problem could be reduced to the simpler one of determining when a certain complicated mathematical sequence starts repeating itself. Identifying a repeated sequence, Shor realized, was something a quantum computer could do. Very roughly speaking, by encoding all the elements of the sequence onto the qubits, the states of the qubits that represent identical--and thus repeated--segments can be lined up to strengthen one another. After a while, these reinforced qubits wash everything else out, providing the answer. In theory, a quantum computer with 5,000 or so qubits could solve in about 30 seconds a prime-number problem that would take a conventional supercomputer 10 billion years.
Now, it just so happens there's an important application for this seemingly esoteric task. Computer data are protected from prying eyes by scrambling the characters of code that represent the data. The mathematical "key" to unscramble the data is in the form of a very large number--typically 250 digits long--and its prime factors. Such encryption is considered unbreakable because no conventional computer can figure out the prime factors of such large numbers in a reasonable amount of time. But, in theory at least, a quantum computer could blow right through these prime-number encryption schemes. A quantum computer hacker would thus have clear access not only to credit card numbers and other personal information that routinely flies around computer networks, including the Internet, but also to government and military secrets. Which explains why certain government agencies, operating on the assumption that it's better to lead than to follow, have been throwing millions of dollars at quantum computer research.
Quantum computer success wouldn't necessarily mean all our data would become unsafe. Even if computer scientists were able to defy all predictions and build a working device in the near future, cryptographers would turn to schemes that aren't based on prime numbers. One such scheme already exists. It involves coding the data in the form of the shortest distance between two secret points in an abstract, multidimensional space. No one has yet shown that a quantum computer could solve this problem.
In fact, with regard to data security, it seems that quantum computers giveth as well as taketh away. That's because a quantum computer could--theoretically--be used to encrypt data in a multiple-state form that could be read properly only by other quantum computers specifically prepared by the sender to read data from the first one. "You'd probably need only about a ten-qubit quantum computer to be useful for an encryption application," says David Wineland at the National Institute of Standards and Technology.
Not only is it unlikely that quantum computers will destroy the integrity of the Internet, but they could also end up being a huge boon to it. Two years ago Bell Labs researcher Lov Grover discovered a way to apply quantum computers to a task that many of us engage in every day: searching out information hidden away somewhere in a vast repository of data. Finding information in a database is like the finding-the-briefcase problem. If different combinations of qubit states could each take a look at a different small segment of the database, then one of the combinations of states would come across the desired information.
Grover also figured out how to cause the combination of qubit states with the right answer to stand out. Again speaking very roughly, the scheme depends on the fact that the qubit states representing "empty rooms"--that is, qubits that haven't found the desired data--are more similar to one another than they are to the qubit states with the answer, just as empty rooms more resemble one another than they do the room that holds the briefcase. Because of their similarity, the wrong qubit states can be combined in such a way as to cancel one another out. Eventually, the one set of qubit states representing the right answer remains.
Because the difference between the "right" and "wrong" qubit states is more subtle than with the prime-number problem, thus slowing the cancellation process, the speedup offered by this sort of quantum search wouldn't be as dramatic. For example, to search among 100 million addresses, a conventional computer would have to make about 50 million attempts before finding what it was looking for; a quantum computer would need some 10,000 tries. But that's still a significant improvement, and it gets bigger with larger databases. What's more, database searching is such a fundamental computer task that any improvement is likely to have an impact on a large array of applications. How would the Internet benefit? Right now, searching all publicly available Web pages for certain key words takes a few seconds (assuming you have a good connection). But remember--the Web is in its infancy. In ten years it might be thousands of times bigger, and growing, with far more people using it for far more chores. It's not hard to imagine all this activity bringing conventional computers to their silicon knees.
A number of theorists are struggling to come up with strategies for quantum software programs that will usefully solve still other sorts of problems. But with many of these strategies the process by which wrong answers cancel out is so inefficient that they would provide only a modest improvement over conventional computers. "There's a large class of problems for which quantum computers would be about twice as fast as classical computers," notes Caltech theorist John Preskill. "But we're after something sexier."
One possibility that Preskill and others are taking a close look at is a quantum program that could determine whether two complex and very different-looking graphs that connect multiple points are in fact equivalent to each other. Such a program could prove invaluable to computer chip designers, for example, who often switch components around without knowing if they've actually changed anything. Another target is the "traveling salesman" problem, which essentially involves figuring out the shortest way to connect a large number of scattered points. This problem shows up in many forms, including the challenge airlines face in serving the most cities with the fewest possible planes. A nice bonus to solving either of these problems is that they're part of a large class of mathematical problems that are believed to be related, so that cracking one of them could point the way to solving them all.
So far, few researchers are willing to predict whether quantum computing will ever go beyond a handful of applications. Still, the overall trend has been encouraging. And despite the early suspicions of many, if not most, physicists that the elusive nature of quantum mechanics would inevitably lead to the uncovering of subtle, fundamental barriers to practical quantum computing, a deep and wide-ranging theoretical search has yet to turn up a single one. "You can't predict the future growth of knowledge, but so far nothing has disappointed me," says David Deutsch, a physicist at Oxford whose proposals for quantum computation in the late 1980s were largely responsible for the field's catching fire.
Anyway, what's the big rush? The history of computing suggests that hardware and software breakthroughs tend to occur ahead of the problems they end up solving. Maybe by the time we need to search databases so large that it takes months for an ordinary computer to get through them, quantum computers will be up and running.
And that, of course, would free computer scientists to look for the next big thing.
