Computación Cuántica: el Algoritmo de Shor

Abstract

En este trabajo se presentan los conceptos preliminares y la explicación de uno de los algoritmos fundamentales de la computación cuántica: el algoritmo de Shor, que consiste en la factorización de un número entero en sus factores primos. Para ello, recordaremos conceptos básicos de álgebra lineal, así como la representación de números naturales como números binarios. También hablaremos de la importancia que presentan los números primos en el algoritmo de Shor mediante la presentación y explicación del sistema de encriptación RSA. Una vez vistos estos conceptos, explicaremos las particularidades presentes en las funciones cuánticas, así como su representación en forma de circuitos cuánticos, que nos servirán para entender la Transformada Cuántica de Fourier (QFT), una de las funciones principales de nuestro algoritmo. Finalizaremos el documento explicando paso a paso el algoritmo de Shor, ilustrándolo con un ejemplo sencillo y comentando cuestiones relacionadas con la eficiencia del mismoIn this work we are going to show the preliminary concepts and the description of one of the fundamental algorithms in quantum computation: Shor’s algorithm, which gives a factorization of an integer number into its prime factors. To do this, we will recall basic linear algebra concepts, as well as the representation of natural numbers as binary ones. We will also discuss the importance of prime numbers in Shor’s algorithm by presenting and explaining the encryptation system called RSA. After seeing these concepts, we will explain some particularities of quantum functions, as well as their representation as quantum circuits, which will help us to understand the quantum Fourier transform (QFT), one of the main functions of our algorithm. We will finish the document by explaining Shor’s algorithm step by step, illustrating it with a simple example and discussing issues related to the algorithm efficiency.