Building a Quantum Portfolio
Like all of quantum mechanics, most quantum algorithms deal in probabilities rather than absolutes. That element of uncertainty is beneficial because it allows a single quantum bit, or qubit, to hold many different states (like one and zero) simultaneously, but it also leads even the best quantum programs to produce an undesired result some of the time.
Another strange property of quantum computers is that checking the program’s results destroys any quantum information it contains–effectively “rebooting” the system. If the result at that stage is not useful, a programmer might have to run the program again and again before she gets a usable answer.
Because of this reboot problem, knowing when to look at a code’s output is a crucial part of quantum computing, explains Tad Hogg of Hewlett Packard (HP) Labs in Palo Alto, California. For example, suppose a program is designed to find a name in a randomized phonebook–something many researchers believe quantum computers would be especially good at. If a programmer checks the code’s output every second, she might have a low chance of finding the right name, but she would have many more opportunities than if she checked just once per hour. And her gamble could payoff if the code found the desired name in just a few tries. The decision to check and reboot is essentially an issue of risk and reward, Hogg explains.
Risk and reward are common in the stock market, so Hogg–along with colleagues from HP and Stanford University–decided to use financial portfolio management techniques to optimize two general types of quantum search code. The first algorithms they examined were supposed to pick a specific “name” out of a “phonebook” by sifting quasi-randomly through the data. By analyzing the risk and reward of checking their code at different times, the team was able to find an optimal time to check for a correct answer. They then applied the same technique to a more complex set of algorithms, ones with identical “check times” but which varied in other ways. They selected a “portfolio” of algorithms which were most efficient, though each one trades off–to varying degrees–faster performance for higher risk of getting no answer. After the portfolio is determined, a programmer could choose the algorithm from the portfolio that is best suited for a specific computing task.
Portfolios of codes can speed the process, but it may be possible to use them in still another way, says Bart Selman of Cornell University. Since the algorithm testing process involves running a portfolio of algorithms simultaneously, he explains, it might be possible to create a “quantum portfolio.” Such a portfolio would use the rules of quantum mechanics to make seemingly different algorithms interdependent upon one another, the way a pair of so-called entangled particles are related. A quantum portfolio might lead to quantum programs with even higher performance.
–Geoff Brumfiel