Big leap for quantum computing

Bad memory? Perhaps quantum computers can help. Scientists learned years ago they can use electrons as super microprocessors under very specialised conditions.

Construction of such machines is still impractical, but that hasn't stopped Luv Grover from writing quantum "software." A researcher at the famed Bell Labs, Grover Tuesday announced he'd designed a program that could allow a quantum computer to find things in a database even if researchers have only a vague notion of what they're looking for.

Nature solves problems much more efficiently than we do. Physicists are currently hard at work building machines that harness this incredible problem-solving power, and Tuesday made another major stride.

Quantum computers employ electrons and other subatomic particles -- called qubits -- in much the same way today's microchips employ tiny switches, the 0's and 1's that make up computer logic. But the atoms inside a quantum computer are much smarter than classical computer bits. They can represent 0, 1 or any number of possibilities in between. This speeds us computations exponentially - a question that would require a classical computer to take 1 million steps, a quantum computer could dispose of in, say, a mere 1,000 steps.

But there are some hitches. Quantum computers cannot be disturbed while working. The mere act of observing one can ruin the computation, a bit like ruining photographic film by looking at it while it's developing.

So the computer works privately and answers questions with almost magical abilities, spitting out an answer when it's done -- a single answer, to a problem that is known to have only one solution.

That works well when there's only one answer, as in simple mathematics problems, but it was a severe limitation on larger, less certain questions.

"There are only a few of these algorithms that work better than classical computers," said Richart Slusher, director of optical physics research at Lucent Technologies' Bell Labs. "But we haven't been at it very long, and every once in a while, we say, 'Ah, here's another one that works well.' "

That situation makes quantum computers analogous to a traditional computing system that has very little useful software written for it.

So far, the most interesting demonstrated use of a quantum computer has been to solve one of math's trickiest, but most straightfoward problems -- discovering the prime factors of a very large number.

But few real-life problems, and few statistical problems, for that matter, have only a single known result. There are often multiple correct answers -- as in a search for Internet Web pages that turns up multiple hits.

Before Grover's work, scientists didn't think quantum computers could handle the uncertainty.

"When you had one 'John Smith' you were working for, it would find it. If you had more than one, it would probably crash," Grover said.

But Tuesday at a conference in Portland, Oregon, Grover introduced a new search algorithm that proved these new-fangled machines of the future will be able to handle vague queries that result in multiple answers. Combined with the ability to perform incredibly fast searches, that would make quantum computers a powerful tool.

In the example most frequently offered by Bell Labs, it could be used to hunt quickly for the exact name and telephone number of a person whose name you can only partly recall.

"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. "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."

Finding such a person with classical brute-force searches would be at least time-consuming and at worst practically impossible. "But with my new algorithm and a quantum computer, it may be possible to rapidly carry out this search," Grover said. "[It] extends quantum search so that it can now search even when only very fuzzy information about the solution is available."

But it will be a while before Grover's "software" can be tested on a working quantum device. His initial search algorithm, which was capable of finding a single result, was published in 1996; two years later the result was tested when scientists built the first quantum machine out of 4 qubits, akin to a classical computer with only four bits.

Today, scientists have constructed machines with up to 7 qubits, Grover said, but scaling the machines to usable sizes is still years away. He wouldn't even hazard a guess as to when scientists could build 20- or 30-qubit machines, which is the minimum size required to perform useful search functions.

"But there are a number of very smart people who are very interested in this," Grover said. "Considering all the excitement, we might get there sooner."

What do you think? Tell the Mailroom. And read what others have said.