Algoritmo de factorización de Shor

Algoritmo de factorización de Shor :

• El algoritmo de factorización de Shor es propuesto por Peter Shor.
• Sugiere que la mecánica cuántica permite que la factorización se realice en tiempo polinomial , en lugar del tiempo exponencial logrado después de usar algoritmos clásicos.
• Esto podría tener un impacto drástico en el campo de la seguridad de datos , un concepto basado en la descomposición en factores primos de grandes números .
• Existen muchos algoritmos de tiempo polinomial para la multiplicación de enteros (p. ej., el algoritmo de Euclides ), pero no existe ningún algoritmo de tiempo polinomial para la factorización.
• Entonces, Shor ideó un algoritmo, es decir, el algoritmo de factorización de Shor, un algoritmo para factorizar números enteros no primos N de L bits.
• Los algoritmos cuánticos son mucho mejores que los algoritmos clásicos porque se basan en la transformada cuántica de Fourier.
• El tiempo de ejecución en la computadora clásica es O[exp (L ^1/3 (log L) ^2/3 )] pero en la computadora cuántica es O(L ³ ) .
• Entonces, el algoritmo de Shor, en principio, muestra que una computadora cuántica es capaz de factorizar números muy grandes en tiempo polinomial.

El algoritmo de Shor depende de :

• Aritmética modular
• Paralelismo cuántico
• Transformación cuántica de Fourier

El algoritmo queda como :

Dado un número compuesto impar N , encuentre un entero d , estrictamente entre 1 y N , que divida a N .

El algoritmo de Shor consta de las siguientes dos partes:

• Conversión del problema de factorizar al problema de encontrar el período. Esta parte se puede implementar con medios clásicos.
• Encontrar el período o encontrar el período cuántico utilizando la transformada cuántica de Fourier , y es responsable de la aceleración cuántica y utiliza el paralelismo cuántico.

En el algoritmo de Shor, la entrada es un número no primo N y la salida es un factor no trivial de N

ENTRADA (N) —> ALGORITMO DE SHOR —> SALIDA (Factor no trivial de N)

Algoritmo: Contiene unos pocos pasos, solo en el paso 2 se requiere el uso de computadoras cuánticas.

1. Elija cualquier número aleatorio, digamos r , tal que r < N para que sean coprimos entre sí.
2. Se usa una computadora cuántica para determinar el período desconocido p de la función f _{r, N} (x) = r ^x mod N .
3. Si p es un número entero impar, vuelva al paso 1 . De lo contrario, vaya al siguiente paso.
4. Como p es un entero par, entonces, (r ^p/2 – 1)(r ^p/2 + 1) = r ^p – 1 = 0 mod N .
5. Ahora, si el valor de r ^p/2 + 1 = 0 mod N , regrese al Paso 1 .
6. Si el valor de r ^p/2 + 1 != 0 mod N , de lo contrario pasar al siguiente paso.
7. Calcule d = mcd(r ^p/2 -1, N) .
8. La respuesta requerida es ‘ d ‘.

Parte clásica ( El problema de búsqueda de pedidos):
Esta es la parte clásica del problema de búsqueda de pedidos. Dado que x y N , tal que x<N y mcd(x, N) = 1 . El orden de x es el menor entero positivo, y tal que x ^y = 1(mod N) .

1. Se elige un número aleatorio n , tal que n < N . Calcule mcd(n, N) .
2. Esto se puede hacer usando el Algoritmo de Euclides.
3. Si mcd(n, N) != 1 , entonces existe un factor no trivial de N. Si (x+p) = n ^{x + p} mod N = n ^x mod N = f(x) .
4. Si r es impar, vuelva al paso 1 .
5. Si n ^p/2 = -1(mod N) , entonces regrese al Paso 1 .
6. El mcd(n ^p/2 +/- 1, N) es un factor no trivial de N .

Parte cuántica:

Esta es la parte de búsqueda de orden cuántico. Elija una potencia de 2, luego
Q = 2L tal que N ² <= Q <= 2N ²

Y considere f = {0, 1, 2, …, Q-1}

Donde, f(y)=1/(Q) ^1/2 ∑ _x=0 ^Q-1 I f(x) I w ^xy y w = exp(2π i/Q) , es decir, Q ^-ésima raíz de la unidad.

• Realicemos el Algoritmo de Shor usando un ejemplo: Para factorizar un entero impar N (sea N = 17).
• Elija un número entero Q tal que N ² <= Q ≤ 2 N ² (sea Q = 324).
• Luego, elija aleatoriamente cualquier entero n tal que mcd (n, N)=1, (elijamos que el entero sea n=7).
• Luego cree dos registros cuánticos (estos registros deben entrelazarse para que el colapso del registro de entrada corresponda al colapso del registro de salida)
  • Registro de entrada: debe contener suficientes qubits para representar números tan grandes como Q-1 (es decir, hasta 323, por lo que necesitamos 9 qubits).
  • Registro de salida: debe contener suficientes qubits para representar números tan grandes como (N – 1) . (es decir, hasta 16, por lo que requerimos 4 qubits).

Código:

from qiskit import IBMQ
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Shor
 
# Enter your API token here
IBMQ.enable_account('ENTER API TOKEN HERE') 
provider = IBMQ.get_provider(hub='ibm-q')
 
# Specifies the quantum device
backend = provider.get_backend('ibmq_qasm_simulator')
 
print('\n Shors Algorithm')
print('--------------------')
print('\nExecuting...\n')
 
# Function to run Shor's algorithm
# where 21 is the integer to be factored
factors = Shor(35)
 
result_dict = factors.run(QuantumInstance(
    backend, shots=1, skip_qobj_validation=False))
 
 # Get factors from results
result = result_dict['factors']
 
print(result)
print('\nPress any key to close')
input()

Producción :

Shors Algorithm
- - - - - - - - - - - - -
Executing...
[[5,7]]
Press any key to close

Salida para el código anterior que muestra los factores 5 y 7 para N=35.