Esencialmente, cómo encontrar el número de ciclos de reloj necesarios para factorizar un número $n$ en un ordenador cuántico con Algoritmo de Shor ? Un ejemplo en cualquier arquitectura sería útil.
Respuesta
¿Demasiados anuncios?
Hacer una estimación precisa es difícil, porque hay muchos factores de los que depende.
- ¿Qué construcciones de circuitos estás utilizando para realizar la exponenciación modular?
- ¿Cómo se realizan las operaciones que no son de Clifford? ¿Cómo se producen los estados mágicos?
- ¿Está limitada la producción del estado mágico o está limitada la medida-reacción-retraso?
- ¿Qué tipo de optimizaciones topológicas y de circuitos está aplicando? ¿Está realizando optimizaciones sobre la marcha? ¿Qué eficacia tienen en promedio?
- ¿Qué tipo de sobrecarga hay en términos de mover los qubits para que puedan interactuar?
Las respuestas a estas preguntas están en constante evolución a medida que se realizan más investigaciones. Para una estimación histórica, véase el documento " Códigos de superficie: Hacia una computación cuántica práctica a gran escala ". Utilizan un circuito de exponenciación modular que utiliza $\approx 280 N^3$ Puertas T dispuestas en $\approx 120 N^3$ capas (separadas por puertas Clifford, que tienen un coste insignificante en comparación).
Si se dispone de muchos más qubits, se pueden utilizar circuitos con mejor complejidad asintótica. $\tilde{O}(N)$ profundidad y $\tilde{O}(N^2)$ cuenta son fácilmente alcanzables con los algoritmos de multiplicación clásicos conocidos, pero pueden no ser mejores para los tamaños de clave RSA típicos. También hay muchas mejoras posibles de factor constante. Por ejemplo, las puertas de Toffoli en un par de computación/descomputación sólo requieren 4 puertas T en total en lugar de 14. Sólo el tiempo dirá lo que realmente se utiliza.
