Una introducción a paseos cuánticos en gráficas

Ponente(s): Hugo Guadalupe Reyna Castañeda, María de los Ángeles Sandoval Romero

Las caminatas aleatorias en gráficas han surgido como una herramienta fundamental en ciencias de la computación, debido a su amplia aplicabilidad en el diseño y análisis de algoritmos aleatorios. Estas caminatas forman la base de numerosos algoritmos utilizados en búsqueda, toma de decisiones, resolución de problemas booleanos, optimización y muestras de distribuciones complejas, mostrando su versatilidad y poder en diversas áreas. En 1982, Richard Feynman revolucionó el campo al proponer que los principios de la mecánica cuántica podrían aprovecharse para el procesamiento de información, sentando así las bases de la computación cuántica. Este nuevo paradigma abre caminos para el desarrollo de algoritmos que podrían superar las limitaciones de los métodos clásicos. En esta charla, ofreceremos una introducción a las caminatas cuánticas en gráficos, un concepto que extiende el marco clásico al ámbito cuántico con el propósito de desarrollar técnicas generales para algoritmos cuánticos más eficientes. Esta idea fue propuesta originalmente en 1993 por Y. Aharonov, L. Davidovich y N. Zagury en su trabajo “Quantum Random Walks”. Nos enfocaremos en la construcción de caminatas cuánticas sobre algunas gráficas finitas y sus principales diferencias con respecto de sus contrapartes clásicas.