Preferencias Benchmarking de QAOA en el problema de reasignación laboral: un análisis empírico utilizando aprendizaje por transferencia e inicialización de TQA
DOI:
https://doi.org/10.24215/15146774e090Palabras clave:
reasignación de puestos de trabajo, QAOA, aprendizaje por transferencia, aplicación al mundo real, benchmarking, NISQResumen
En la última década, ha habido un progreso significativo en el desarrollo de computadoras cuánticas ruidosas de escala intermedia (NISQ), aunque se necesitan más mejoras de hardware para que los algoritmos cuánticos a gran escala se ejecuten sin errores. Mientras tanto, los investigadores continúan enfocándose en el desarrollo de algoritmos efectivos para el hardware actual, con énfasis en aplicaciones a corto plazo como la optimización combinatoria. Este estudio presenta un análisis comparativo del Algoritmo de Optimización Aproximada Cuántica (QAOA) aplicado al Problema de Reasignación de Trabajos (JRP), que implica asignar n trabajadores a m trabajos vacantes para maximizar la finalización de tareas de alta prioridad y la satisfacción del trabajador. El algoritmo se combina con la inicialización de Recocido Cuántico Trotterizado (TQA) y Aprendizaje por Transferencia, lo que puede mejorar la calidad de la solución en todas las instancias. El análisis comparativo, realizado con simulación clásica sin ruido en 105 instancias de JRP, muestra resultados prometedores con razones de aproximación que van de 0,86 a 0,97. Esto supone una mejora media del 12% en la productividad organizativa gracias a una mejor asignación de tareas prioritarias y a la satisfacción de los trabajadores.
Referencias
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., Franco, N., Fratini, F., Fuller, B., Gacon, J., Gonciulea, C., Gribling, S., Gupta, S., Hadfield, S., Heese, R. y Zoufal, C. (2024). Challenges and opportunities in quantum optimization. Nature Reviews Physics, 6(12), 718–735. https://doi.org/10.1038/s42254-024-00770-9
Campos, E., Rabinovich, D., Akshay, V. y Biamonte, J. (2021). Training saturation in layerwise quantum approximate optimization. Physical Review A, 104(3), L030401. https://doi.org/10.1103/PhysRevA.104.L030401
Choi, J. y Kim, J. (2019). A tutorial on quantum approximate optimization algorithm (qaoa): Fundamentals and applications. 2019 International Conference on Information and Communication Technology Convergence (ICTC), 138–142. https://doi.org/10.1109/ICTC46691.2019.8939749
Cohen, D., Cooper, M., Jeavons, P. y Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22(1), 1–22. https://doi.org/10.1613/jair.1400
De Luca, G. (2022). A survey of nisq era hybrid quantum-classical machine learning research. Journal of Artificial Intelligence and Technology, 2(1), 9–15. https://doi.org/10.37965/jait.2021.12002
Delgado, I. P., Markaida, B. G., Ali, A. M. y de Leceta, A. M. F. (2023). Qubo resolution of the job reassignment problem. 2023 IEEE 26th International Conference on Intelligent Transportation Systems (ITSC), 4847– 4852. https://doi.org/10.1109/ITSC57777.2023.10422467
Farhi, E., Goldstone, J. y Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv, 1411.4028. https://arxiv.org/abs/1411.4028
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B. y Leymann, F. (2023). Quantum combinatorial optimization in the nisq era: A systematic mapping study. ACM Computing Surveys, 56(3), 1–36. https://doi.org/10.1145/3620668
Hadfield, S., Wang, Z., Rieffel, E. G., O’Gorman, B., Venturelli, D. y Biswas, R. (2017). Quantum approximate optimization with hard and soft constraints. Proceedings of the Second International Workshop on Post Moores Era Supercomputing, PMES'17, 15–21. https://doi.org/10.1145/3149526.3149530
Hmer, A. y Mouhoub, M. (2010). Teaching assignment problem solver. International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, 6097, 298–307. https://doi.org/10.1007/978-3-642-13025-0_32
Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83–97. https://doi.org/10.1002/nav.3800020109
Meseguer, P., Rossi, F. y Schiex, T. (2006). Soft constraints. En F. Rossi, P. van Beek y T. Walsh (Eds.), Foundations of artificial intelligence (Vol. 2, pp. 281–328). Elsevier. https://doi.org/10.1016/S1574-6526(06)80013-1
Montanez-Barrera, J., Michielsen, K. y Neira, D. E. B. (2025). Evaluating the performance of quantum process units at large width and depth. arXiv, 2502.06471. https://doi.org/10.48550/arXiv.2502.06471
Montanez-Barrera, J., Willsch, D. y Michielsen, K. (2025). Transfer learning of optimal qaoa parameters in combinatorial optimization. Quantum Information Processing, 24(5), 129. https://doi.org/10.1007/s11128-025-04743-4
Niu, M. Y., Lu, S. y Chuang, I. L. (2019). Optimizing qaoa: Success probability and runtime dependence on circuit depth. arXiv, 1905.12134. https://doi.org/10.48550/arXiv.1905.12134
Papadimitriou, C. H. y Steiglitz, K. (1998). Combinatorial optimization: Algorithms and complexity. Courier Corporation.
Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176(2), 774–793. https://doi.org/10.1016/j.ejor.2005.09.014
Powell, M. J. D. (1964). An efficient method for finding the minimum of a function of several variables without calculating derivatives. The Computer Journal, 7(2), 155–162. https://doi.org/10.1093/comjnl/7.2.155
Rajak, A., Suzuki, S., Dutta, A. y Chakrabarti, B. K. (2022). Quantum annealing: An overview. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 381(2241), 20210417. https://doi.org/10.1098/rsta.2021.0417
Sack, S. H. y Serbyn, M. (2021). Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum, 5, 491. https://doi.org/10.22331/q-2021-07-01-491
Sharma, V., Saharan, N. S. B., Chiew, S.-H., Chiacchio, E. I. R., Disilvestro, L., Demarie, T. F. y Munro, E. (2022). Openqaoa–an sdk for qaoa. arXiv, 2210.08695. https://doi.org/10.48550/arXiv.2210.08695
Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G. H. y Tennyson, J. (2022). The variational quantum eigensolver: A review of methods and best practices. Physics Reports, 986, 1–128. https://doi.org/10.1016/j.physrep.2022.08.003
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2026 Adriano Lusso, Christian Nelson Gimenez, Alejandro Mata Ali
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Aquellos autores/as que tengan publicaciones con esta revista, aceptan los términos siguientes:
- Los autores/as conservarán sus derechos de autor y garantizarán a la revista el derecho de primera publicación de su obra, el cuál estará simultáneamente sujeto a la Creative Commons Atribución-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0) que permite a terceros compartir la obra siempre que se indique su autor y su primera publicación esta revista, no hagan uso comercial de ella y las obras derivadas de hagan bajo la misma licencia.
- Los autores/as podrán adoptar otros acuerdos de licencia no exclusiva de distribución de la versión de la obra publicada (p. ej.: depositarla en un archivo telemático institucional o publicarla en un volumen monográfico) siempre que se indique la publicación inicial en esta revista.
- Se permite y recomienda a los autores/as difundir su obra a través de Internet (p. ej.: en archivos telemáticos institucionales o en su página web) antes y durante el proceso de envío, lo cual puede producir intercambios interesantes y aumentar las citas de la obra publicada. (Véase El efecto del acceso abierto).
