Algoritmo cuántico para resolver el problema de la mochila binaria en instancias de baja dimensionalidad

Abstract

Día a día los problemas que enfrenta la humanidad son más complejos, y las herramientas que nos brinda la computación clásica empiezan a ser insuficientes para resolverlos, como por ejemplo los problemas de optimización donde un espacio de búsqueda puede crecer exponencialmente; es así como los avances recientes en la investigación cuántica han llevado al desarrollo de algoritmos cuánticos experimentales que prometen resolver dichos problemas de optimización y han demostrado su superioridad ante algunos de sus análogos clásicos. En este contexto, la computación cuántica ha empezado a mostrar su dominio y en los últimos años empresas como IBM o Microsoft empiezan a ofertar servicios de cómputo cuántico para tareas de optimización y análisis de datos. Con este nuevo paradigma se podrán estudiar problemas de alta complejidad que tienen gran cantidad de operaciones y manejan gran cantidad de variables, para esto, se hace uso de algunas propiedades de la física cuántica como el entrelazamiento cuántico o la superposición cuántica, con las cuales se pueden realizar más operaciones en una misma unidad de tiempo disminuyendo radicalmente los tiempos de respuesta. Debido a que la aplicabilidad de dichos algoritmos sobre un dispositivo cuántico para muchos problemas de optimización teóricos y del mundo real, que a menudo contienen gran cantidad de restricciones, se encuentra limitada por el número actual de qubits que se han logrado integrar en un sistema físico estable, en los últimos años se han realizado estudios para tratar de aplicar algunas leyes del campo cuántico a algoritmos que funcionan sobre un sistema de computación clásico. Un problema de optimización particularmente conocido y estudiado es el problema de la mochila binaria, el cual sirve de base para dar solución a una gran variedad de problemas combinatorios complejos. Ya que se han venido desarrollando soluciones de algoritmos híbridos que incluyen componentes cuánticos, se hace necesario comprender los conceptos claves de la computación cuántica, los modelos hamiltonianos, la computación cuántica adiabática y el desarrollo actual de soluciones cuánticas que permitan obtener resultados comparables a las soluciones convencionales. Así, en este documento se detallan los pasos seguidos para construir una solución al problema de la mochila binaria utilizando un algoritmo de Computación Cuántica Adiabática haciendo uso de las librerías de Qiskit y su implementación en Python. Para validar la eficiencia del algoritmo propuesto, se realizaron experimentos con un conjunto de instancias de diversa complejidad y correlación, y se comparan los resultados de la propuesta cuántica con tres algoritmos del estado del arte. Los resultados arrojados indican que el algoritmo cuántico se encuentra al nivel del algoritmo clásico que obtuvo los mejores resultados y es más eficiente y eficaz que dos propuestas de algoritmos evolutivos. Se concluye discutiendo la viabilidad experimental del algoritmo cuántico evaluado, así como su potencial para encontrar soluciones viables y reducir los requisitos de recursos para implementar soluciones a estos problemas de optimización que permitan dirigir la búsqueda del conocimiento necesario para lograr avances en el campo de la implementación de algoritmos que integren conocimientos del área de computación cuántica y brinden un rendimiento superior a los algoritmos clásicos actuales.