March 2003

Harnessing Quantum Bits

Continued from page 2

By Michael Hiltzik

Beyond Secure Codes

at the same time, shor's work provoked a surge of interest in other possible applications of quantum computing. "After the first result from Shor," says computer scientist Wim van Dam of HP Labs, "everybody was very optimistic that we'd find lots and lots of algorithms" for which quantum computing would be useful. But through most of the 1990s, such "killer apps" remained elusive. For a time, scientists feared that the factoring problem would be quantum computing's only payoff.

In the last two years, however, an improved understanding of how qubits work has stimulated a new search for problems qubits are particularly well suited to solve. Edward Farhi of the Center for Theoretical Physics at MIT is among those who have undertaken that work. "The whole focus of our interest," Farhi says, "is if you had a perfectly functioning quantum computer, what would you do with it?"

Farhi and his colleagues have identified a range of general, if abstract, computations quantum computers can complete far faster than classical computers. One is a navigation problem in which a traveler with neither map nor guide moves from starting point to destination via random paths that branch from a given number of way stations. Surprising nobody, Farhi's team showed that under such conditions, the time a classical computer requires to find a way from point A to point B expands exponentially as the number of branching points between A and B increases. In contrast, a quantum computer would travel all possible paths at once, reliably finding its way across the maze in a time frame that expands only arithmetically with the complexity of the maze.

"I'm kind of pleased with this thing even though it's a bit artificial," Farhi says. What distinguishes Farhi's problem from the famous "traveling salesman" problem and other logistical conundrums is that the traveler has no map and therefore only limited knowledge of the pathway. But in the real world, a traveler is likely to have a map showing all possible paths, and the challenge is to find the most efficient route. All a quantum computer does is traverse all paths at once to quickly arrive at the destination-but it won't produce a particular route. So it isn't yet clear whether or not Farhi's work points to a practical application. "This is a steppingstone to a better example," Farhi says hopefully. "I guess you could say we're looking for areal-world example."

A more likely use of quantum computing may be in database searches. In 1996 Lov Grover, a physical-sciences researcher at Lucent Technologies' Bell Labs, developed an algorithm that showed how quantum computing could vastly accelerate searches: A classical computer searching a phone book with, say, one million entries would average some five hundred thousand tries to find a single specified phone number. A quantum computer would need only one thousand tries.

"The point is," Farhi says, "quantum speedup is not universal. So finding problems for which it's advantageous is an art."