Análisis detallado del algoritmo de Shor en computación cuántica

Abstract

Este trabajo se enfoca en el estudio detallado del algoritmo de Shor y su implementación en el contexto de la computación cuántica. El objetivo principal es explorar este algoritmo y extraer de él estrategias y/o patrones que puedan ser aplicables a otros contextos. En particular, se hace un análisis del algoritmo de estimación de fase cuántica (QPE) como una herramienta fundamental para la obtención de la periodicidad en funciones complejas, como la exponencial modular. Se presenta además una adaptación del QPE para explorar la periodicidad en la secuencia de Fibonacci modulada; función escogida principalmente por su amplia implicación en diversas áreas científicas y tecnológicas. Así, son revelados resultados interesantes sobre la aplicabilidad del algoritmo de Shor más allá de su uso en factorización de enteros. Mediante simulaciones utilizando el software Qiskit, se demuestra que el QPE es capaz de identificar correctamente el periodo de la secuencia de Fibonacci bajo ciertos módulos. Sin embargo, la identificación resulta fallida para el resto de consideraciones, lo que presenta una posible limitación o sesgo en el algoritmo. Debiéndose esta a la falta de optimización del circuito o a la ineficacia de la estructura propuesta. Finalmente, se discuten posibles optimizaciones del algoritmo y se proponen líneas de investigación a seguir para profundizar en la identificación de la eficacia y las limitaciones del algoritmo.

This paper focuses on the detailed study of Shor’s algorithm and its implementation in the context of quantum computing. The main objective is to explore this algorithm and to extract strategies and/or patterns from it that can be applicable to other contexts. In particular, an analysis is made of the quantum phase estimation (QPE) algorithm as a fundamental tool for obtaining periodicity in complex functions, such as the modular exponential. An adaptation of the QPE to explore periodicity in the modulated Fibonacci sequence is also presented; function selected mostly due to its ample implication in various scientific and technological areas. Thus, revealing interesting results on the applicability of Shor’s algorithm beyond its use in integer factorisation. Through simulations using the Qiskit software, it is shown that the QPE is able to correctly identify the period of the Fibonacci sequence under certain moduli. However, the identification fails for the rest of the considerations, which presents a possible limitation or bias in the algorithm. Caused by the lack of optimisation of the circuit or the inefficiency of the proposed structure. Finally, we discuss possible optimisations of the algorithm and propose lines of research to follow in order to further identify the effectiveness and limitations of the algorithm.