Implementing pure adaptive search with grover's quantum algorithm

D. Bulger, W. P. Baritompa, G. R. Wood

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)

Abstract

Pure adaptive search (PAS) is an idealized stochastic algorithm for unconstrained global optimization. The number of PAS iterations required to solve a problem increases only linearly in the domain dimension. However, each iteration requires the generation of a random domain point uniformly distributed in the current improving region. If no regularity conditions are known to hold for the objective function, then this task requires a number of classical function evaluations varying inversely with the proportion of the domain constituted by the improving region, entirely counteracting the PAS apparent speedup. The Grover quantum computational search algorithm provides a way to generate the PAS iterates. We show that the resulting implementation, which we call the Grover adaptive search (GAS), realizes PAS for functions satisfying certain conditions, and we believe that, when quantum computers will be available, GAS will be a practical algorithm.

Original languageEnglish
Pages (from-to)517-529
Number of pages13
JournalJournal of Optimization Theory and Applications
Volume116
Issue number3
DOIs
Publication statusPublished - Mar 2003
Externally publishedYes

Keywords

  • Discrete optimization
  • global optimization
  • Grover iterations
  • Markov chains
  • quantum computers
  • random search.

Fingerprint

Dive into the research topics of 'Implementing pure adaptive search with grover's quantum algorithm'. Together they form a unique fingerprint.

Cite this