next up previous
Next: Presente y futuro de Up: Inicios de la Computación Previous: Inicios de la Computación

El algoritmo de Shor

La pregunta que Feynman dejó sin contestar, es si ésta complejidad cuántica puede servir de algo computacionalmente, porque al fin y al cabo, la complejidad se encuentra en las amplitudes de probabilidad que determinan el estado del sistema cuántico, valores que no pueden ser leídos. Esta pregunta fue contestada con un rotundo SI cuando Peter Shor, de los laboratorios de AT&T demostró en 1994 que, en principio, un computador cuántico puede factorizar un número eficientemente.

El algoritmo de Shor se convirtio rápidamente en la killer application de la computación cuántica. La factorización de números tiene la propiedad de que es fácil verificar si dos numeros $ p$ y $ q$ dividen a $ m$, pero si solo conocemos $ m$, es muy difícil encontrar $ p$ y $ q$. Es ampliamente considerado (aunque no ha si demostrado) que la factorización de números en sus factores primos es superpolinomial en $ \log(n)$. El algoritmo más rápido que se conoce ejecuta en tiempo

$\displaystyle \textrm{tiempo} \simeq e^{[c(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}]}
$

donde $ c=\left(\frac{64}{9}\right)^{\frac{1}{3}} \sim 1.9$. debido a esta dificultad, muchos esquemas de encriptamiento tales como el RSA y el encriptamiento con llave pública, se basan en la factorización de números para protejer la información.

El algoritmo de Shor, por el contrario, es capaz de encontrar los factores primos de un número arbitrario $ n$ en tiempo $ O[(\ln n)^3]$. esto significa que cómputos que antes se consideraban imposibles ahora podrían calcularse en cuestión de dias. El algoritmo de Shor pone en peligro los actuales esquemas de seguridad utilizados en Internet.


next up previous
Next: Presente y futuro de Up: Inicios de la Computación Previous: Inicios de la Computación
Jose Castro 2004-10-06