¿Qué tan rápido puede una computadora cuántica romper una contraseña en comparación con una computadora normal?

Romper una contraseña es un problema para las computadoras convencionales porque entra en una clase de problemas que se sabe que no son polinomiales (NP).

Estos problemas son los que sabemos cómo resolver utilizando nuestros algoritmos actuales, pero en realidad no podemos resolverlos porque la cantidad de recursos (generalmente tiempo o memoria) es demasiado grande.

Al no ser polinomiales, generalmente se caracterizan por un tiempo de ejecución que es del orden de factorial n. Es decir, Texec = O (n!).

A modo de comparación, para ordenar una lista de palabras en orden alfabético tiene Texec = O (n.ln (n)) en el mejor caso, o Texec = O (n ^ 2) en el caso de un tipo simple de algoritmo de clasificación de burbujas .

En su caso, n podría ser la longitud de la contraseña, en bits. Por lo tanto, no hay problema en descifrar esto en computadoras convencionales para longitudes de contraseña lo suficientemente pequeñas. El usuario consciente de la seguridad, por lo tanto, solo debe intentar hacer que su contraseña sea lo suficientemente larga como para que O (n!) Sea mayor que la vida útil del planeta (por ejemplo) … que se alcanza, de hecho, a valores bastante razonables de norte. (Tenga en cuenta que aquí estoy simplificando deliberadamente … lo más preocupante es la longitud de las claves utilizadas por los sistemas de seguridad de Internet).

Ahora, según la aproximación de Stirling, O (n!) ~ O (exp (-n) .n ^ n).
Como señala Quora User, el objetivo de las computadoras cuánticas es poder convertir esta clase de algoritmo no polinomial (NP) en un polinomio simple, haciendo que la búsqueda, la clasificación y la exploración del espacio de diseño sean manejables, incluso para valores bastante grandes de norte.

Todavía necesita los recursos … que no tenemos en este momento … la computadora cuántica más grande hasta la fecha todavía está restringida en la cantidad de hardware (y la cantidad de qubits) que tiene.

En teoría, una computadora cuántica que puede hacer malabarismos con “n” bits cuánticos puede realizar 2 ^ n operaciones en paralelo. Yo creo que. Sin embargo, es REALMENTE difícil mantener n bits en el aire. Algo relacionado con la decoherencia, que mi limitado poder cerebral encuentra incoherentemente.

De todos modos, teóricamente, realmente pueden ir rápidamente, suponiendo que no haya una enorme lentitud constante por operación que el factor 2 ^ n no pueda superar. Verá que nuestras viejas computadoras no cuánticas pueden realizar miles de millones de operaciones por segundo, utilizando miles de millones de puertas. Una computadora cuántica tendría que ser igualmente rápida en las operaciones básicas y en la lectura de los resultados. Todo un reto.