Portfolios of Quantum Algorithms

Tad Hogg
HP Labs
USA

Quantum computers, if they can be built, will rapidly factor integers, an apparently intractable task for conventional machines. More generally, quantum computers' ability to quickly evaluate all search states in parallel seems ideal for NP problems. Unfortunately, the difficulty of exploiting this capability appears to preclude rapid worst-case search. For typical cases, recent studies suggest possible good performance with suitable choices of run time and other algorithm parameters. Instead of attempting to find a single good choice for these parameters, I'll describe how portfolios of quantum algorithms can perform better, and how they differ from portfolios of conventional algorithms. I'll also discuss ways to visualize running quantum programs (via a demo available at http://www.hpl.hp.com/research/idl/projects/quantum/demo).

For further details, see Maurer et al., Phys. Rev. Lett. 87,257901 (2001).