Algoritmo de Shor velocidad

Soy un erudito novato en ciencias de la computación, y me piden que escriba un artículo que implique la factorización de enteros. Como resultado, tengo que investigar el algoritmo de Shor en computadoras cuánticas.

Para los otros algoritmos, pude encontrar ecuaciones específicas para calcular el número de instrucciones del algoritmo para un tamaño de entrada dado (a partir del cual pude calcular el tiempo requerido para calcular en una máquina con una velocidad dada). Sin embargo, para el algoritmo de Shor, lo más que puedo encontrar es su complejidad: O( (log N)^3 ).

¿Hay alguna forma de encontrar su velocidad / complejidad real a partir de su notación Big-O? Si no, ¿hay alguien que pueda decirme lo que quiero o cómo encontrarlo?

La mejor estimación que conozco se puede encontrar en Redes eficientes para la factorización cuántica , por David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni y John Preskill, que da$72 (\log N)^3$.

Dicho esto, una comparación directa del número de pasos en una computadora cuántica versus el número de pasos en una computadora clásica es problemática por varias razones. Primero, como dice la respuesta de DW, el número de pasos depende de la arquitectura exacta de la computadora cuántica, que no tendremos hasta que se construya uno. En segundo lugar, es probable que el tiempo requerido para un solo paso en una computadora cuántica sea bastante más lento que un solo paso en una computadora clásica. ¹ Nuevamente, no sabremos cuánto más lento hasta que existan computadoras cuánticas.

¹ Si fuera más rápido, podría usar la misma arquitectura para construir una computadora clásica que sería al menos tan rápida, y probablemente más rápida porque para una computadora clásica, no necesita preocuparse por mantener la coherencia cuántica.

Lo que está pidiendo no existe, por buenas razones.

Hoy no hay una computadora existente que pueda ejecutar el algoritmo de Shor. Para ejecutar el algoritmo de Shor, necesita una computadora cuántica, que aún no existe. Por lo tanto, no debe esperar estimaciones precisas de su velocidad o tiempo de ejecución, ya que eso dependerá de los detalles de la computadora en la que se ejecuta el algoritmo, y posiblemente no podamos conocer esos detalles hasta que hayamos construido con éxito uno .