Cálculo de logaritmos discretos en una computadora cuántica

Abstract

El presente trabajo desarrolla matemáticamente la publicación presentada por Peter Shor en 1995, donde propone un algoritmo cuántico para el cálculo de logaritmos discretos. Dicho algoritmo, ideado para ser implementado en una computadora cuántica, es exponencialmente más rápido que cualquier algoritmo clásico conocido hasta ahora. Pero ¿a qué se debe el interés en calcular eficientemente un logaritmo discreto? Se debe a que numerosos criptosistemas utilizan los logaritmos discretos como técnica para garantizar la seguridad de la información transmitida por un determinado canal. Así, muchas criptografías de clave pública, como por ejemplo el protocolo de intercambio de Diffie-Hellman, que se aplica para acordar una clave secreta entre dos máquinas, o el Algoritmo ElGamal, utilizado para autenticar firmas digitales, llegarían a ser obsoletas si el algoritmo propuesto por Shor fuera ejecutado en una computadora cuántica. Es decir, que dicho algoritmo podría ser empleado para atacar las bases de seguridad en el tránsito de la información, reduciendo drásticamente el tiempo que se necesita para descubrir numerosas claves de seguridad informática. Por otro lado, en este trabajo de tesis se plantea el desafío de mostrar al lector que la algoritmia cuántica, una ciencia que se encuentra en sus inicios, puede ser entendida sin dificultad aplicando conocimientos básicos de números complejos, álgebra lineal y probabilidad. En este sentido, y para facilitar la comprensión de los temas, se han desarrollado numerosos ejemplos que aclaran los conceptos y resultados obtenidos.