RT Generic
T1 Quantum Algorithms for Multiobjective Combinatorial Optimization
A1 Fogel Lezcano, Gerardo Gabriel
AB 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 optimizationproblems 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.
PB FP-UNA
YR 2017
FD 2017
LK http://hdl.handle.net/20.500.14066/3110
UL http://hdl.handle.net/20.500.14066/3110
LA eng
NO CONACYT - Consejo Nacional de Ciencia y Tecnología
DS MINDS@UW
RD 21-nov-2024