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

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?

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\rangle$

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".

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:

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] .

$n$$n \cdot v$$v$$2 \times 10^{11}$operaciones 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.

$10^9$

• 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.