Bell Labs Researcher Devises Extremely Fast Quantum Algorithm for Intelligent Searching of Databases.

Business Editors

PORTLAND, Ore.--(BUSINESS WIRE)--May 23, 2000

A prominent quantum computing researcher at Bell Labs, the research and development arm of Lucent Technologies (NYSE:LU), has devised an extremely fast quantum algorithm that can identify an object in a large database even when the inquiry is somewhat vague.

Bell Labs scientist Lov Grover is presenting his visionary algorithm at the Association for Computing Machinery's 32nd annual Symposium on the Theory of Computing (STOC) taking place here this week. STOC is considered one of the most prestigious conferences in computer science, and Grover is the inventor of some of the most significant and powerful algorithms in the emerging field of quantum computing.

Quantum computing is a burgeoning field of research that applies concepts of quantum physics to building more efficient computers. Although only rudimentary quantum computers have been built so far, many researchers believe that quantum computing has great potential. Algorithms are sets of instructions that allow computers to perform specific tasks.

When implemented, the new algorithm by Grover would be a boon to anyone with less than perfect memory. Grover's latest algorithm uses a process called sampling that statisticians use to solve problems in the absence of perfect information. For example, it could be used to hunt quickly for the exact name and telephone number of a person one as met briefly but whose name one has half-forgotten.

"Perhaps you remember his first name was John, but you can't remember his last name, except that it was a common one such as Smith or Jones or Miller," Grover said. "You think the chance of his last name being Smith is 50 percent, while of it being Jones is 30 percent, and Miller is 20 percent. You remember that he lived near Lincoln Center in New York City, in an apartment overlooking Broadway. And you also remember that it had struck you on looking at his card that the last four digits of his telephone number were the same as those of your doctor."

Today, with this information, identifying the person might be a somewhat daunting prospect. "Save for looking through the phone book for all the John Smiths (or Joneses or Millers) who live in New York City, there is no fast and reliable way you can do it," said Grover. "But with my new algorithm and a quantum computer, it may be possible to rapidly carry out this search."

Although this example might seem contrived, these sorts of problems are very common in computer science and statistics. One immediate application is a sampling algorithm that is much faster than anything possible on a conventional computer.

"Only a handful of quantum computing algorithms exist since they are difficult to invent and the field is young," said Richart Slusher, director of optical physics research at Bell Labs. "This is another important milestone for quantum computing."

Grover is the inventor of some of the most versatile algorithms in quantum computing. Four years ago, he came up with a quantum search algorithm -- now known as the Grover Search Algorithm (GSA) -- that showed how a quantum computer could exceed the limits of conventional computing in speed. The GSA was successfully implemented in a simple quantum computer two years ago.

The GSA is a series of instructions for a quantum computer that can pinpoint a certain object in a large database very quickly, much faster than traditional computers.

For instance, if a database contains a million items, a classical computer typically requires 500,000 steps to find the correct item. A quantum computer using the GSA would need only about 1,000 steps -- a remarkable improvement in speed that becomes more and more dramatic as the size of the database increases.

In 1998, Grover extended the GSA by developing a general technique for designing novel quantum mechanical applications and enhancing known applications.

He then showed how the quantum operations in the GSA can be modified to yield different applications that can be applied to a number of other important computer science problems. Both the 1996 and 1998 algorithms required perfect information about the items one was looking for -- no fuzziness was allowed.

"The latest algorithm extends quantum search so that it can now search even when only very fuzzy information about the solution is available," Grover said. "It may lead to applications that are of even greater importance than those from the GSA."

Bell Labs is celebrating its 75th anniversary this year. One of the most innovative R&D entities in the world, Bell Labs has generated more than 40,000 inventions since 1925. It has played a pivotal role in inventing or perfecting key communications technologies for most of the 20th century, including transistors, digital networking and signal processing, lasers and fiber-optic communications systems, communications satellites, cellular telephony, electronic switching of calls, touch-tone dialing, and modems.

Bell Labs has a long history of contributions to computer science -- the UNIX operating system, and the awk, C and C++ programming languages emerged from Bell Labs. It was at Bell Labs that Peter Shor first devised the quantum computing algorithm for factorizing large numbers a few years ago. Until now, the GSA and Shor's algorithm were the only major quantum algorithms known.

Today, Bell Labs continues to draw some of the best scientific minds. With more than 30,000 employees located in 25 countries, it is the largest R&D organization in the world dedicated to communications and the world's leading source of new communications technologies. In a recent report, Technology Review magazine said Bell Labs patents had the greatest impact on telecommunications for 1999.

Lucent Technologies, headquartered in Murray Hill, N.J., U.S.A., designs and delivers the systems, software, silicon and services for next-generation communications networks for service providers and enterprises. Backed by the research and development of Bell Labs, Lucent focuses on high-growth areas such as optical and wireless networks; Internet infrastructure; communications software; communications semiconductors and optoelectronics; Web-based enterprise solutions that link private and public networks; and professional network design and consulting services. For more information on Lucent Technologies and Bell Labs, visit the company's Web site at http://www.lucent.com or the Bell Labs Web site at http://www.bell-labs.com.