Factorización con el Algoritmo de Shor
En este tutorial, aprenderemos sobre el algoritmo de Shor, que es un algoritmo cuántico para factorizar enteros grandes de manera eficiente, proporcionando una aceleración exponencial en comparación con los algoritmos clásicos.
Nota
Si aún no lo has hecho, puede ser útil revisar primero estos tutoriales: Quantum Basics y Quantum Circuits.
El Problema
El problema de la factorización de enteros consiste en encontrar los factores primos de un número compuesto dado. Por ejemplo, si tenemos el número 15, sus factores primos son 3 y 5. Este problema es de gran importancia en criptografía, ya que muchos esquemas de cifrado dependen de la dificultad de factorizar enteros grandes.
Clásicamente, los mejores algoritmos conocidos para factorizar enteros grandes se ejecutan en tiempo sub-exponencial, lo que hace inviable factorizar números grandes en un tiempo razonable.
La Solución
El algoritmo de Shor, desarrollado por Peter Shor en 1994, proporciona una solución en tiempo polinomial al problema de factorización de enteros mediante la computación cuántica. El algoritmo consta de dos partes principales: una parte clásica y una parte cuántica. La parte clásica implica reducir el problema de factorización a un problema de encontrar el período de cierta función, mientras que la parte cuántica usa la transformada de Fourier cuántica para encontrar este período de manera eficiente.
El algoritmo puede resumirse como sigue, al intentar factorizar el número \(N\):
Elige un entero aleatorio \(a\) tal que \(1 < a < N\)
Calcula el máximo común divisor (MCD) de \(a\) y \(N\). Si el MCD es mayor que 1, hemos encontrado un factor no trivial de \(N\).
Si el MCD es 1, procedemos a encontrar el período \(r\) de la función \(f(x) = a^x \mod N\) usando la parte cuántica del algoritmo.
Si \(r\) es par y el MCD de \(a^{r/2} - 1\) y \(N\) es mayor que 1, hemos encontrado un factor no trivial de \(N\).
De lo contrario, repetimos el proceso con un entero aleatorio \(a\) diferente.
La Implementación
Como ejemplo, consideremos el número 3. Aunque 15 se usa a menudo como ejemplo para la factorización, el circuito cuántico para factorizarlo es más difícil de explicar. En su lugar, factorizaremos 3 en 1 y 3 para demostrar el algoritmo.
Entonces, siguiendo los pasos:
Elegimos un entero aleatorio \(a\) tal que \(1 < a < 3\). La única opción es \(a = 2\).
Calculamos el MCD de \(2\) y \(3\), que es 1, por lo que procedemos al siguiente paso.
Necesitamos encontrar el período \(r\) de la función \(f(x) = 2^x \mod 3\). Para ello, usamos el siguiente circuito cuántico:
from qilisdk.digital import Circuit, X, H, Controlled, CNOT, SWAP, T, Adjoint, M
from qilisdk.backends import QiliSim, DigitalMethod
from qilisdk.functionals import DigitalPropagation
from qilisdk.readout import Readout
# Initialize the circuit with 4 qubits (2 for the input and 2 for the output)
shors = Circuit(4)
shors.add(X(3))
shors.add(H(0))
shors.add(H(1))
# Modulo exponentiation
shors.add(Controlled(1, basic_gate=SWAP(2, 3)))
# Inverse Quantum Fourier Transform
shors.add(H(0))
shors.add(Adjoint(T(0)))
shors.add(CNOT(1, 0))
shors.add(T(0))
shors.add(CNOT(1, 0))
shors.add(Adjoint(T(1)))
shors.add(H(1))
shors.add(SWAP(0, 1))
# We measure the first two qubits to find the period r
shors.add(M(0))
shors.add(M(1))
# Run the simulation
backend = QiliSim(digital_simulation_method=DigitalMethod.statevector(matrix_free=False))
res = backend.execute(DigitalPropagation(shors), Readout().with_sampling(1000))
print(res)
Esto dará como resultado una mezcla 50/50 de 0 y 2, que corresponde al período \(r = 2\).
Como \(r\) es par, calculamos el MCD de \(a^{r/2} - 1 = 2^1 - 1 = 1\) y \(3\), que es 1, por lo que no encontramos un factor no trivial.
Repetiríamos el proceso con un entero aleatorio \(a\) diferente, pero como no hay otras opciones, concluimos que los factores de 3 son 3 y 1.