Bueno, para empezar, el algoritmo de Shor es un algoritmo diseñado para ejecutarse en una computadora cuántica. El algoritmo toma un número [matemático] N [/ matemático] y genera sus factores. Por ejemplo, la entrada [matemática] N = 15 [/ matemática] daría como resultado la salida [matemática] 15 = 3 \ cdot 5 [/ matemática]. O como un ejemplo más difícil, la entrada [matemática] N = 694921 [/ matemática] daría como resultado la salida [matemática] 694921 = 787 \ cdot 883 [/ matemática].
El algoritmo más conocido para factorizar números primos en una computadora clásica (no cuántica) requiere una cantidad de tiempo que es básicamente exponencial con el tamaño de [matemáticas] N [/ matemáticas]. Esta es la razón por la cual el algoritmo de Shor se considera importante: una computadora cuántica que lo ejecuta solo requeriría un tiempo polinómico (en lugar de exponencial). Dado que la seguridad del popular sistema de cifrado RSA se basa en la dificultad de la factorización principal, el algoritmo de Shor ha atraído mucho interés de las comunidades de privacidad y seguridad de datos.
Ese es el contexto detrás del algoritmo de Shor. En cuanto a cómo funciona realmente, he tratado de hacer una lluvia de ideas sobre una analogía adecuada, pero ninguna es remotamente tan buena como la escrita por Scott Aaronson en Shor, lo haré, así que citaré la suya. La esencia básica del algoritmo de Shor es el proceso de búsqueda de períodos que se realiza mediante la Transformación Cuántica de Fourier (QFT) . El QFT toma alguna función [matemática] f (x) [/ matemática] y calcula el período de la función. Por ejemplo, si [math] f (x) = f (x + 10) [/ math] para todos [math] x [/ math], entonces la función se repite cada 10 valores, y podemos decir que tiene un período de 10.
- ¿Qué lenguajes de programación se usan en la computación cuántica?
- ¿El lanzamiento de un satélite capaz de criptografía cuántica sorprendió a los criptógrafos internacionales?
- ¿Hay alguna informática más rápida que la computación cuántica?
- ¿Cómo se comunican las partículas cuánticas cuando están separadas por una gran distancia?
- ¿Pueden los transistores emitir bajo, medio, alto en lugar de bajo, alto? Si es así, ¿cuál es la diferencia computacional entre esto y la computación cuántica?
Entonces, ¿cómo funciona realmente el QFT? Aquí es donde recurriré a la analogía de Aaronson. Por favor, léalo detenidamente, ¡prometo que será esclarecedor!
OK, déjame probar esto. Como muchos científicos informáticos, mantengo horas extremadamente extrañas. ¿Conoces el famoso experimento en el que pegan a las personas durante semanas en una habitación sellada sin relojes ni luz solar, y las personas cambian gradualmente de un día de 24 horas a un día de 25 o 26 o 28 horas? Bueno, eso es solo la vida ordinaria para mí. Un día me despertaré a las 9 a.m., al día siguiente a las 11 a.m., el día siguiente a la 1 p.m., etc. De hecho, felizmente ‘daré la vuelta’ si no intervienen clases o citas. (Solía hacerlo todo el tiempo en Berkeley).
Ahora, aquí está mi pregunta: digamos que te digo que me desperté a las 5pm esta tarde. Solo por ese hecho, ¿qué puede concluir acerca de cuánto dura mi “día”: si tengo un horario de 25 horas, un horario de 26.3 horas, o lo que sea?
¡La respuesta, por supuesto, no es mucho! Quiero decir, es una apuesta bastante segura que no estoy en un horario de 24 horas, ya que de lo contrario me despertaría por la mañana, no a las 5 p.m. Pero casi cualquier otro horario (25 horas, 26 horas, 28 horas, etc.) necesariamente me hará “recorrer todo el día”, por lo que no sería una sorpresa verme levantarme a las 5 de la tarde en una tarde en particular .
Ahora, sin embargo, quiero que te imagines que la pared de mi habitación está cubierta de relojes analógicos. Estos son relojes muy extraños: uno de ellos hace una revolución completa cada 17 horas, uno de ellos cada 26 horas, uno de ellos cada 24.7 horas, y así sucesivamente durante casi todas las horas que puedas imaginar. (Para simplificar, cada reloj tiene solo una manecilla de hora, no manecilla de minutos). También quiero que te imagines que debajo de cada reloj hay una cartulina con una chincheta. Cuando me mudé a mi apartamento por primera vez, cada chincheta estaba en el medio de su tablero respectivo. Pero ahora, cada vez que me levanto por la “mañana”, lo primero que hago es dar la vuelta a mi habitación y mover cada chincheta exactamente una pulgada en la dirección que señala la manecilla del reloj que está encima.
Ahora, aquí está mi nueva pregunta: al examinar las chinchetas en mi habitación, ¿es posible averiguar qué tipo de horario estoy manteniendo? Afirmo que es posible. Como ejemplo, supongamos que mantenía un día de 26 horas. Entonces, ¿qué pasaría con la chincheta debajo del reloj de 24 horas? No es difícil ver que sufriría un movimiento periódico : claro, se desplazaría un poco, pero después de cada 12 días volvería al centro del tablero donde había comenzado. Una mañana movería la chincheta una pulgada en esta dirección, otra mañana una pulgada en eso, pero eventualmente todos estos movimientos en diferentes direcciones se cancelarían mutuamente.
Por otro lado, una vez más, suponiendo que tuviera un día de 26 horas, ¿qué pasaría con el pulgar debajo del reloj de 26 horas? Aquí la respuesta es diferente. En lo que respecta al reloj de 26 horas, ¡me he estado despertando exactamente a la misma hora cada “mañana”! Cada vez que me levanto, el reloj de 26 horas apunta en la misma dirección que la última vez que me desperté. ¡Así que seguiré moviendo la chincheta una pulgada más en la misma dirección, hasta que ni siquiera esté en el cartel!
Se deduce, entonces, que solo al ver qué chincheta viajó más lejos desde su punto de partida, podría averiguar en qué tipo de horario estaba. En otras palabras, podrías inferir el “período” de la secuencia periódica que es mi vida.
Así es como funciona el QFT. Un comentario que vale la pena agregar: el QFT se puede hacer de manera eficiente en una computadora cuántica, porque puede hacer que todos los “experimentos de reloj” se ejecuten a la vez en superposición , con los malos experimentos deteriorados por los efectos de interferencia destructiva y los buenos experimentos dominando por la interferencia constructiva efectos
¡Casi allí! El resto del algoritmo de Shor es completamente un algoritmo clásico. Una vez que tenemos el mecanismo de búsqueda de períodos de la Transformada Cuántica de Fourier, podemos explotarlo para encontrar patrones en la estructura matemática del número que estamos tratando de factorizar, [matemáticas] N [/ matemáticas]. En particular, encontramos el período de [math] a ^ x \ mod N [/ math], donde [math] a [/ math] es esencialmente un número aleatorio menor que [math] N [/ math]. Por cierto, en caso de que la palabra “mod” no sea familiar, solo significa resto. Para recapitular con un ejemplo específico, si [matemática] N = 77 [/ matemática] y [matemática] a = 22 [/ matemática], entonces la QFT nos dirá cuánto tiempo tenemos que continuar en la secuencia de [matemática] 22 ^ 1, 22 ^ 2, 22 ^ 3 \ mod 77, [/ math] y así sucesivamente hasta que lleguemos a 22 nuevamente.
A partir de ahí, solo tomamos prestado un resultado de la teoría de números que generalmente * produce un factor de [matemáticas] N [/ matemáticas]. El resultado es que el máximo común denominador de [matemáticas] N [/ matemáticas] y [matemáticas] a ^ {\ text {período} / 2} -1 [/ matemáticas] es un factor de [matemáticas] N [/ matemáticas] . ¡Hecho!
Pongo un * por ‘generalmente’ porque el algoritmo a menudo puede ser desafortunado por razones teóricas numéricas. Cuando eso sucede, la elección de [matemáticas] a [/ matemáticas] no dará lugar a factores de [matemáticas] N [/ matemáticas]. En ese caso, solo tenemos que repetir desde el paso 1, ¡eligiendo un nuevo valor para [math] a [/ math]! La probabilidad de que un [math] a [/ math] aleatorio funcione es lo suficientemente alta como para que el algoritmo pueda ejecutarse algunas veces antes de generar un factor exitoso.
Y ese es el algoritmo de Shor. Como punto final, vale la pena mencionar que para que el algoritmo sea realmente útil, ¡primero será necesario construir computadoras cuánticas escalables! Hasta ahora, lo mejor que una computadora cuántica ha hecho es factorizar 21 como [matemática] 3 \ cdot 7 [/ matemática] … y muchos en el campo agregarán en broma ” con alta probabilidad ” .
