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)³) 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((logN)^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.

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.

Contenido

1 Procedimiento
- 1.1 Parte clásica
- 1.2 Parte cuántica: subprograma para encontrar el período
2 Explicación del algoritmo
- 2.1 I. Obtención de factores a partir del período
- 2.2 II. Encontrar el período
3 Referencias
4 Véase también

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:

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

Parte clásica

Escoja un número pseudo-aleatorio a < N
Compute el mcd(a, N). Esto se puede hacer usando el algoritmo de Euclides.

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 (ver abajo) para encontrar r, el período de la función siguiente:

$f(x) = a^x\ \mbox{mod}\ N$ ,

es decir el número entero más pequeño r para el cual

$f (x + r) = f (x)$ .
Si r es impar, vaya de nuevo al paso 1.
Si a^r/2 ≡ -1 (mod N), vaya de nuevo al paso 1.
Los factores de N son el mcd(a^r/2 ± 1, N). Terminamos.

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

Comience con un par de registros qubits de entrada y salida con log₂N 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.
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$
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$
Realice una medición. Obtenemos un cierto resultado y en el registro de entrada y f(x₀) 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.
Convierta a y/N en una fracción irreducible, y extraiga el denominador r ', que es un candidato a r.
Compruebe si f(x) = f(x + r '). Si es así terminamos.
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.
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 implentar 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. 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 (Z/N Z)^×. 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

$a^r \equiv 1\ \mbox{mod}\ N.\,$

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

$a^r - 1 = (a^{r/2} - 1) (a^{r/2} + 1) \equiv 0\ \mbox{mod}\ N$

$\Rightarrow N\ | (a^{r/2} - 1) (a^{r/2} + 1).\,$

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 (a^r/2 + 1), entonces N debe tener un factor común no trivial con (a^r/2 - 1) y (a ^r/2 + 1).

Prueba: Por simplicidad, denote (a^r/2 - 1) y (a^r/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.

II. 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 probablidad. 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.

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).
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.
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)²) 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

e 2π i b y r / N = 1

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 de valoración de fase cuántica disfrazado.

Referencias

Preprint del papel original de Peter Shor:

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor (en inglés)

Un libro de textos general en computación cuántica:

Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000 (en inglés)

Véase también

Computación cuántica

Categorías:

Algoritmos cuánticos
Algoritmos de factorización de enteros

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

Algoritmo de Shor — 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(log N), así nombrado por Peter Shor. Muchas Criptografías de clave pública, tales como RSA, llegarían a ser obsoletas si … Enciclopedia Universal
Algoritmo cuántico — Transformada de Fourier cuántica sobre tres qubits, basada en la aplicación reiterada de la puerta cuántica de Hadamard y de puertas de cambio de fase. Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación… … Wikipedia Español
Peter Shor — Saltar a navegación, búsqueda Peter Shor Nacimiento 14 de agosto 1959 Nueva York Campo(s) Ingeniero en computación Instituciones MIT … Wikipedia Español
Computación cuántica — La esfera de Bloch es una representación de un qubit, el bloque de construcción fundamental de los computadores cuánticos. 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… … Wikipedia Español
Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… … Wikipedia Español
Factorización de enteros — Saltar a navegación, búsqueda En teoría de números, el problema de la factorización de enteros consiste en encontrar un divisor no trivial de un número compuesto; Por ejemplo dado el número 91, el reto es encontrar un número tal como el 7 que lo… … Wikipedia Español
Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número … Wikipedia Español
Premio Gödel — Saltar a navegación, búsqueda El Premio Gödel es un premio que se entrega a autores de artículos relacionados con teoría de la computación. El nombre del premio se debe al matemático Kurt Gödel, y es otorgado por la European Association for… … Wikipedia Español
BQP — Saltar a navegación, búsqueda En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. Dicho de otra… … Wikipedia Español
Qubit — Saltar a navegación, búsqueda … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Algoritmo de Shor

Contenido