Confirms potential for exponentially faster calculation
SAN JOSE, Calif. (August 15, 2000) -- The world's most advanced quantum computer has been developed at IBM's Almaden Research Center. Scientists then used it to show that such devices can solve problems that are impossibly hard for conventional computers.
"Quantum computing begins where Moore's Law ends -- about the year 2020, when circuit features are predicted to be the size of atoms and molecules," says Isaac L. Chuang, who led the team of scientists from IBM Research, Stanford University and the University of Calgary. "Indeed, the basic elements of quantum computers are atoms and molecules."
Quantum computers get their power by taking advantage of certain quantum physics properties of atoms or nuclei that allow them to work together as quantum bits, or "qubits," to be the computer's processor and memory. By interacting with each other while being isolated from the external environment, theorists have predicted -- and this new result confirms -- that qubits could perform certain calculations exponentially faster than conventional computers.
The new quantum computer contains five qubits* -- five fluorine atoms within a molecule specially designed so the fluorine nuclei's "spins" can interact with each other as qubits, be programmed by radiofrequency pulses and be detected by nuclear magnetic resonance instruments similar to those commonly used in hospitals and chemistry labs.
Using the molecule, Chuang's team solved in one step a mathematical problem for which conventional computers require repeated cycles. The problem is called "order-finding" -- finding the period of a particular function -- which is typical of many basic mathematical problems that underlie important applications, such as cryptography.
In particular, the order-finding problem can be described by considering a large number of rooms and an equal number of randomly placed one-way passages, some of which may loop back upon themselves into the same room. It is certain that at some point, a person moving through the rooms and passages will return to the starting room. The problem is to calculate with the least number of queries, the minimum number of passages through which one must travel through before returning to the starting room. IBM Research's 5-qubit quantum computer solved any case of the problem in one step, while a conventional approach would require up to four steps, depending on the particular case. The new result confirmed the predictions of Prof. Richard Cleve of the University of Calgary in Canada made earlier this year.
While the potential for quantum computing is huge and recent progress is encouraging, the challenges remain daunting. IBM's 5-qubit quantum computer is a research instrument. Commercial quantum computers are still many years away, since they must have at least several dozen qubits before difficult real-world problems can be solved.
"This result gives us a great deal of confidence in understanding how quantum computing can evolve into a future technology," Chuang says. "It reinforces the growing realization that quantum computers may someday be able to live up to their potential of solving in remarkably short times problems that are so complex that the most powerful supercomputers can't calculate the answers even if they worked on them for millions of years."
Chuang says the first applications are likely to be as a co-processor for specific functions, such as database lookup and finding the solution to a difficult mathematical problem. Accelerating word processing or Web surfing would not be well-suited to a quantum computer's capabilities.
Chuang will present his team's latest result today at Stanford University at the Hot Chips 2000 conference, which is organized by the Institute of Electrical and Electronics Engineers' (IEEE) Computer Society. His co-authors are Gregory Breyta and Costantino S. Yannoni of IBM-Almaden, Stanford University graduate students Lieven M.K Vandersypen and Matthias Steffen, and theoretical computer scientist Richard Cleve of the University of Calgary. The team has also submitted a technical report of their experiment to the scientific journal, Physical Review Letters.
History:
When quantum computers were first proposed in the 1970s and 1980s (by theorists such as the late Richard Feynmann of California Institute of Technology, Pasadena, Calif.; Paul Benioff of Argonne National Laboratory in Illinois; David Deutsch of Oxford U. in England., and Charles Bennett of IBM's T.J. Watson Research Center, Yorktown Heights, N.Y.), many scientists doubted that they could ever be made practical. But in 1994, Peter Shor of AT&T Research described a specific quantum algorithm for factoring large numbers exponentially faster than conventional computers -- fast enough to break the security of many public-key cryptosystems. Shor's algorithm opened the doors to much more effort aimed at realizing the quantum computers' potential. Significant progress has been made by numerous research groups around the world.
Chuang is currently among the world's leading quantum computing experimentalists. He also led the teams that demonstrated the world's first 2-qubit quantum computer (in 1998 at University of California Berkeley) and 3-qubit quantum computer (1999 at IBM-Almaden). The order-finding result announced today is the most complex algorithm yet to be demonstrated by a quantum computer.
<< *Note: Earlier this year, scientists at Los Alamos National Laboratories announced they had achieved quantum coherence in a seven-qubit molecule. While this is a necessary condition for achieving a quantum computer, they have not yet used the molecule as a seven-qubit quantum computer to solve a problem or to implement a quantum algorithm. >>
Journal
Physical Review Letters