boost quantum computing
Technology Research News
Financial advisers commonly tell investors
to diversify their portfolios in order to minimize risk. This concept
is also true in computing.
Just as multiple investments allow investors to better balance financial
risk and reward, a mix of algorithms will work better than any single
algorithm to solve computer problems that take varying amounts of time
for each attempt. In computing, the potential risk is that any given attempt
will require a lot of time, while the potential reward is a quick solution.
Researchers who previously proved this point for classical computing have
shown that the portfolio strategy will also improve the performance of
In both classical and quantum computing, the advantage of using the portfolio
strategy boils down to having a range of tools available in the face of
In classical computing, these types of problems include scheduling and
route-planning problems that require each possibility to be examined one
at a time, and Web searches and robot navigation that exist in variable
environments like the Internet or the physical world. "For an algorithm
or program that has a certain probability of executing in a given time,
many trials of that algorithm will [vary] in their finishing times," said
Bernardo Huberman, a scientist at Hewlett-Packard Laboratories.
In their previous work, the researchers identified that variance for these
hard combinatorial classical computer problems, and were able to construct
a mixture of algorithms that decreased the variability and also increased
Quantum algorithms by their nature are probabilistic, varying in unknown
ways on different problems, said Huberman. According to the researchers'
calculations, the gain in efficiency in using portfolios of quantum algorithms
is equivalent to the gain in using portfolios of classical algorithms.
In quantum computing, the length of time a program runs is set beforehand
and the question is whether it will succeed. The variability is in the
likelihood of success. Using portfolios of algorithms will improve those
chances of success.
In addition, it might be possible to use the weirdness of quantum mechanics
to further increase the efficiency by combining contributions from multiple
algorithms, said Huberman.
Quantum computing can in theory use the interactions of atoms and subatomic
particles to solve certain problems like cracking secret codes and searching
large databases much faster than the fastest classical computer possible.
Quantum particles like atoms and electrons can spin in one of two directions,
up or down. These two directions can represent the ones and zeros of digital
information. When a subatomic particle or atom is undisturbed it enters
into the weird quantum mechanical state of superposition, meaning it is
in some unknown mixture of all possible states. In superposition, the
particles spin in some mixture of up and down at the same time.
In these unknown superpositions, particles have certain probabilities
of being in any one state. Quantum algorithms run a certain number of
operations based on these probabilities. After the algorithm goes through
the given number of operations, the results are examined, which destroys
the superposition. If the computer did not find the answer during these
operations, the problem must be run all over again.
Quantum portfolios would allow the researchers to find the algorithm with
the best chance of finding the answer for a given problem and number of
Taking advantage of quantum portfolios will require practical quantum
computers, which are probably decades away. "Twenty years sounds like
a safe bet," said Huberman.
Huberman's research colleagues were Sebastian M. Maurer of Stanford University
and Tad Hogg of HP Labs. They published their research in the December
17, 2001 issue of the journal Physical Review Letters. The research was
funded by the Fannie and John Hertz Foundation and Hewlett-Packard Company.
Timeline: 20 years
Funding: Private, Corporate
TRN Categories: Quantum Computing
Story Type: News
Related Elements: Technical paper, "Quantum portfolios,"
Physical Review Letters, December 17, 2001
Tiny chain revs microdevices
Starting over speeds
nanotubes may oscillate
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link