7 March 2000
Source:
http://www.nytimes.com/library/national/science/030700sci-quantum-computing.html
By SARA ROBINSON
BERKELEY, Calif. -- Six years ago, Dr. Peter Shor, a researcher at AT&T Labs, galvanized an obscure area of computer science when he published a recipe by which a computer based on the principles of quantum mechanics could break the cryptographic codes protecting data transmissions over the Internet.
Since then, top researchers around the world have joined forces to further explore how the power of the strange rules that prevail in the submicroscopic realm of the atom can be harnessed in a computer.
Many government and corporate research labs like Microsoft Research, International Business Machines and AT&T Labs, either already have a quantum computing group, or, like NASA's Ames Research Center and the Hewlett-Packard Corporation, are thinking of starting one.
An ambitious group in New York has even begun a quantum computing start-up, called MagiQ Technologies, with a stated goal of building a "quantum Internet."
At a weeklong quantum computing conference last month at the Mathematical Sciences Research Institute here, researchers from universities and corporate labs gathered to discuss advances in the field.
Talks centered on algorithms for quickly solving problems thought infeasible for "classical" computers, understanding the limits of the computational power of quantum computers, various approaches to building a practical device and methods for correcting computational errors.
The week culminated in a series of presentations to the Information Technology Office of the Defense Department's funding agency, which is considering a program for financing quantum computing research.
But even as the participants celebrated the advances in this technology, which go far beyond speculations of just a few years ago, they acknowledged that researchers were still far from understanding either the potential or the limits of the technology and even further from building a practical device.
Even so, some of the researchers said they were lured to the field, not by the possibility of a quantum computer on every desktop, but as a gateway to a better understanding of the bizarre world of quantum physics.
An ordinary or "classical" computer stores information in units called bits (0's or 1's), typically represented by electrical currents or voltages that are either high or low. A quantum computer, however, stores information by using the states of elementary particles.
Classically, the electron in a hydrogen atom, say, can be in a high or low energy state. But in the weird world of quantum physics the state of the electron is not just high or low but a weighted combination of both simultaneously: what physicists call a "superposition" of states. As a result, a quantum bit in some sense contains more information than its classical counterpart.
More important, as the number of quantum bits grows, the amount of information required to describe it grows exponentially. Classically, since each electron can be in one of two states, a system of 200 hydrogen atoms will be in one of 2200 states. Quantum theory, however, says that the system at any moment is in a superposition of all of those 2200 possibilities at once. Because 2200 is a huge number, far larger than the estimated number of particles in the universe, scientists question how the universe can manage to even keep track of its own natural processes. But the fact that it can hints at an enormous resource for computing power.
"For a tiny system of 200 atoms, it is as though nature must keep 2200 pieces of scratch paper on the side, each with a number written on it," said Dr. Umesh Vazirani, a professor of computer science at the University of California at Berkeley and a co-organizer of the conference.
But this vast storehouse of information is difficult to tap. According to the theory of quantum mechanics, a scientist cannot look at an electron without jarring it out of its delicate superposition and collapsing it into a single one of its two classical states according to the weights. The challenge of devising quantum algorithms for solving problems is to harness this vast and hidden information processing power despite the inability to access all of it.
Despite their potential power, Dr. Shor said in his presentation, quantum computers will not necessarily perform all tasks more quickly than classical computers. A working quantum computer, he said, is likely to perform each operation more slowly than a classical computer.
Only for certain problems where researchers have discovered methods of exploiting this vast pool of stored information to extract an answer in far fewer steps -- methods impossible on a classical computer -- will it be possible to speed up the computation. Examples of this are Dr. Shor's algorithm for factoring numbers into their prime components, a process that enables the cracking of codes, and an algorithm by Dr. Lov Grover, a Bell labs researcher, for searching a very specialized type of database.
Many researchers, including Dr. Shor, are trying to find quantum algorithms for other problems, believed to be beyond the reach of classical devices. Others are working on quantum cryptographic schemes to replace existing schemes in case a practical device is built.
Dr. Vazirani's presentation highlighted research on the limits of quantum computers. For example, Dr. Grover's algorithm allows a database to be searched in the square root of the time required by a classical computer.
This square root speed-up is the best that can be achieved, according to work by Dr. Vazirani and others. Their result suggests, he said, that the hardest problems in computing may forever be beyond the reach of quantum computers. Dr. Vazirani pointed out, however, that such limits might be a blessing in disguise because it raises hopes that new crytosystems can be developed that quantum computers cannot break.
Dr. Isaac Chuang, a physicist at the I.B.M. Almaden Research Center in San Jose, Calif., described several competing technologies for a working computer. In one of those, he reported, researchers have managed to perform Dr. Grover's database search algorithm using as many as four quantum bits. All the proposals, however, face difficulties in scaling up to a practical device.
"The main challenge in building a quantum computer," Dr. Chuang said, "is that you want to isolate it from everything in the external world, yet, at the same time, be able to manipulate it at high speed."
A major difficulty with running a quantum computer, the experts say, is correcting the errors that build up during a calculation. States stored in memory will get jostled inadvertently, for example, and operations will be applied to the wrong quantum bit.
Dr. Daniel Gottesman, of Microsoft Research, reviewed techniques for correcting some of the errors that occurred while computations were in progress. Beginning with a startling breakthrough by Dr. Shor and colleagues, he said, researchers have outlined how to restore quantum states that have been stored in memory but have partly collapsed due to inadvertent observations.
In addition, research by Dr. Gottesman and others has shown that errors in the computations themselves can also be corrected, as long as there are not very many of them. He and others are trying to develop error correction techniques that are more efficient and that can accommodate larger numbers of errors.
These researchers seem not to be disheartened by the many barriers to a desktop quantum computer.
"What is the value of a newborn baby?" asked Richard Josza, a professor of computer science at the University of Bristol in England. "Now, it can't do anything. But the potential is limitless."
Copyright 2000 The New York Times Company