Lucent Technologies Researcher Shows Quantum Computers Can Perform More Applications Than Previously Thought

While digital computers rely on transistors switching on and off to perform its tasks - the switch is either a 1 or a 0 - the processing units in quantum computers could simultaneously register a 0 and 1. The simultaneous nature of the processing units would allow quantum computers to tackle more complicated problems than a digital computer because a single processing unit could perform multiple calculations at the same time.

Although researchers have discussed the possibility of quantum computers since the 1970s, the first working one was announced only last month by a group of university researchers. The computer used the hydrogen and oxygen atoms from a chloroform molecule to solve a simple search problem.

Now, Lucent's Grover, who works at the company's Bell Labs, has developed a general technique for designing novel quantum mechanical applications and enhancing known applications. "The framework I'm describing can be used to enhance the results of almost any set of instructions entered into a quantum computer," said Grover, who is presenting his research findings at the Association for Computer Machinery's Symposium on the Theory of Computing.

Two years ago, Grover shook up the computing world when he proposed that a quantum computer might be able to exceed conventional computational limits. He developed a series of instructions for a quantum computer that could perform exhaustive searches. For instance, if a list contains 10,000 items, a classical computer requires 5,000 steps to find the correct item. Meanwhile, a quantum computer using the Grover Search Algorithm needs only 100 steps because the processing unit can be in multiple states at the same time and simultaneously examine multiple items. Grover describes the process in terms of wave phenomena. "All the paths leading to the desired results interfere constructively," Grover said, "and the other ones interfere destructively and cancel each other out."

At the conference, Grover will show that the Grover Search Algorithm is just one in a large category of algorithms for quantum computing. Similar techniques can be applied to a number of other important problems. One application is searching for an item when some information is known about it. This type of problem occurs in numerous applications, such as recovering a signal from a data transmission corrupted by noise.

Using a similar approach, Grover also has shown that quantum computers would be appropriate for various statistical applications, such as estimating the mean and median of a large group of numbers. In both cases, Grover's new technique is considerably faster than anything previously known with classical or quantum computing. For example, to estimate either the mean or median with an accuracy of 1 percent would require only about 100 steps on a quantum computer; a classical computer would need about 10,000 steps.

Because of the delicate nature of a quantum computer's processing units, the computers would be sensitive to outside interference, such as the smallest amount of light or noise. As a result, it is believed that any significant quantum computer would need elaborate error correction capabilities.

Grover's latest research shows that the quantum search algorithm is surprisingly robust to certain types of errors. "This is a surprising result because quantum mechanical computers derive their power through a quantum mechanical interference of all possible computational paths," Grover said. "Therefore, it is generally believed that anything affecting any of the possible computational paths will lead to incorrect answers. For the case of search-type applications, it turns out that all paths get affected in similar ways, so their interference still gives valid answers."

Lucent Technologies, headquartered in Murray Hill, N.J., designs, builds and delivers a wide range of public and private networks, communications systems and software, data networking systems, business telephone systems and microelectronic components. Bell Labs is the research and development arm of Lucent Technologies. For more information on Lucent Technologies, visit the company's web site at http://www.lucent.com.