El algoritmo de Shor, desarrollado por Peter Shor en 1994, puede factorizar un entero N en tiempo polinómico O((log N)³) utilizando ordenadores cuánticos. El mejor algoritmo clásico conocido (criba general del cuerpo de números) se ejecuta en tiempo subexponencial. Esto es significativo porque el cifrado RSA depende de la dificultad de factorizar números grandes. El algoritmo de Shor utiliza la Transformada Cuántica de Fourier para encontrar el período de una función exponencial modular. Aunque el algoritmo es teóricamente poderoso, ejecutarlo en hardware real para romper RSA-2048 requeriría millones de qubits con corrección de errores, mucho más allá de las capacidades NISQ actuales (que tienen como máximo ~1000 qubits ruidosos). El algoritmo de Shor es la principal motivación de la investigación en criptografía post-cuántica y del esfuerzo de estandarización de criptografía post-cuántica del NIST.
Términos relacionados
QFT
AlgorithmsQuantum Fourier Transform (transformada cuántica de Fourier): el análogo cuántico de la transformada discreta de Fourier, exponencialmente más rápido.
Estimación de Fase Cuántica
AlgorithmsUn algoritmo que estima la fase del autovalor de un operador unitario: la subrutina que subyace al algoritmo de Shor y a los cálculos de energía en química cuántica.
Corrección de Errores Cuánticos
HardwareLa corrección de errores cuánticos (QEC) protege qubits lógicos frente a decoherencia y fallos de puerta mediante varios qubits físicos. Es la base de la computación cuántica tolerante a fallos.
NISQ
HardwareNoisy Intermediate-Scale Quantum (cuántica ruidosa de escala intermedia): dispositivos con 50 a 1000 qubits sin corrección de errores completa.