Sebastian Maurer, Tad Hogg and Bernardo A. Huberman
HP Laboratories
Palo Alto, CA 94304
Abstract
Quantum computation holds promise for the solution of many
intractable problems. However, since many quantum algorithms are stochastic
in nature they can only find the solution of hard
problems probabilistically. Thus the efficiency of the algorithms
has to be characterized both by the expected time to completion
and the associated variance. In order to minimize both the
running time and its uncertainty, we show that portfolios of
quantum algorithms analogous to those of finance can outperform
single algorithms when applied to the NP-complete problems such as3-SAT.
Full paper: shortqu.pdf
|
printable version
