hints at quantum computer power
Technology Research News
Planning the best route to take for, say,
running errands seems like a fairly simple problem. But the number of
possibilities increases exponentially with each additional destination.
For 15 destinations there are billions of possible routes.
To make matters worse, there are no known mathematical shortcuts for finding
the most efficient route. Solving the problem means comparing every route.
"The number of possibilities with 500 [destinations] is huge. It's more
than astronomically big," said Edward Farhi, a professor of physics at
the Massachusetts Institute of Technology.
"If all the computers in the world were operating since the beginning
of time, they could not go through a list that long. Ordinary computers
could never find an answer to that problem by blind searching," he said.
An algorithm developed by a team of researchers based at MIT, however,
raises the tantalizing possibility that quantum
computers will be able to solve it. Route optimization is an NP-complete
problem, which is the class of problems whose solution times increase
exponentially with the size of the problem, and mathematically solving
one NP-complete problem solves them all.
An algorithm that solves this type of currently unsolvable problem would
have a wide range of practical uses, from laying out circuit boards to
scheduling flights to analyzing genes. Existing algorithms used on NP-complete
problems that have large numbers of possibilities can only provide estimates.
Researchers have proved that quantum computers will be able to crack encrypted
codes and search large, unstructured databases that are far beyond the
abilities of even the most powerful classical computers. If researchers
can prove that quantum computers will also be able to solve NP-complete
problems, they will significantly broaden the range of potential uses
for quantum computers.
The researchers simulated a quantum computer consisting of 20 quantum
bits, or qubits, on
an ordinary computer and then ran their algorithm on the simulation. They
tested the algorithm with randomly generated instances of the NP-complete
problem Exact Cover, which starts with a group of subsets of some number
of items. The subsets have the same number of items but they can overlap
each other. The problem is to find the subgroup of subsets that includes
all of the items but that has no overlapping subsets.
The running time for the algorithm increased only quadratically rather
than exponentially relative to the increase in the size of the problem.
Quadratic time is the square of the size of the problem. Exponential time
is the size of the problem to the power of three or greater. Although
the time it took the algorithm to solve the problem grew as the number
of possibilities increased, the quadratic growth rate didn't outstrip
the theoretical ability of a quantum computer to solve large instances
of the problem, according to Farhi.
The results are encouraging but far from conclusive. The researchers still
need to demonstrate that classical computers require exponentially longer
times to solve the same problem and that their quantum algorithm requires
only quadratically longer times for larger instances of the problem than
they were able to simulate. And even then, they would have only demonstrated
that the algorithm outperforms classical computers for randomly generated,
though difficult instances of the problem.
"What would really be convincing about the efficacy of our method would
be a mathematical proof. In the absence of that, I would just say we're
accumulating evidence," said Farhi.
Actually solving the problem means proving that the algorithm would work
in quadratic amounts of time for every possible instance of the problem,
"This is very interesting work," said David Meyer, a research professor
in the mathematics department at the University of California at San Diego.
"It provides some hope that quantum computers may be generally useful,
rather than only special interest." Researchers must demonstrate general
utility in order to justify the immense resources that will be required
to build quantum computers, he said.
It is possible, though not certain, that researchers will be able to determine
conclusively whether quantum computers will outperform classical computers
for NP-complete problems before actually building practical quantum computers,
said Farhi. Practical quantum computers, which require hundreds of connected
qubits, will likely take 20 years to develop, he said.
Farhi's research colleagues were Jeffrey Goldstone, Joshua Lapan, Andrew
Lundgren and Daniel Preda of MIT and Sam Gutmann of Northeastern University.
They published the research in the April 20, 2001 issue of the journal
Science. The research was funded by the Department of Energy and MIT.
Timeline: 20 years
Funding: Government, University
TRN Categories: Quantum Computing
Story Type: News
Related Elements: Technical paper, "A Quantum Adiabatic
Evolution Algorithm Applied to Random Instances of an NP-Complete Problem,"
Science, April 20, 2001
yield nanotube transistors
hints at quantum computer power
makes DNA more conductive
process points to nanotech production
pins DNA molecules in place
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link