THE GREAT Quantum NUMBER CRUNCHER – research into quantum computer networks – includes related articles on quantum physics – Abstract
David H. Freedman
IF SOMEONE SUCCEEDS in building a quantum computer — and the odds of that look better every day — the information age MAY NEVER BE THE SAME.
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 dam 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 rind 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 “travelling 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.
RELATED ARTICLE: The Nuts and Bolts of Qubits, Part 1 (IF YOU REALLY MUST KNOW)
If only atoms were more cooperative. David Wineland is a member of one of the dozen or so teams of scientists who are wrestling with them in an effort to put quantum weirdness to work for the cause of faster–much, much faster–computing. Wineland and his colleagues at the National Institute of Standards and Technology use an electron beam to first strip a beryllium atom of an electron. Then they use a combination of laser beams and electromagnetic fields to hold the beryllium ion in place.
Once coaxed into this somnolent state, the ion can be tickled with another laser beam into two simultaneous quantum states–one in which the ion is vibrating at high energy, and the other in which it’s vibrating at lower energy. The mixture of the two states can be thought of as a qubit, with, for example, the low-energy state being a 0 and the high-energy state being a 1.
After working on this for some four years now, Wineland can get two or more ions side by side acting as potential qubits. Unfortunately, there isn’t really any interesting computing that can be done on a few qubits–or even a million qubits, for that matter–if the qubits aren’t linked in some way. That’s because computing logic requires that different pieces of data affect one another; for example, when two numbers are added to make a third, or a no is changed into a yes if two names match.
To achieve this sort of basic computer logic, Wineland recently added an important new wrinkle to the scheme. He uses the laser beam to cause the ions in his trap to swing rapidly back and forth in unison, creating yet another pair of superimposed quantum states: one in which the group of ions is swinging together, and the other in which they’re at rest. The trick lies in the ability of the ions to go in and out of this group jig, which affects, and is affected by, the rapid vibrations of the individual ions. Thus the vibrations of one ion might in some cases cause the group to start swinging together, which might in turn cause one of the other ions to speed up or slow down its vibrations.
Think of a van full of people in which a few of the passengers start stomping their feet. This sets the van rocking, which inspires a new person to stomp but also scares the original stompers into stopping, which stops the van from rocking. That leads new people to stomp and–voila–an odd sort of processing occurs in the form of stompers being turned on and off via the van’s rocking. In the same way, the vibrational states of the individual ions can be turned on and off via the swinging of the group, or vice versa. What’s more, the exact determination of which ions are turned on and off by the rocking, and under what conditions, can be controlled simply by applying laser beams at different energies. “This gives us a general approach to quantum logic,” says Wineland.
Well, at least in principle. In practice, Wineland has been battling a stream of problems. Some are minor, such as the tendency of lasers to fluctuate in intensity a bit too much to allow each ion to be precisely controlled. He’s also having trouble getting more than two or three ions to sit still in his trap. But a two- or even three-qubit computer won’t cut it, as with ordinary computers, it takes a lot of bits to deal with a significant amount of data. Still, Wineland predicts he’ll make big strides in both problems over the next few years. “I don’t see any fundamental roadblocks to eventually dealing with tens of ions,” he says. “Maybe hundreds.” That would be plenty to tackle some important real-world computing chores.
RELATED ARTICLE: The Nuts and Bolts of Qubits, Part 2
If any of us ever get to surf a quantum Internet, it might be because of the research of people like Jeff Kimble of Caltech. The problem most researchers encounter in trying to develop a rudimentary quantum computer is that of scaling up the number of atoms in strange quantum mechanical states that can serve as qubits–the quantum analogue of an ordinary bit of computer data. Building devices with a few qubits isn’t all that hard; building devices with the 50 or so qubits deemed necessary for solving important problems faster than conventional computers seems horrifically daunting. But what if instead of one device with 50 qubits, you hooked together five devices with ten qubits each? That’s where Kimble’s quantum network comes in.
Kimble starts with an atom trapped in two simultaneous quantum states by electromagnetic fields inside a chamber. With the right combination of electromagnetic fields, Kimble can make such an atom emit a photon of light energy that will itself be in a superimposition of different states of “polarization” –a characteristic that can very roughly be thought of as a clockwise or counterclockwise rotational orientation of the photon. And, as is necessary for quantum computing logic, changes to the state of the atom will affect the state of the photon, so that the atom and the photon can serve as a two-qubit system.
Even more important, the photon qubit can then travel on–at the speed of light, of course–to another atom, become absorbed by it, and thereby push the second atom into a qubit state. In other words, the first atom-qubit can affect a second atom-qubit via the photon-qubit, creating a three-qubit system. In principle, a chain of atom-to-photon-to-atom qubits could be fashioned this way.
Kimble proposes to create devices with perhaps a handful of qubits and then link them with fiber-optic cable. Then the atom at the end of the chain of qubits in one node can pass a photon qubit through the cable onto the first atom of the chain in the next node, in effect allowing the two short chains of qubits to operate as one longer chain. “If you can wire two nodes together quantum mechanically,” says Kimble, “you get computing capabilities that are exponentially larger than the two nodes operating independently. It’s a way big difference.” If that sounds too good to be true, just consider that a pair of ordinary numbers gives you 100 possibilities (00 through 99) and adding a second, separate pair gives you another 100 possibilities, for a total of 200. But if the two pairs can be linked into a single four-digit number, you’d have 10,000 possibilities (0000 through 9999). In essence, that’s the sort of linking that Kimble’s system would provide.
Okay, so Kimble is still struggling just to get a single atom to transfer a photon to another atom down the hall. “You’ve got to start somewhere,” he says. “Nobody knows which path will turn into the yellow brick road.”
DAVID H. FREEDMAN (“The Great Quantum Number Cruncher,” page 90), a contributing editor of DISCOVER, is the author of Brainmakers and co-author of At Large: The Strange Case of the World’s Largest Internet Invasion.
COPYRIGHT 1999 Discover
COPYRIGHT 2000 Gale Group