Algoritmo de Shor

En computación cuántica, el algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)3) y espacio O(logN), 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 poco prá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.

El algoritmo de Shor fue demostrado en 2001 por un grupo en IBM, que descompuso 15 en sus factores 3 y 5, usando una computadora cuántica con 7 qubits.

Procedimiento

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 periodo.

Parte clásica

  1. Escoja un número pseudo-aleatorio a < N
  2. Compute el mcd(a, N). Esto se puede hacer usando el algoritmo de Euclides.
  1. Si el mcd(a, N) ≠ 1, entonces es un factor no trivial de N, así que terminamos.
  1. Si no, utilice el subprograma para encontrar el período (ver abajo) para encontrar r, el período de la función siguiente:
    ,
    es decir el número entero más pequeño r para el cual
    .
  2. Si r es impar, vaya de nuevo al paso 1.
  3. Si ar/2 ≡ -1 (mod N), vaya de nuevo al paso 1.
  4. Los factores de N son el mcd(ar/2 ± 1, N). Terminamos.

Parte cuántica: subprograma para encontrar el período

  1. Comience con un par de registros qubits de entrada y salida con log2N qubits cada uno, e inicialícelos a
    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
  3. Aplique la transformada cuántica de Fourier al registro de entrada. La transformada cuántica de Fourier en N puntos se define como:
    Lo que nos deja en el estado siguiente:
  4. Realice una medición. Obtenemos un cierto resultado y en el registro de entrada y f(x0) en el registro de salida. Este paso no es necesario, ya que, de acuerdo con el principio de medición en diferido, el resultado será el mismo al final del algoritmo independientemente de que se realice una medición. No obstante, por razones de simplificación a la hora de entender el algoritmo, incluiremos este paso. Puesto que f es periódica, la probabilidad de medir cierto y viene dada por
    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.
Other Languages