Portfolios boost quantum computing

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 quantum computers.

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 the unknown.

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

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

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