Un poco de computación cuántica: Algoritmos más comunes

Guillermo Morales-Luna
Centro de Investigación y Estudios Avanzados del IPN
(CINVESTAV-IPN)
gmorales@cs.cinvestav.mx

El presente escrito constituye una introducción a la computación cuántica, es más bien un cursillo ``tutorial'' y el único reclamo de originalidad es la de su presentación. De hecho, ha sido grande la tentación de sutituir el adjetivo ``cuántica'' en ``computación'' por la frase adjetival ``paralela basada en álgebra exterior''. Nuestra presentación deja de lado la discusión sobre la plausibilidad de la computación cuántica y las nociones inherentes de la física cuántica involucradas. Aquí sólo nos concentraremos en presentar este paradigma como uno abstracto de cómputo y en él presentamos sus funciones primitivas, los esquemas de composición y la codificación de entradas y salidas. Nos basamos en planteamientos ortodoxos de álgebra exterior y utilizamos una notación más acorde con esta última.

Antes que nada presentamos las nociones básicas necesarias de álgebra exterior. Al iniciar el concepto de computación cuántica propiamente presentamos a los espacios de Hilbert donde se realiza, la noción de qubit e ilustramos el mecanismo de cómputo con el algoritmo ya clásico de Deutsch-Josza. Luego presentamos un algoritmo para calcular transformaciones discretas de Fourier en tiempo lineal. Finalmente, presentamos el célebre algoritmo de Shor para la factorización de enteros en tiempo polinomial.

Un poco de computación cuántica: Algoritmos más comunes

Resumen: