Algoritmo de shor

El algoritmo de Shor es un algoritmo informático cuántico de tiempo polinomial para la factorización de enteros . ^{[1] De manera} informal, resuelve el siguiente problema: Dado un número entero , encuentre sus factores primos . Fue descubierto en 1994 por el matemático estadounidense Peter Shor .${\ Displaystyle N}$

En una computadora cuántica, para factorizar un número entero , el algoritmo de Shor se ejecuta en tiempo polinomial (el tiempo tomado es polinomio en , el tamaño del número entero dado como entrada). ^[2] Específicamente, toma puertas cuánticas de orden usando multiplicación rápida, ^[3] demostrando así que el problema de factorización de enteros puede resolverse de manera eficiente en una computadora cuántica y, en consecuencia, está en la clase de complejidad BQP . Esto es casi exponencialmente más rápido que el conocido algoritmo de factorización clásico más eficiente, la criba general de campo numérico , que funciona en tiempo sub-exponencial : . ^[4]${\ Displaystyle N}$${\ Displaystyle \ log N}$${\ Displaystyle O \! \ left ((\ log N) ^ {2} (\ log \ log N) (\ log \ log \ log N) \ right)}$ ${\ Displaystyle O \! \ left (e ^ {1.9 (\ log N) ^ {1/3} (\ log \ log N) ^ {2/3}} \ right)}$La eficiencia del algoritmo de Shor se debe a la eficiencia de la transformada cuántica de Fourier y la exponenciación modular por cuadraturas repetidas . ^[5]

Si una computadora cuántica con una cantidad suficiente de qubits pudiera funcionar sin sucumbir al ruido cuántico y otros fenómenos de decoherencia cuántica , entonces el algoritmo de Shor podría usarse para romper esquemas de criptografía de clave pública , como

RSA se basa en la suposición de que factorizar números enteros grandes es computacionalmente intratable. Hasta donde se sabe, esta suposición es válida para computadoras clásicas (no cuánticas); no se conoce ningún algoritmo clásico que pueda factorizar números enteros en tiempo polinomial. Sin embargo, el algoritmo de Shor muestra que factorizar enteros es eficiente en una computadora cuántica ideal, por lo que puede ser factible derrotar a RSA construyendo una computadora cuántica grande. También fue un poderoso motivador para el diseño y la construcción de computadoras cuánticas y para el estudio de nuevos algoritmos de computadoras cuánticas. También ha facilitado la investigación sobre nuevos criptosistemas que son seguros de las computadoras cuánticas, denominados colectivamente criptografía post-cuántica .

Subrutina cuántica en el algoritmo de Shor