En otras palabras, ¿la investigación de factorización permanecerá únicamente en el mundo clásico o hay investigaciones interesantes en curso en el mundo cuántico relacionadas con la factorización?
algorithm
shors-algorithm
R. Chopin
fuente
fuente
Respuestas:
Asintóticamente, el algoritmo de Shor es realmente eficiente. Básicamente es solo: superposición, exponenciación modular (el paso más lento) y una transformación de Fourier. La exponenciación modular es lo que hace para usar realmente el criptosistema RSA. Eso significa para una computadora cuántica, cifrar / descifrar RSA legítimamente sería aproximadamente la misma velocidad que usar el algoritmo de Shor para romper el sistema. Así que soy escéptico de que haya mejoras en la idea básica.
Dicho esto, cualquier mejora en la suma de enteros, la multiplicación de enteros o la transformación cuántica de Fourier mejoraría el algoritmo de Shor, y esas son todas subrutinas muy generales en las que la gente seguramente trabajará. Una breve búsqueda en Google Scholar muestra mucha investigación sobre cómo mejorar los circuitos aritméticos cuánticos.
Creo que habrá más investigación sobre las compensaciones clásicas / cuánticas en el algoritmo de Shor. Es decir, si tiene una computadora cuántica pequeña o ruidosa, ¿puede modificar el algoritmo de Shor para que siga funcionando, pero tal vez necesite mucho más procesamiento previo y posterior en una computadora clásica, o tal vez tenga una menor probabilidad de éxito, etc.? En esta área hay Algoritmos Cuánticos para Calcular Logaritmos Discretos Cortos y Factorizar Enteros RSA . También está el tamiz de campo de número cuántico, un enfoque en el que se usa una computadora cuántica "pequeña" (demasiado pequeña para usar el algoritmo de Shor directamente) como una subrutina del tamiz clásico de campo numérico, mejorando ligeramente la complejidad del tiempo (aunque estoy personalmente convencido de que la corrección de errores para esto requerirá más qubits físicos que el algoritmo de Vanilla Shor).
En resumen, no espero ningún nuevo algoritmo de factorización cuántica radical y no creo que nadie esté trabajando en ello. Pero hay muchos ajustes interesantes que deben hacerse para adaptarse a casos de uso específicos.
fuente
Como complemento a la respuesta de Sam:
No, en parte porque el enfoque de Shor no es la única forma de factorizar números.
La factorización también se puede escribir como un problema de optimización .
Esto se puede resolver usando la máquina D-Wave , pero también usando una computadora cuántica basada en compuerta .
fuente
Como recordatorio, el algoritmo de Shor se implementa en el modelo de compuerta de cómputo.
El tiempo de ejecución del algoritmo adiabático es, según tengo entendido, notablemente voluble para determinar, basándose en las propiedades espectrales del problema hamiltoniano.
Aunque las simulaciones numéricas a veces parecen alentadoras, creo que todavía es una pregunta abierta sobre si un algoritmo de factorización adiabático realmente proporciona una aceleración exponencial sobre la factorización clásica.
Ver más detalles en este documento de Peng, Liao, Xu, Gan Qin, Zhou, Suter y Du - su FIG. 3 simulaciones del tiempo de ejecución sugieren un ajuste cuadrático; sin embargo; No estoy seguro de si se ha llevado a cabo más investigación para demostrar tal ajuste, o para proporcionar más evidencia de incluso un tiempo de ejecución polinomial.
fuente