Quantum Algorithms for Multiobjective Combinatorial Optimization

Abstract

This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.