Abstract
We investigate the entwined roles that additional information and quantum algorithms play in reducing the complexity of a class of global optimization problems (GOP). We show that: (i) a modest amount of additional information is sufficient to map the continuous GOP into the (discrete) Grover problem; (ii) while this additional information is actually available in some GOPs, it cannot be taken advantage of within classical optimization algorithms; and (iii) quantum algorithms offer a natural framework for the efficient use of this information resulting in a speed-up of the solution of the GOP.
| Original language | English |
|---|---|
| Pages (from-to) | 9-14 |
| Number of pages | 6 |
| Journal | Physics Letters, Section A: General, Atomic and Solid State Physics |
| Volume | 296 |
| Issue number | 1 |
| DOIs | |
| State | Published - Apr 8 2002 |
Funding
This work was partially supported by the Material Sciences and Engineering Division Program of the DOE Office of Science under contract DE-AC05-00OR22725 with UT-Battelle, LLC. We thank Drs. Robert Price, Tim Fitzsimmons, and Iran Thomas from DOE for their support. V.P. thanks Dr. Cassius D'Helon for an enlightening discussion on Chen and Diao's algorithm and for a careful reading of the manuscript.
| Funders | Funder number |
|---|---|
| Office of Science | DE-AC05-00OR22725 |