Hacia un algoritmo A* cuántico: incorporación de la heurística en caminatas cuánticas

Abstract

En el presente Trabajo se explora la posibilidad de formular una versión cuántica del algoritmo A*, ampliamente utilizado en la resolución de problemas de búsqueda y en la resolución del camino más corto/óptimo. Para ello, se propone integrar caminatas cuánticas de Szegedy y la transformada de Doob, con el fin de introducir una heurística en el procedimiento cuántico. La metodología se centra en el análisis teórico y la construcción de un esquema algorítmico que combina registros adicionales y un mecanismo de parada, integrados en un marco cuántico unitario. Los resultados muestran la viabilidad de obtener el camino más óptimo utilizando el algoritmo planteado, demostrando la viabilidad de este y su capacidad de adaptación a distintos grafos. En conclusión, se sientan las bases para un algoritmo A* cuántico, destacando tanto las ventajas como los retos de su implementación en dispositivos de la era NISQ y a futuro.