• Featured in Physics

Portfolios of Quantum Algorithms

Sebastian M. Maurer, Tad Hogg, and Bernardo A. Huberman
Phys. Rev. Lett. 87, 257901 – Published 27 November 2001
Physics logo
PDFExport Citation

Abstract

Quantum computation holds promise for the solution of many intractable problems. However, since many quantum algorithms are stochastic in nature they can find the solution of hard problems only probabilistically. Thus the efficiency of the algorithms has to be characterized by both 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 as 3-satisfiability.

  • Received 25 June 2001

DOI:https://doi.org/10.1103/PhysRevLett.87.257901

©2001 American Physical Society

Authors & Affiliations

Sebastian M. Maurer

  • Physics Department, Stanford University, Stanford, California 94043

Tad Hogg and Bernardo A. Huberman

  • HP Labs, Palo Alto, California 94304

See Also

Building a Quantum Portfolio

Geoff Brumfiel
Phys. Rev. Focus 8, 32 (2001)

References (Subscription Required)

Click to Expand
Issue

Vol. 87, Iss. 25 — 17 December 2001

Reuse & Permissions
Access Options

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×