Eficiencia de algoritmos cuánticos para solución de problemas de enrutamiento

Abstract

Este trabajo propone un algoritmo para hayar la ruta más eficiente en una red de nodos de telecomunicaciones. Este algoritmo habitualmente conocido como problema del vendedor ambulante, se puede resolver con un algoritmo cuántico de forma más eficiente. En un trabajo de grado anterior, se propone una modificación del algoritmo de Grover de forma heurísitica y además utilizar una codificación novedosa con la intención de hacer más eficiente el algoritmo. El trabajo ha consistido en desarrollar esta idea e implementar el algoritmo para luego comprobar su funcionamiento en un número concreto de nodos, para este caso cinco. Para obtener dicho fin, se comenzó con la optimización de una parte del algoritmo de Grover, conocido como oráculo. Para ello primero se ha desarrollado una implementación en un ordenador clásico en código python, luego se ha ido transformando parte a parte a código qiskit, el cuál es una herramienta proporcionada por IBM para el manejo de computación cuántica a nivel de circuitos. El algoritmo de Grover requiere transformar los costes en fases cuánticas, que van de 0 a 2π, para eso hemos necesitado tambi-én desarrollar un programa que transforme un conjunto de costes a una distribución de fases. Tras tener implementado todo el algoritmo se puso en marcha y se testeó en diversas ocasiones para ver la capacidad de resolver un problema real, se hizo tanto en un ordenador cuántico simulado como en un ordenador cuántico real. Para implementar estas simulaciones ha sido necesario modificar la implementación convencional para que fuese capaz de poder trabajar con esta nueva codificación. Una vez implementado, se observó que en el 75 % de los casos la ruta de mayor probabilidad era también la de menor costo cuando las pruebas se hacían en un ordenador cuántico simulado. Cuando estas implementaciones se hicieron en un ordenador cuántico real, los resultados diferían de los vistos en un ordenador simulado, fallando a la hora de encontrar la ruta de menor costo. La conclusión es que el sistema opera adecuadamente en un entorno ideal. Sin embargo, al enfrentarse a las limitaciones de los prototipos utilizados en este estudio, el algoritmo no muestra eficacia.