Implementación numérica del algoritmo de factorización de Shor

Abstract

A pesar del descubrimiento de muchos algoritmos cuánticos con gran potencial teórico, a la fecha la principal limitación de la Computación Cuántica en la práctica es la poca escalabilidad de las computadoras cuánticas. El algoritmo de factorización de Shor es uno de estos novedosos algoritmos, y permite una mejora exponencial en el costo computacional de la factorización de enteros grandes. La complejidad de la factorización utilizando computadoras clásicas es la base de la fortaleza de muchos de los sistemas criptográficos de clave pública más utilizados en la actualidad, y una potencial implementación escalable del algoritmo de Shor los volvería obsoletos. En este trabajo se presenta y desarrolla la teor´ıa para la simulación de algoritmos cuánticos en computadoras clásicas. A partir de ella, se lleva a cabo una implementación numérica para la simulación de compuertas y circuitos cuánticos, introduciendo técnicas algebraicas para reducir el número de operaciones, a la vez que se presentan versiones paralelizadas de las compuertas fundamentales. Luego, se simulan dos implementaciones distintas del algoritmo de Shor para factorizar números de n bits, que utilizan 2n + 3 y 2n + 2 qubits cada una.

Despite the discovery of many quantum algorithms with great theoretical potential, to date the main limitation of Quantum Computing in practice is the poor scalability of quantum computers. Shor’s factoring algorithm is one of these novel algorithms, and it allows an exponential improvement in the computational costs of factoring large integers. The complexity of the factoring problem using classical computers is the key to the strength of many of the most widely used public key cryptographic systems, and a potential scalable implementation of Shor’s algorithm would make them obsolete. In this work, a theory for the simulation of quantum algorithms on classical computers is presented and developed. From this, a numerical implementation that allows the simulation of quantum gates and circuits is carried out, introducing algebraic techniques to reduce the number of calculations by the time parallelized versions of the fundamental gates are presented. Then, two different implementations of Shor’s algorithm for factoring n bits numbers are simulated, with 2n + 3 and 2n + 2 qubits each.