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.
Corrección de Errores Cuánticos
HardwareTécnicas para detectar y corregir errores en circuitos cuánticos sin medir (y colapsar) los qubits.
NISQ
HardwareNoisy Intermediate-Scale Quantum (cuántica ruidosa de escala intermedia): dispositivos con 50 a 1000 qubits sin corrección de errores completa.