¿Podría haber un algoritmo de cifrado que una computadora cuántica no pudiera romper por la fuerza bruta?

Si. Las computadoras cuánticas pueden resolver algunos problemas de manera más efectiva que las computadoras clásicas, pero hay muchos más problemas para los cuales probablemente no haya un algoritmo cuántico efectivo. Problemas de celosía: uso en criptografía: Wikipedia es un ejemplo de esquemas que los investigadores creen que son resistentes a la cantidad. (“Creer”: no lo sabemos con certeza, pero eso no es un hecho sorprendente; ni siquiera sabemos algo tan trivial sobre los modelos de computación clásicos como si [math] P \ neq NP [/ math], entonces no sorprende que tampoco podamos decir con una prueba si hay problemas de NP que definitivamente son difíciles en los modelos de computación cuántica.) En general, sabemos que cualquier problema de NP puede resolverse mediante un algoritmo cuántico en el tiempo [matemática] \ sqrt { 2 ^ n} * polinomio (n) [/ math] que es una aceleración significativa suponiendo que creemos en la hipótesis del tiempo exponencial y, por lo tanto, creemos que hay problemas de NP que no se pueden resolver más rápido que [math] 2 ^ n [/ math], pero desde el punto de vista criptográfico (incluso ignorando que generalmente no se trata de problemas NP-completos que usamos en criptografía) eso no es una gran aceleración en absoluto: todo lo que necesita es aumentar todas sus claves dos veces y obtendrá la misma seguridad. Entonces, aunque sabemos que partes de la criptografía clásica serán inútiles frente a los algoritmos cuánticos, también hay partes de la criptografía que no podemos romper con los algoritmos cuánticos y creemos que esto no será posible.