Implementing Pure Adaptive Search with Grover's Quantum Algorithm
D. Bulger, W.P. Baritompa, and G.R. Wood
View Report [PDF - 164 KB]
Abstract
Pure Adaptive Search (PAS) is an idealised stochastic algorithm for unconstrained global optimisation. 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 PAS's apparent speed-up. Grover's quantum computational search algorithm provides away to generate the PAS iterates. We show that GAS realizes Pure Adaptive Search for functions satisfying certain conditions, and (when quantum computers are available) will be a practical algorithm.
Back to Research Reports
