Although practical machines lie years in the future, a formerly fanciful idea is gaining plausibility.
In Brief:
Systems in which information obeys the
laws of quantum mechanics could far exceed the performance of any conventional computer. Now that the principles of quantum computing have been demonstrated in the lab, IBM scientists are tackling the
formidable task of building machines
No matter how fast conventional computers become, there will always be some calculations that are too large
for them to complete in reasonable time. Hoping to circumvent these limitations, physicists have begun in the past few years to seriously entertain the possibility that a radically different type of computing could solve certain kinds of problems that a conventional computer could not solve in the lifetime of the universe. Called "quantum computing," it harnesses the often nonintuitive quantum properties of individual atoms and photons to store and process information.
Although it had been realized since the 1980s that quantum computers could, in theory, outperform classical machines, quantum computing was until five years ago generally considered an esoteric area of interest. Now, that perception is changing, according to Nabil Amer, who coordinates IBM Research's quantum computing efforts. "Progress has been impressive," he says. "Quantum circuits have been constructed, error-correction codes have been tested experimentally, and one kind of extremely efficient quantum algorithm -- for searching databases -- has been verified in a prototype quantum
computer."
BEYOND CLASSICAL PHYSICS
Although quantum computing is based on physical ideas elaborated in the 1920s, the recognition that quantum mechanics might be useful for computing only dawned on scientists in the 1980s. One reason is that the computers of the 1940s and '50s were built from vacuum tubes and other devices that were clearly in the macroscopic realm, suggests IBM Fellow Charles Bennett, one of the creators of the broader field of quantum information theory. Quantum concepts simply
didn't appear relevant.
Nevertheless, as physicists began to consider the physical limits of computing, they were gradually led toward the quantum arena. First, IBM Fellow Rolf Landauer discovered, in 1961, that energy is used up only during irreversible operations, ones in which information is discarded. Based on that work, Bennett showed in 1973 that fully reversible computation, which did not consume any energy, was theoretically possible. Since quantum computations also are reversible, experience gained in reversible programming in the 1970s and '80s proved useful for designing quantum algorithms.
The path toward quantum computing began in 1980, when Paul Benioff of Argonne National Laboratory published a quantum mechanical model for computation. Two years later, Richard Feynman introduced the idea that any physical system could be simulated with a quantum computer. It was David Deutsch at Oxford University who, in 1985, first produced a mathematical description of a universal quantum computer -- a machine that could be constructed out of quantum elements and would in some ways be superior to a conventional computer. But a flood of interest in the field did not emerge till 10 years later.
WHAT "BETTER" MEANS
It was the discovery of just how much more powerful a quantum computer could be that set off
the current wave of activity. In 1994, Peter Shor of AT&T Laboratories invented an algorithm
that could take advantage of quantum phenomena to factor large numbers and could hence be used,
for instance, to crack the RSA Public Key Cryptosystem, used by governments and corporations
around the world for secure communication. An important simplification of Shor's algorithm
was subsequently made by Don Coppersmith of IBM's Thomas J. Watson Research Center.
RSA is based on the idea that it is easy to multiply two large numbers to get a third, but very difficult to factor that third large number to get the first two. With conventional computers, the difficulty of finding the factors of a number is believed to increase exponentially with the number of its digits. A 250-digit number, for example, takes roughly a million times longer to factor than a 130-digit number. By making the number long enough, one can ensure that no conventional computer will factor the number in any reasonable length of time.
But Shor showed that a quantum computer could factor numbers much faster, because the number of steps it requires is proportional to the square of the number of digits. Factoring a 250-digit number is therefore only four times as hard for a quantum computer as a 130-digit one.
BETTING ON SUCCESS
Shor's results gave a tremendous boost to the nascent field of quantum computing, and
subsequently other quantum algorithms were discovered that also revealed an inherent
advantage of quantum computing for solving certain kind of problems. Such concepts,
however, could never be put to the test without a working quantum computer, and neither
Shor's nor the other algorithmic work addressed the question of whether such a machine
could ever be built. But several groups were betting that it could.
IBM was home to one of these. In the early '90s, Amer had assembled a small, informal
"alternatives for computing" group at Watson to look at what the next steps in computing might be. To get the members thinking as broadly as possible, he challenged them with the question, If God had not made silicon, how would we build computers? After examining various ideas, Amer says, "we decided to focus on quantum computing because we thought it promising and because we had a solid base of expertise in the field of quantum information."
THE WORLD OF QUBITS
What makes a quantum computer so different from -- and potentially so much more powerful than --
a conventional machine is the peculiar nature of quantum bits, or qubits. A qubit is the information
unit processed by a quantum computer. Physically, it can be represented by any quantum system that
can exist in two different states. But thanks to the very unclassical concepts of "superposition"
and "entanglement," a qubit is not limited to the values of 0 or 1.
One choice of a qubit might be an electron spinning in a magnetic field. Whenever the spin is
measured, it is always found to be either aligned with the field ("spin-up" state) or opposite to the
field ("spin-down" state). But when the electron is essentially isolated from the environment -- as
it must be in a quantum computer -- it behaves as if it were simultaneously in both up and down states,
with a discrete probability of being in the spin-up state and another probability of being in the
spin-down state. This phenomenon is known as superposition of states.
Entanglement is the other main quantum mechanical principle upon which quantum computing rests.
A pair of particles, such as two electrons with up and down spins, can be entangled --
prepared in such a way that the spin of one electron is guaranteed to be the opposite of the other's.
What makes this so strange is that, until one of the particles is measured, neither has a definite spin
direction. Yet, as soon as one is measured and found, say, to be spin up, the other will be known to be
in the spin-down state. As long as the two particles remain isolated -- no matter how far apart they may be --
they will remain entangled, and measuring the state of one will immediately provide knowledge about the state of the other.
While the probabilities of the outcome of a measurement can be calculated in advance, the actual result cannot
be known beforehand. Intuitively, one would not expect a lack of predictability to be useful for computing,
but superposition and entanglement are valuable because they generate a rapidly increasing number of states as
more qubits come into play. So, while a 2-bit classical register can be in only one of four possible binary
configurations (00, 01, 10 or 11), a quantum register consisting of two qubits can store all four numbers
at the same time, since each qubit represents two values. Adding more qubits increases the register's
capacity exponentially. A quantum computer can then perform logic operations on 2n inputs in a single
computational step. To perform the same task with a classical computer, 2n processors would have to
work in parallel, or else the computation would have to be repeated 2n times. This is the basis for what is often referred to
as quantum parallelism.
TWO BY TWO
A quantum computer is an apparatus in which the states of the qubits can be made to evolve in a deterministic way and thereby carry out a computation by operating on the qubits with quantum logic gates. At first, it was thought that to perform the logical operations, at least three qubits would have to be made to interact in a single gate, in a manner similar to a classical AND gate, which brings together two inputs to produce an output. But, while it is difficult to make two electrons or other particles approach and withdraw from one another precisely, it is virtually impossible to do so with three particles simultaneously.
Soon after Shor's algorithm was published, David DiVincenzo at Watson found a way around this problem. In what represents one of the most important steps toward a practical computer, DiVincenzo demonstrated that bringing pairs of particles together would be sufficient to carry out any logical operation, even one involving hundreds or thousands of qubits.
QUANTUM HARDWARE
Although there are many possible systems that would serve as qubits, attention has focused on a small number of promising ones.
At IBM's Almaden Research Center, two projects are currently under way to build actual quantum computers. One is based on ions,
the other on spinning nuclei.
"Ion traps" use electromagnetic forces to suspend individual ions (atoms lacking one or more electrons)
in an ultrahigh vacuum, isolating them from their environment so that the superposition of their states
can evolve and interact. Laser beams are used to switch the ion's energy levels between the 0 and 1 states
as well as to permit the ions to interact. Currently, Almaden's Ralph DeVoe is constructing a simple quantum
logic gate containing a few ions in a single trap that will provide a sophisticated tool for testing fundamental
theories of quantum computing.
Beginning in 1996, Isaac Chuang, now at Almaden, and Neil Gershenfeld of MIT's Media Lab pioneered another approach,
based on nuclear magnetic resonance (NMR) technology. This physical process -- which involves orienting and measuring
the spins of atomic nuclei in a magnetic field -- is the one that serves as the basis for medical magnetic resonance
imaging (MRI) machines.
Nuclei make almost perfect qubits, as was first pointed out by DiVincenzo in 1995.
Like electrons, they can have spin-up and spin-down states, but, in addition, the superpositions
of nuclear spin states typically last much longer than those of electron states or of most other physical systems,
thus allowing more time for quantum computation. However, such good isolation also means that large numbers of nuclei,
about 1018, are needed to be able to create an observable signal. Since these nuclei are nearly randomly oriented at
room temperature, most NMR applications never explore the quantum behavior of nuclei.
But Chuang and Gershenfeld developed a new method, using traditional NMR tools, that makes the room-temperature
nuclei behave as if they were in a very cold system, so that all the measured spins appear to be oriented in the
same direction. This permits observation of the quantum behavior of nuclear spins in molecules and hence provides
a basis for quantum computation with NMR. The new method, which uses chloroform molecules, applies two radio-frequency
pulses of different durations to control the spin states. A pulse of a certain length flips a spin from up to down,
whereas a pulse of half that duration creates a superposition state of up and down.
Calculations can be performed because the spin's evolution after the flip is influenced by the state of adjacent atoms
in the same molecule. If the adjacent atoms' nuclear spin is up, then a second half pulse, applied after an appropriate
evolution time, will flip the spin of the first nucleus down. If the adjacent nuclear spin is down, the same half pulse
will result in an up spin. This is what computer scientists term an "exclusive OR gate."
Chuang and Gershenfeld used a sequence of such pulses to implement a quantum algorithm invented by Lov Grover of Lucent
Technologies' Bell Labs. The algorithm allows databases to be searched faster than is possible with conventional techniques. For example, to find an item in a list of n entries would take a classical computer, on average, n/2 tries. Grover's algorithm on a quantum computer reduces the number of tries to the square root of n. Although Chuang and Gershenfeld's implementation involved only two qubits, it was the first time a quantum calculation of any size had been performed. It proved that quantum computing can work.
MORE QUBITS
Other groups around the world have initiated experiments in quantum computing. Caltech, Stanford, Oxford,
Los Alamos National Laboratory, the National Institute of Standards, the University of Innsbruck and the
University of California at Berkeley are developing implementations aimed at handling a few qubits. However,
to perform useful computations, quantum computers will need hundreds or thousands of qubits, each individually
addressable and readable. It is conceivable that this could be done with molecules made up of thousands of atoms,
such as polymers. A number of natural large molecules are candidates for scaling up today's primitive NMR quantum computers.
Another approach, still in the conceptual stage, aims to extend conventional silicon microprocessor technology for use in quantum
computing. First
proposed earlier this year by Daniel Loss of the University of Basel and David DiVincenzo, it has also been explored by Bruce Kane
of the University of New South Wales, among others. The basic idea is to store a qubit in the spin of single electrons trapped
in nanoscale semiconductor structures called quantum dots.
These structures behave like tiny electrical boxes, confining small numbers of electrons by surrounding
them on all sides with electric potentials generated by "impurity" atoms deposited in the silicon.
Placing a grid of electrical gates over an array of such quantum dots would enable a pair of adjacent
qubits to interact. For example, by means of a localized electric field, the electrical barrier between
the qubits could be temporarily lowered, allowing their quantum states to mingle.
Such a quantum computer design, which would operate at very low temperatures, would also need
to apply a magnetic field to each individual dot in order, for example, to flip the spins of
the electrons when needed by a calculation. An extension of this idea is to form tiny
ferromagnetic dots, surrounded by electrical barriers. When the barriers are lowered by
an imposed electric field, the electron will be able to move into the magnetic field, again for
a strictly defined amount of time. DiVincenzo has devised a similar scheme to use a magnetic material
to read out the spin of the electrons.
The actual fabrication of such a silicon-based quantum computer would pose huge technical challenges considering, among other hurdles, the requirement of accurately positioning the impurity atoms. "There are huge difficulties to be overcome, and no one can be at all sure that quantum computing will in the end do better than -- or even as well as -- transistor-based computers," cautions Landauer.
OUTLOOK HOPEFUL
Today's quantum computations are carried out at the level of two or three qubits -- a long way
from the realm of useful computing. Even so, there are reasons for optimism, Amer believes.
"Assuming no fundamental barriers to scalability," he says, "one might envision a time
when quantum computers could serve as coprocessors for conventional machines,
or even as stand-alone special-purpose computers dedicated to solving problems
that are intractable with current computer technology."
Eric J. Lerner is a freelance writer in Lawrenceville, New Jersey.
Correcting Quantum Errors
To perform useful calculations, a quantum computer has to be able to carry out a large number of intermediate steps -- trillions
in the case of factoring large numbers with several hundred digits. But any interaction with some uncontrolled, external
atom or electron introduces a slight decoherence or randomness that destroys quantum superposition and eventually makes
a quantum computer less and less reliable.
While noise, a form of randomness, is also a problem with conventional computers, techniques exist to reduce it,
and error correcting codes allow a computer to check its results and automatically fix corrupted bits. The need for
equally effective error correction in quantum computing was clarified and brought to the fore by the tireless
"friendly criticism" of Rolf Landauer, an IBM Fellow at the Thomas J. Watson Research Center.
Several groups undertook to meet the challenge, including one at Thomas J. Watson Research Center. The group,
consisting of Charles Bennett, David DiVincenzo, John Smolin and visiting scientist William Wootters from Williams College,
invented an error correction method that could, in principle, work well with qubits.
The IBM error correction scheme uses entanglement to protect quantum states from damage that they would otherwise suffer
when they are sent through a noisy channel, such as the one required for moving data around inside a quantum computer.
Instead of being used to send the valuable quantum state itself, the noisy channel is used to share the entangled pairs
of particles. Some of these are corrupted by noise, but the remaining ones can be salvaged and used in a process called
quantum teleportation, predicted by Bennett, Wootters and collaborators in 1993 and demonstrated in several laboratories
during 1998. In quantum teleportation, an entangled pair of particles is used to disembody a quantum state at the sending
location and later recreate it exactly at the receiving location, just as if it had been sent through an ideal, noiseless
channel. (See "Communicating over Quantum Channels,"
Research, Number 1, 1994.)
