Quantum Enhancements for Direct Search Methods

This dissertation explores the use of quantum search algorithms to im- prove direct search methods for single and multiobjective optimization. Quantum search algorithms are known to reduce the expected number of oracle calls needed to find the solution of an unstructured search problem from O(N ) to O(√N). However, this reduction relies on the existence of a solution and these algorithms are not well equipped to determine when no solution exists. Due to their probabilistic nature, an exhaustive search is not guaranteed to occur using any finite number of oracle calls. This poses a significant hurdle when using them for direct search methods, where convergence requires accurate searches to be performed during each iteration. For those unfamiliar, we provide a brief review of quantum computing and quantum search algorithms in chapter 1. In chapter 2, we develop a classical-quantum hybrid algorithm for use within a type of direct search method called Generalized Pattern Search (GPS). These methods generate a sequence of iterates by systematically searching for a point that provides a reduced objective function value. The points chosen for consideration are determined by the outcome of the most recent search, with convergence of the algorithm requiring the search results to be accurate. We prove that our algorithm accurately identifies a point with reduced objective function value using O(√N) zeroth-order oracle calls, when one exists, otherwise correctly determining that no such point exists using O(N) oracle calls. In chapter 3, we extend the approach used in chapter 2 to the multi- objective variant of GPS called Direct MultiSearch (DMS). In this setting, the iterates of GPS are replaced with sets of non-dominated points. Iterate updates are performed by adding a candidate point to the incumbent set and removing all dominated points from the result. We prove that our algorithm accurately performs this update, identifying an element of the incumbent set that dominates the candidate point using O(√N) calls to oracles for the objective functions or identifying all elements of the incumbent set dominated by the candidate point using O(N) oracle calls.