¿El algoritmo de Shor termina la búsqueda de algoritmos de factorización en el mundo cuántico de la computación?

10

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?

R. Chopin
fuente
1
conocer un algoritmo para resolver el problema de manera eficiente no significa que no se encuentren otros algoritmos que sean mejores (en general o en circunstancias específicas)
glS
2
¿Se pregunta si se ha demostrado que el algoritmo de Shor es óptimo, o si la investigación de algoritmos de factorización clásica sigue siendo útil?
ahelwer
Le pregunto a este último. Estoy seguro de que la búsqueda continuará en el mundo clásico porque nadie sabe si existe o no una solución rápida, pero ¿qué hay de la computación cuántica? ¿Están todos satisfechos con el algoritmo de Shor hasta el punto de ir a otros campos?
R. Chopin
1
Creo que quiere decir "la investigación de factoring permanecerá únicamente en el mundo clásico ..."
Mark S

Respuestas:

7

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.

Sam Jaques
fuente
1
Creo que encontrará RSA post-cuántica una lectura interesante. Muchas gracias por las interesantes referencias agregadas en su respuesta.
R. Chopin
1

Como recordatorio, el algoritmo de Shor se implementa en el modelo de compuerta de cómputo.

(norte-Xy)2Xynorte

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.

Marcas
fuente