Título: «Pruebas y análisis de algoritmos cuánticos para optimización combinatoria»
Defendida: 28 de octubre de 2025
Tesista: Adriano Mauricio Lusso
Directores: Christian N. Gimenez – Alejandro Mata Ali
Desde sus orígenes, la computación ha evolucionado tanto en sus fundamentos teóricos como en sus capacidades tecnológicas, permitiendo abordar problemas cada vez más complejos. No obstante, ciertos desafíos, como los que plantea la optimización combinatoria, continúan siendo inecientes de resolver dentro del paradigma clásico. En este contexto, la computación cuántica, y en particular algoritmos como el Algoritmo Cuántico de Optimización Aproximada (QAOA), surgen como alternativas prometedoras. Esta tesis estudia la aplicabilidad de QAOA al Problema de Reasignación de Puestos de Trabajo (JRP), un problema con relevancia industrial directa que ha sido escasamente abordado en el ámbito de la investigación desde la perspectiva de la computación cuántica. La propuesta consiste en implementar el JRP mediante QAOA y realizar simulaciones en entornos cuánticos sin ruido. Se dene un conjunto de hiperparámetros para el algoritmo y se genera una muestra representativa de 105 instancias del JRP. Luego, se establecen métricas de rendimiento para evaluar la calidad de las soluciones obtenidas y la robustez del algoritmo ante distintos escenarios. Los datos recopilados son posteriormente analizados y comparados. La motivación para explorar QAOA en este contexto es doble. Por un lado, aplicar este al- goritmo a problemas combinatorios clásicos como los de asignación permite estudiar su de- sempeño y escalabilidad bajo restricciones realistas, propias de los dispositivos NISQ (Cuánticos Ruidosos y de Escala Intermedia): cantidad limitada de bit cuánticos, circuitos poco profundos y restricciones en la cantidad de iteraciones de optimización. Por otro lado, si bien las formulaciones clásicas de JRP pueden resolverse de forma eciente, en la práctica industrial suelen abordarse con restricciones blandas, lo que complejiza el problema y reduce drásticamente la efectividad de los solucionadores clásicos. En contraste, en QAOA este tipo de restricciones pueden integrarse de manera natural gracias a su estructura variacional, evitando así los costos computacionales signicativos que enfrentan los métodos clásicos. Los resultados obtenidos muestran que QAOA es capaz de generar soluciones aproximadas de alta calidad para el JRP, alcanzando razones de aproximación promedio cercanas a 0, 9 y mejoras de ganancia de hasta un 12 %. Se observó una relación consistente entre el incremento del parámetro de profundidad p y el aumento del rendimiento, lo cual también implica una mayor cantidad de iteraciones del optimizador clásico embebido dentro de QAOA. Además, los experimentos destacan la inuencia del desbalance entre trabajadores y puestos vacantes, la efectividad de la inicialización basada en TQA, y el potencial del aprendizaje por transferencia para reducir los tiempos de optimización sin comprometer la calidad de las soluciones.
