Title: Quantum basin hopping with gradient methods

Dr David Bulger

Department of Statistics - Macquarie University

This talk will describe a global optimisation method involving two well-known quantum algorithms: Grover's algorithm, and the quantum Fourier transform. As a point of departure, consider multistart with some gradient-based local optimisation (steepest descent, conjugate gradient, et cetera). That is, we repeatedly choose a random domain point x, and descend to the bottom of the "basin" containing x. When a stopping criterion is reached, we report the best point seen, which is the local minimum in the best basin we've found. Thus there are two components: a searching component (searching for the best basin) and a local optimisation component. Grover's quantum searching algorithm can find a target in effort proportional to 1/sqrt(p), where p is the target's size (the corresponding effort on a Turing computer is proportional to 1/p). Also, the quantum complexity of gradient estimation does not increase with domain dimension (the corresponding Turing complexity increases linearly with dimension). The optimisation approach discussed in this talk combines * the natural benefit of local optimisation achieved by classical multistart, * the quadratic acceleration of Grover's algorithm (loosely, a speed increase by a factor of the square root of the number of basins), and * the acceleration due to faster gradient estimation (a speed increase by a factor of the domain dimension). It is uncertain how far we can get in 50 minutes. We'll start with a quick & simple overview of quantum computation. Next we'll walk through the execution of Grover's algorithm in the simplest nontrivial case. Next we'll look at the dynamic oracle construction trick which converts Grover's algorithm to a minimisation method. Next we'll look at gradient estimation. Putting it all together may have to be left as an exercise!