¿Cuál es el valor entero mínimo para que la factorización cuántica valga la pena?

11

Supongamos que tenemos computadoras cuánticas y clásicas de modo que, experimentalmente, cada operación lógica elemental de factorización matemática es igualmente costosa en tiempo en factorización clásica y cuántica: que es el valor entero más bajo para el cual el proceso cuántico es más rápido que el clásico ¿uno?

SalvaCardona
fuente
2
Un cálculo muy preciso dependería de detalles como la implementación de operaciones de suma en el algoritmo cuántico, y también de las operaciones precisas utilizadas en el mejor algoritmo de factorización clásico. En ambos casos, a menudo estamos acostumbrados a ignorar factores constantes en la cantidad de trabajo requerido, pero incluso más en el caso clásico que en el caso cuántico. ¿Estaría satisfecho con una estimación de orden de magnitud (por ejemplo, una ventaja cuántica obtenida en algún lugar entre 350-370 bits --- para proporcionar una posible respuesta que he creado desde el aire sin ningún análisis real)?
Niel de Beaudrap
@NieldeBeaudrap Diría que por las razones que usted indicó, sería imposible proporcionar un número exacto. Si su estimación "fuera del aire" se basa en algún razonamiento, creo que sería interesante. (En otras palabras, una suposición educada tiene valor, pero una suposición salvaje no)
Lagarto discreto
@DiscreteLizard: si tuviera un medio sólido de estimar listo, no habría producido una respuesta de ejemplo basada en ningún análisis :-) Estoy seguro de que hay una forma razonable de producir una estimación interesante, pero las que sería capaz de proporcionar fácilmente tendría barras de error demasiado grandes para ser muy interesantes.
Niel de Beaudrap
Dado que este problema es (o fue) comúnmente tomado como una "prueba" típica de que las computadoras cuánticas son capaces de proezas fuera de los ámbitos de la informática clásica, pero casi siempre en términos estrictos de complejidad computacional (por lo tanto, descuidan todas las constantes y solo son válidas para entradas arbitrariamente altas) tamaños) Yo diría que una respuesta aproximada de orden de magnitud (y su derivación) ya sería útil / pedagógica. Tal vez las personas en CS / teóricaCS estén dispuestas a ayudar.
agaitaarino
1
@agaitaarino: Estoy de acuerdo, aunque la respuesta tendrá que suponer una explicación más o menos precisa del rendimiento de los mejores algoritmos clásicos para la factorización. El resto lo puede hacer un estudiante razonablemente bueno de computación cuántica.
Niel de Beaudrap

Respuestas:

8

La parte cuántica del algoritmo de Shor es, esencialmente, una exponenciación modular única realizada bajo superposición seguida de una transformada de Fourier y luego una medición. La exponenciación modular es, con mucho, la parte más cara.

Supongamos que cada [...] operación lógica elemental de factorización matemática es igualmente costosa en la factorización clásica y cuántica.

Si suponemos que la exponenciación modular toma exactamente tanto tiempo en una computadora cuántica como lo haría en una computadora clásica, entonces la transición donde la computación cuántica mejoró ocurriría en un número muy bajo. Calcular las exponenciaciones modulares es muy rápido, clásicamente, porque puede usar el cuadrado al cuadrado. Estimaría enormemente que el crossover suceda incluso antes de que llegue a números de 30 bits (números de más de mil millones).

Pero las computadoras cuánticas no van a hacer matemáticas tan rápido como las computadoras clásicas . Por ejemplo, en mi computadora portátil, puedo hacer una exponenciación modular de 1000 bits en Python en una fracción de segundo. Pero en las computadoras cuánticas previsibles, tomaría horas o días. El problema es la diferencia masiva ( masiva ) en el costo de una compuerta AND.

|T

Supongamos que obtenemos un millón de estados T por segundo, y queremos convertir esto en una tasa de adiciones de 64 bits para comparar con la máquina clásica. Una adición de 64 bits requiere 64 puertas AND, cada una de las cuales requiere 4 puertas T. 1 millón dividido por 4 dividido por 64 da ... aproximadamente 4KHz. Por el contrario, una máquina clásica hará fácilmente mil millones de adiciones por segundo. Los sumadores cuánticos son un millón de veces más lentos que los sumadores clásicos (de nuevo, estimamos ampliamente, y tenga en cuenta que este número debería mejorar con el tiempo).

Otro factor que vale la pena considerar son los diferentes costos de las computadoras cuánticas y clásicas. Si tienes cien millones de dólares y eliges entre una computadora cuántica y mil computadoras clásicas, ese factor de 1000 debe tenerse en cuenta. En este sentido, podríamos decir que los sumadores cuánticos son mil millones de veces menos eficientes que los sumadores clásicos (en FLOPS / $).

Una penalización de factor constante de mil millones es normalmente un factor decisivo inmediato. Y para los algoritmos cuánticos con una mera ventaja cuadrática (como Grover), sostengo que de hecho es un factor decisivo. Pero el algoritmo de Shor se vuelve exponencialmente mejor en relación con la estrategia clásica a medida que aumenta el número de bits en el número para factorizar. ¿Cuántos bits antes de que comamos esa constante "miserable" 10 ^ 9 con nuestro crecimiento exponencial en ventaja?

Considere que RSA-640 fue factorizado en 2005 usando ~ 33 años de CPU. Una computadora cuántica debería poder hacer ese número en menos de un día. Si tienes mil computadoras clásicas trabajando en el problema, terminarían en unas dos semanas. Entonces parece que Quantum está ganando por 640 bits, pero solo por un orden de magnitud o tres. ¿Entonces tal vez el corte ocurriría en algún lugar alrededor de 500 bits?

De todos modos, sé que esta no es una respuesta difícil y rápida. Pero espero haber transmitido algún sentido de las cantidades en las que pensaría al comparar lo clásico y lo cuántico. Realmente nadie sabe los factores constantes involucrados todavía, por lo que me sorprendería si alguien pudiera darle una estimación adecuada mejor que "en algún lugar de los cientos de bits".

Craig Gidney
fuente
Este es un buen esfuerzo, pero ¿cómo se obtiene la estimación de 30 bits? ¿Con qué compara exactamente el algoritmo de Shor cuando lo considera un posible punto de cruce?
Niel de Beaudrap
1
@NieldeBeaudrap Como dije, es una suposición descabellada. Me imagino: la multiplicación modular tiene un factor constante decente (clásico). Lo mismo ocurre con las fracciones continuas. ¿Los algoritmos de factorización también tienen buenos factores constantes? ¿Probablemente no? Si es así, el crossover ocurriría casi de inmediato en lugar de en grandes números. Si alguien quiere comparar esas dos cosas entre sí, actualizaré la respuesta. Considero que la "carne" es el resto.
Craig Gidney
1
Normalmente no me opondría a esto como una intuición, excepto que su conjetura salvaje es precisamente sobre el tema de la pregunta. (La pregunta también se plantea de tal manera que sugiere la conciencia de los problemas de la velocidad del reloj.) Las técnicas más rápidas para factorizar números muy grandes implican factores constantes grandes, pero en realidad considerarlas es el punto de la pregunta; pero para números de alrededor de mil millones, incluso podríamos considerar la división de prueba usando una tabla de primos de hasta aproximadamente 32,767, lo que sería muy rápido en la práctica. Una comparación cuantitativa incluso con esto sería un comienzo.
Niel de Beaudrap
6

Como mencioné en los comentarios, una respuesta muy precisa probablemente dependerá de muchas opciones técnicas que son algo arbitrarias. Es probable que sea más importante obtener una estimación de orden de magnitud y dar cuenta de la mayor cantidad posible al hacerla.

Esta respuesta no pretende ser una respuesta definitiva, sino un paso en la dirección correcta en referencia a la literatura existente (aunque ciertamente ya tiene más de una década), específicamente:

  • Van Meter, Itoh y Ladd. Tiempo de ejecución dependiente de la arquitectura del algoritmo de Shor . Proc. Superconductividad mesoscópica + Spintronics 2006; [ arXiv: quant-ph / 0507023 ]

Van Meter, Itoh y Ladd intentan comparar el rendimiento del algoritmo de Shor con la tecnología informática disponible que realiza el Tamiz de campo numérico (el algoritmo clásico más conocido para la factorización). No he tenido tiempo de leer los detalles del artículo, probablemente podría obtenerse una respuesta superior al hacerlo, pero la Figura 1 de ese artículo nos permite hacer una estimación numérica razonable:

ingrese la descripción de la imagen aquí

Aquí, las curvas pronunciadas representan el tiempo de computación de las redes informáticas clásicas. La curva etiquetada 'NFS, 104 PC, 2003' parece indicar cálculos (y el tiempo de cálculo proyectado) de ciento cuatro computadoras personales alrededor de 2003, según lo informado por RSA Security Inc. en 2004 [ http: //www.rsasecurity. com / rsalabs / node.asp? id = 2096] .

nnvv2×1011operaciones por segundo. Habría que hacer una evaluación comparativa hipotética del algoritmo de Shor contra una computadora cuántica que funciona a una velocidad de reloj comparable.

109

  • A pesar de una ventaja de operaciones por segundo de un factor de 200 o más, el gráfico indica cuándo esta implementación NFS clásica de 200 GHz es superada por una computadora cuántica de 1 GHz que realiza el algoritmo de Shor (con números de aproximadamente 200 dígitos) y por una computadora cuántica de 1 MHz ( en aproximadamente números de 330 dígitos).
  • También tenemos una curva que proyecta el rendimiento "en 2018", que representa 1000 veces la potencia de cálculo clásica: las intersecciones con las computadoras cuánticas de 1 GHz y 1 MHz están en números de 350 bits y números de 530 bits.

El aumento de los puntos de cruce con los cálculos cuánticos, desde el cálculo en 2003 hasta el proyectado en 2018, que representa un aumento de la velocidad de reloj de 1000, es un factor de aproximadamente 5/3. A partir de esto, podemos estimar que la ventaja computacional del tamaño de los números que una computadora clásica puede resolver rápidamente, debido a un aumento de velocidad de un factor de 200, es aproximadamente 7/6. Luego podemos estimar que el punto de cruce de una sola computadora clásica de 1 GHz que realiza NFS, con una computadora cuántica de 1 GHz que realiza el algoritmo de Shor, es de aproximadamente 170 bits.

El resultado final: una respuesta precisa dependerá de muchos supuestos técnicos que pueden cambiar el resultado preciso significativamente, por lo que es mejor buscar una estimación aproximada. Pero esta pregunta se ha investigado al menos una vez antes, y haciendo algunos supuestos y extrapolaciones sobre el rendimiento basados ​​en el rendimiento clásico en 2003, parece que los algoritmos de Shor superarán al algoritmo clásico más conocido en función de cada operación por números alrededor de 170 bits.

Niel de Beaudrap
fuente
Esta es una buena respuesta. Vale la pena señalar que la idea de este documento de una "operación lógica elemental" está (muy apropiadamente) al nivel de una compuerta AND, a diferencia del nivel de una instrucción de CPU o una operación BigInt (que sospecho es lo que era el autor de la pregunta) pensando). En mi propia respuesta, suponía que la exponenciación modular se hacía "como si fuera clásica", lo que implicaría, por ejemplo, multiplicaciones de FFT. Es por eso que adiviné un número que era mucho más bajo que este documento, que (apropiadamente) hace la multiplicación de libros escolares con sumadores de ondas para su aritmética cuántica.
Craig Gidney
@SalvaCardona: te recomiendo que no aceptes mi respuesta. Mi análisis es muy superficial, y deberías esperar para un mejor análisis.
Niel de Beaudrap