Depende en gran medida del esquema de cifrado. Por supuesto, como señala Alon Amit, una computadora cuántica no funciona como muchas computadoras clásicas en paralelo, pero los algoritmos cuánticos que se han propuesto se pueden aplicar al descifrado de códigos.
Si hablamos del cifrado RSA, un esquema de clave pública de uso común que se basa en la dificultad de factorizar números grandes, una computadora cuántica completamente ampliada debería ser capaz de descifrar el código muy rápidamente. El algoritmo de Shor puede factorizar números exponencialmente más rápido que cualquier algoritmo clásico conocido. Es decir, si una computadora cuántica puede romper un cifrado RSA de 128 bits en un segundo, solo lleva unos segundos romper una clave de 256 bits. Mientras que si una computadora clásica, utilizando los algoritmos de factorización disponibles, puede romper una clave de 128 bits en un segundo, ni siquiera piense en intentar romper una clave de 256 bits.
Si el esquema de cifrado no es RSA, entonces la computación cuántica puede ayudar, pero probablemente no de manera tan dramática. Si, por ejemplo, se usa una clave privada, puede intentar descifrar el código por fuerza bruta, probando cada clave. Para N claves posibles, el tiempo para esto se escala como N. En este caso, el algoritmo de Grover se puede aplicar si tiene una computadora cuántica. El algoritmo de Grover busca en el tiempo una base de datos de elementos N sin clasificar que se escala como sqrt (N). (Desea buscar en la base de datos de todas las claves posibles la que convierte el mensaje codificado en texto). De este modo, obtiene una mejora cuadrática. Desafortunadamente para el descifrador de códigos, si puede romper la clave de 128 bits en un segundo, el tiempo para la clave de 256 bits es ridículamente largo, ya sea que use la fuerza bruta clásica o el algoritmo de Grover.
- ¿Cuáles son las grandes ideas sobre la mecánica cuántica?
- ¿La presión tiene un origen mecánico cuántico?
- ¿Se puede usar el lenguaje de programación utilizado hoy para la computación cuántica?
- Cómo trabajar en computación cuántica en Google
- La singularidad tecnológica: ¿cuánto poder informático se necesitaría para ejecutar una simulación de antepasados para todos los que alguna vez existieron en la Tierra?
Los tiempos absolutos son difíciles de dar sin saber cómo se implementa la computadora cuántica. Sin embargo, cada “ejecución” del algoritmo cuántico debe tener lugar dentro del tiempo de coherencia de los qubits, que generalmente está en el rango de microsegundos a segundos, dependiendo del qubit propuesto. Necesita ejecutar esto varias veces para obtener el resultado. Creo que el algoritmo de Shor no necesita ejecutarse demasiadas veces, probablemente en el orden del número de qubits en el sistema. Para algo así como 10 ^ 4 qubits, esto daría escalas de tiempo que van desde 0.01s a 3 horas. El algoritmo de Grover debe ejecutarse ~ sqrt (N) veces, donde N es el número de claves posibles. Para cualquier N apreciablemente grande, digamos 2 ^ 256, este es un tiempo ridículamente largo.
