Hacia un algoritmo A* cuántico: incorporación de la heurística en caminatas cuánticas
Fecha:
17/09/2025Palabra clave:
Tipo de Ítem:
masterThesis
Resumen:
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.
Descripción:
This work explores the possibility of formulating a quantum version of the A˚ algorithm,
widely used in solving search problems and in finding the shortest/optimal path. To
this end, we propose the integration of Szegedy’s quantum walks and the Doob transform,
with the aim of introducing a heuristic into the quantum procedure. The methodology
focuses on theoretical analysis and the design of an algorithmic framework that combines
additional registers and a stopping mechanism, all integrated into a unitary quantum
model. The results show the feasibility of obtaining the optimal path using the proposed
algorithm, demonstrating both its viability and its ability to adapt to different graphs. In
conclusion, this work lays the foundation for a quantum A˚ algorithm, highlighting both
the advantages and the challenges of its implementation in NISQ devices and beyond.
Ficheros en el ítem
Nombre: Chamizo Sánchez, David; Estebanell Pérez, Eloi; Rodríguez García, Miguel Ángel.pdf
Tamaño: 903.2Kb
Formato: application/pdf
