Simulation
hints at quantum computer power
By
Eric Smalley,
Technology Research NewsPlanning 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, said Farhi.
"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
Advertisements:
May 2/9, 2001
Page One
Jolts yield nanotube transistors
Simulation hints at quantum computer power
Metal makes DNA more conductive
Etching process points to nanotech production
Plastic pins DNA molecules in place
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
