Factorització amb l’Algorisme de Shor
En aquest tutorial, aprendrem sobre l’algorisme de Shor, que és un algorisme quàntic per factoritzar enters grans de manera eficient, proporcionant una acceleració exponencial en comparació amb els algorismes clàssics.
Nota
Si encara no ho heu fet, pot ser útil consultar primer aquests tutorials: Quantum Basics i Quantum Circuits.
El Problema
El problema de la factorització d’enters consisteix a trobar els factors primers d’un nombre compost donat. Per exemple, si tenim el nombre 15, els seus factors primers són 3 i 5. Aquest problema és de gran importància en criptografia, ja que molts esquemes de xifratge depenen de la dificultat de factoritzar enters grans.
Clàssicament, els algorismes més coneguts per factoritzar enters grans s’executen en temps sub-exponencial, la qual cosa fa inviable factoritzar nombres grans en un temps raonable.
La Solució
L’algorisme de Shor, desenvolupat per Peter Shor el 1994, proporciona una solució en temps polinomial al problema de factorització d’enters mitjançant la computació quàntica. L’algorisme consta de dues parts principals: una part clàssica i una part quàntica. La part clàssica implica reduir el problema de factorització a un problema de trobar el període d’una determinada funció, mentre que la part quàntica usa la transformada de Fourier quàntica per trobar aquest període de manera eficient.
L’algorisme es pot resumir de la manera següent, en intentar factoritzar el nombre \(N\):
Trieu un enter aleatori \(a\) tal que \(1 < a < N\)
Calculeu el màxim comú divisor (MCD) de \(a\) i \(N\). Si el MCD és major que 1, hem trobat un factor no trivial de \(N\).
Si el MCD és 1, procedim a trobar el període \(r\) de la funció \(f(x) = a^x \mod N\) usant la part quàntica de l’algorisme.
Si \(r\) és parell i el MCD de \(a^{r/2} - 1\) i \(N\) és major que 1, hem trobat un factor no trivial de \(N\).
En cas contrari, repetim el procés amb un enter aleatori \(a\) diferent.
La Implementació
Com a exemple, considerem el nombre 3. Encara que el 15 s’usa sovint com a exemple per a la factorització, el circuit quàntic per factoritzar-lo és més difícil d’explicar. En el seu lloc, factoritzarem 3 en 1 i 3 per demostrar l’algorisme.
Llavors, seguint els passos:
Triem un enter aleatori \(a\) tal que \(1 < a < 3\). L’única opció és \(a = 2\).
Calculem el MCD de \(2\) i \(3\), que és 1, de manera que procedim al pas següent.
Necessitem trobar el període \(r\) de la funció \(f(x) = 2^x \mod 3\). Per fer-ho, usem el circuit quàntic següent:
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)
Això donarà com a sortida una barreja 50/50 de 0 i 2, que correspon al període \(r = 2\).
Com que \(r\) és parell, calculem el MCD de \(a^{r/2} - 1 = 2^1 - 1 = 1\) i \(3\), que és 1, de manera que no trobem un factor no trivial.
Llavors repetiríem el procés amb un enter aleatori \(a\) diferent, però com que no hi ha altres opcions, concloem que els factors de 3 són 3 i 1.