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.

El algoritmo de Shor es un procedimiento que permite encontrar factores de un número de una manera
eficiente. La implementación de este algoritmo se puede llevar a cabo de manera clásica o utilizando
circuitos cuánticos (que no han sido llevados a la práctica todavía). Esta última implementación es (por
supuesto) la más conveniente cuando se desea encontrar el orden, un parámetro muy necesario a la hora de
encontrar los factores primos de un cierto número.

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 aplicado en la práctica en 2001 por un grupo en IBM, que descompuso 15 en sus
factores 3 y 5, usando una computadora cuántica con 7 qubits.

Índice
Procedimiento
Parte clásica
Parte cuántica: subprograma para encontrar el período
Explicación del algoritmo
I. El problema de la factorización.
Teorema 1
Teorema 2
II. El algoritmo de Shor.
1) Si '"`UNIQ--postMath-00000020-QINU`"' es par.
2) '"`UNIQ--postMath-00000022-QINU`"' es de la forma '"`UNIQ--postMath-00000023-
QINU`"'.
3) Procedimiento aleatorio.
4) Cálculo de '"`UNIQ--postMath-0000002C-QINU`"' y aplicación de los teoremas.
III. Obtención de factores a partir del período
IV. Encontrar el período
Véase también
Referencias

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

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.

Explicación del algoritmo

El algoritmo se compone de dos partes. La primera parte del algoritmo convierte el problema de
descomponer en factores en el problema de encontrar el período de una función, y se puede implementar
clásicamente. La segunda parte encuentra el período usando la transformada de Fourier cuántica, y es
responsable de la aceleración cuántica.

I. El problema de la factorización.

Sea . Entonces, encontrar un factor , es encontrar una solución para la ecuación:

Es decir, se necesita encontrar un , tal que al dividir su cuadrado entre se tenga como resto 1.

A la hora de intentar abordar este problema, existen un par de teoremas que son útiles:

Teorema 1
Sea , y sea una solución de la ecuación (*) (solución no trivial) donde es claro .
Entonces: Ó o es un factor no trivial del número ("mcd" significa el
1
máximo común divisor). ​

Teorema 2

Sea impar con descomposición en factores primos . Sea además

(aleatorio) que es coprimo con ( ) y el orden de ese número entero, es decir, aquel tal
que: . (De este último paso, esto es, hallar r, se encarga el circuito cuántico
correspondiente). Entonces:

Con estos dos teoremas en mente, ya se puede empezar a plantear la secuencia en la que está basada el
algoritmo de factorización de Shor.

Notas:

La notación que se utiliza es, en todo momento coherente, en el sentido de que las variables que aparecen
en los teoremas y fuera de ellos o en cualquier otro contexto de a continuación son las mismas.

Por otro lado, la relación que presentan las variables e es: . Como se va a poder ver en la
siguiente sección.1 ​

II. El algoritmo de Shor.

Este algoritmo sirve para factorizar números enteros de gran tamaño. Se exponen y se comentan todas las
fases de este algoritmo. En todo momento, el algoritmo va a devolver un factor del número que se desea
descomponer. Los tres primeros casos corresponden a una implementación clásica, en el sentido de que no
es necesaria la presencia de ningún circuito cuántico. Corresponden por tanto a la eliminación de casos de
tipo trivial o que una implementación clásica puede realizar con suficientemente buena eficiencia.

1) Si es par.

En efecto, la primera comprobación que se realiza al número es el caso trivial de que su última cifra sea un
número par. En tal caso, el algoritmo devuelve 2, y el programa podrá continuar con .

2) es de la forma .

La siguiente fase, es implementar una comprobación para los números enteros mayores o iguales a 1 y
números mayores o iguales a 2. Se ha de tener en cuenta este tipo de números para que (como se verá en
el paso 4) al utilizar el teorema 2 la probabilidad de obtener un buen candidato a factor sea más alta del
75%. En este caso, el algoritmo, devuelve el factor a.

3) Procedimiento aleatorio.
Se toma un número tal que . Si , entonces el programa devuelve
precisamente este número. Esto se hace solo para comprobar si el número elegido comparte factores con
. En caso de que los dos números sean coprimos se sigue con el siguiente paso de la serie.

En este punto, dado el número natural anterior, se utilizan los algoritmos de estimación de fase y en
concreto de orden, para hallar precisamente (el orden). Estos algoritmos como se puede ver en los
enlaces, dependen de la implementación del circuito cuántico en cuestión.

4) Cálculo de y aplicación de los teoremas.

Como ya se dijo antes, partimos de que se conoce el orden. Ahora, se aplican los teoremas anteriores para
intentar hallar este factor.

La primera parte de este último paso, consiste en la comprobación de si se cumplen los requisitos que el
teorema 2 impone para asegurar una alta probabilidad. Esto ya se hizo en los procedimientos anteriores,
pues se sabe que; es impar, tiene al menos dos factores primos distintos es coprimo con . Bajo estas
condiciones, es posible asegurar que existe una alta probabilidad de que el número sea no trivial, esto es:

y que por supuesto es par.

Y habiendo comprobado esto, se está en disposición de aplicar el teorema 1 pues se cumplen a su vez todas
las condiciones necesarias para poder aplicarlo y de esta forma obtener con alta probabilidad un factor de
. Bien o .

Como se ve todo este proceso depende de una cierta probabilidad de éxito. Si en algún punto el algoritmo
falla, comienza de nuevo.1 2​ 3​ ​

III. Obtención de factores a partir del período

Los números enteros menores que N y coprimos con N forman un grupo finito bajo multiplicación módulo
N, que se denota típicamente . Para el final del paso 3, tenemos un número entero a en este grupo.
Puesto que el grupo es finito, a debe tener un orden finito r, el número entero positivo más pequeño tal que

Por lo tanto, N |(ar - 1). Suponga que podemos obtener r, y es par. Entonces

r es el número entero positivo más pequeño tal que a r ≡ 1, así que N no puede dividir a (a r/2 - 1). Si N
tampoco divide (ar/2 + 1), entonces N debe tener un factor común no trivial con (ar/2 - 1) y (a r/2 + 1).

Prueba: Por simplicidad, denote (ar/2 - 1) y (ar/2 + 1) u y v respectivamente. N | uv, luego kN = uv para un
cierto número entero k. Suponga que el mcd(u, N) = 1; entonces mu + nN = 1 para ciertos números enteros
m y n (ésta es una propiedad del máximo común divisor). Multiplicando ambos lados por v, encontramos
que mkN + nvN = v, luego N |v. Por contradicción, mcd(u, N) ≠ 1. Por un argumento similar, mcd(v, N) ≠
1.
Esto nos provee de una factorización de N. Si N es el producto de dos primos, esta es la única factorización
posible.

IV. Encontrar el período

El algoritmo, para encontrar el período de Shor, se basa radicalmente en la capacidad de una computadora
cuántica de estar en muchos estados simultáneamente. Los físicos llaman a este comportamiento
superposición cuántica. Para computar el período de una función f, evaluamos la función en todos los
puntos simultáneamente.

Sin embargo, la física cuántica no permite que tengamos acceso a toda esta información directamente. Una
medición cuántica dará solamente uno de todos los valores posibles, destruyendo todos los otros. Por lo
tanto tenemos que transformar cuidadosamente la superposición a otro estado que devuelva la respuesta
correcta con alta probabilidad. Esto es alcanzado usando la transformada de Fourier cuántica.

Shor tuvo que solucionar así tres "problemas de implementación". Todos tuvieron que ser implementados
"rápidos", que significa ejecutar con un número de puertas cuánticas que es polinómico en logN.

1. Crear una superposición de estados. Esto puede hacerse aplicando las puertas de
Hadamard a todos los qubits en el registro de entrada. Otro enfoque sería utilizar la
transformada de Fourier cuántica (véase abajo).
2. Implementar la función f como una transformada cuántica. Para alcanzar esto, Shor utilizó
exponenciación por cuadrados para su transformación modular de la exponenciación.
3. Realizar una transformada de Fourier cuántica. Usando puertas controladas NOT y puertas
de una sola rotación de qubit, Shor diseñó un circuito para la transformada de Fourier
cuántica que usa exactamente ((logN)2) puertas.

Después de todas estas transformaciones una medición dará una aproximación al período r. Por simplicidad
asuma que hay una y tal que yr/N es un número entero. Entonces la probabilidad de medir y es 1. Para ver
esto notemos que

para todos los números enteros b. Por lo tanto la suma que nos da la probabilidad de la medición y será N/r
puesto que b toma aproximadamente N/r valores y así la probabilidad es 1/r. Hay r, y tales que yr/N es un
número entero, luego la suma de las probabilidades es 1. Nota: otra manera de explicar el algoritmo de Shor
es observando que es precisamente el algoritmo cuántico de estimación de fase disfrazado.

Véase también
Computación cuántica
Algoritmo de Grover

Referencias
1. Nielsen, Michael A.; Chuang, Isaac L. (2000). Quantum computation and quantum
information (https://www.worldcat.org/oclc/43641333). Cambridge University Press.
p. pp233. ISBN 0521632358. OCLC 43641333 (https://www.worldcat.org/oclc/43641333).
2. Shor, Peter W. (1999-01). «Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer» (https://dx.doi.org/10.1137/s0036144598347011).
 SIAM Review 41 (2): 303-332. ISSN  0036-1445 (https://portal.issn.org/resource/issn/0036-1445).
doi:10.1137/s0036144598347011 (https://dx.doi.org/10.1137%2Fs0036144598347011).
3. «Un poco de computación cuántica. Algoritmos más comunes. Guillermo Morales Luna» (htt
ps://web.archive.org/web/20101207082511/http://www.fceia.unr.edu.ar/~diazcaro/QC/Tutoria
ls/Un%20poco%20de%20computacion%20cuantica%20-%20Algoritmos%20mas%20comu
nes.pdf). Archivado desde el original (https://www.fceia.unr.edu.ar/~diazcaro/QC/Tutorials/U
n%20poco%20de%20computacion%20cuantica%20-%20Algoritmos%20mas%20comunes.
pdf) el 7 de diciembre de 2010. Consultado el 29 de mayo de 2018.

Obtenido de «https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Shor&oldid=144921344»

Esta página se editó por última vez el 23 jul 2022 a las 02:26.

El texto está disponible bajo la Licencia Creative Commons Atribución Compartir Igual 3.0;
pueden aplicarse
cláusulas adicionales. Al usar este sitio, usted acepta nuestros términos de uso y nuestra política de privacidad.
Wikipedia® es una marca registrada de la Fundación Wikimedia, Inc., una organización sin ánimo de lucro.