Algoritmo de Shor

Que tal compañeros esta vez vengo a mostrar una pequeña introducción a un tema que me pareció interesante y trata acerca del algoritmo de shor.


¿Que es exactamente o cual es su definición?

El algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)³) y espacio O(log N), así nombrado por Peter Shor.

Muchas criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si el algoritmo de Shor es implementado alguna vez en una computadora cuántica práctica. Un mensaje cifrado con RSA puede ser descifrado descomponiendo en factores la llave pública N, que es el producto de dos números primos.

Los algoritmos clásicos conocidos no pueden hacer esto en tiempo O((log N)^k) para ningún k, así que llegan a ser rápidamente imprácticos a medida que se aumenta N. Por el contrario, el algoritmo de Shor puede romper RSA en tiempo polinómico. También se ha ampliado para atacar muchas otras criptografías públicas.

Como todos los algoritmos de computación cuántica, el algoritmo de Shor es probabilístico: da la respuesta correcta con alta probabilidad, y la probabilidad de fallo puede ser disminuida repitiendo el algoritmo.

¿Que es un computador cuántico?

La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de qubits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica, lo que ha dado lugar a una gran expectación, ya que algunos problemas intratables pasan a ser tratables. Mientras un computador clásico equivale a una máquina de Turing, un computador cuántico equivale a una máquina de Turing indeterminista.

El problema que intenta solucionar el algoritmo de Shor es que, dado un número entero N, intentamos encontrar otro número entero p entre 1 y N que divida N.
El algoritmo de Shor consiste en dos partes:

1. Una reducción del problema de descomponer en factores al problema de encontrar el orden, que se puede hacer en una computadora clásica.
2. Un algoritmo cuántico para solucionar el problema de encontrar el orden.

punto 1 (la parte clásica):

1. Escoja un número pseudo-aleatorio a <>
2.Compute el mcd(a, N).podemos por ejemplo usar el aglrotimo de Euclides. #algoritmo que nos permite encontrar eficientemente el máximo común divisor.

Si el mcd(a, N) ≠ 1, entonces es un factor no trivial de N, así que terminamos.
Si no, utilice el subprograma para encontrar el período para encontrar r, el período de la función siguiente:
f(x) = a^x mod N,
es decir el número entero más pequeño r para el cual
f(x + r) = f(x).
3. Si r es impar, vaya de nuevo al paso 1.
4. Si ar/2 ≡ -1 (mod N), vaya de nuevo al paso 1.
5. Los factores de N son el mcd(ar/2 ± 1, N). Terminamos.

punto 2 subprograma para encontrar el período (parte cuántica):

1. Comience con un par de registros qubits de entrada y salida con log2N qubits cada uno, e inicialícelos a
N^{-1/2} \sum_x \left|x\right\rangle \left|0\right\rangle
donde x va de 0 a N - 1.
2. Construya f(x) como función cuántica y aplíquela al estado antedicho, para obtener
N^{-1/2} \sum_x \left|x\right\rangle \left|f(x)\right\rangle
3. Aplique la transformada de Fourier cuántica al registro de entrada. La transformada de Fourier cuántica en N puntos se define como:
U_{QFT} \left|x\right\rangle = N^{-1/2} \sum_y e^{2\pi i x y/N} \left|y\right\rangle
Lo que nos deja en el estado siguiente:
N^{-1} \sum_x \sum_y e^{2\pi i x y/N} \left|y\right\rangle \left|f(x)\right\rangle
4. Realice una medición. Obtenemos un cierto resultado y en el registro de entrada y f(x0) en el registro de salida. Puesto que f es periódica, la probabilidad de medir cierto y viene dada por

N^{-1} \left| \sum_{x:\, f(x)=f(x_0)} e^{2\pi i x y/N} \right|^2 = N^{-1} \left| \sum_{b} e^{2\pi i (x_0 + r b) y/N} \right|^2
El análisis muestra ahora que cuanto más alta es esta probabilidad, tanto más el yr/N es cercano a un número entero.

5. Convierta a y/N en una fracción irreducible, y extraiga el denominador r ', que es un candidato a r.
6. Compruebe si f(x) = f(x + r '). Si es así terminamos.
7. Si no, obtenga más candidatos a r usando valores cercanos a y, o múltiplos de r '. Si cualquier candidato cumple las condiciones, terminamos.
8. Si no, vaya de nuevo al paso 1 del subprograma.

Esto me parece algo interesante para poder empezar a investigar, por ahora solo fue la parte introductoria por la cual también en estos momentos estoy investigando; como dato les dejo algunas paginas que encontré con información acerca del tema, la mayoría de ellas en ingles pero buscare información con la cual pueda estar en español también.


Pagina con algo de contenido acerca del tema
Pagina con explicación y códigos de simulacion del mismo
Explicacion del algoritmo con datos interesantes
wikipedia: lo único que encontré por ahora en español y que se encuentra en este blog (no necesario si se lee lo de arriba)

Actualizado

aqui un pdf. con informacion del mismo en español

para verlo online haz click en este Link.

para descarga este Link.