Impacto de Quantum Computers, que no sean nuevos algoritmos

Lo que sucede con la computación cuántica es que aún no sabemos .

Algunos pensamientos:

• Si alguna vez alcanzamos una verdadera computadora cuántica, es probable que sea significativamente más rápido que las computadoras clásicas, cuando la velocidad se mide de manera similar.
• Si va a ser más rápido, no sabemos cuánto más rápido hasta que construimos uno. Los prototipos actuales están lejos de ser completos, e incluso las demostraciones "hito" de la tecnología son cuestionables.
• La computación cuántica ofrece un atajo potencial para ciertas operaciones, ya que puede usar varias formas de trucos de la mecánica cuántica para producir resultados previamente "desconocidos" a partir de valores de entrada.
• Sin embargo, los resultados cuánticos son probabilísticos; En realidad, no es tan concreto como decir "es rápido", porque tienes que hacerlo rápido y correcto . No es fácil de hacer.
• Si puede encontrar un atajo cuántico para un problema, construir una computadora cuántica e implementar ese atajo dentro de la computadora, y encontrar una manera de obtener el resultado con p > 0.5, está en pista.
• El gran "potencial" es para el algoritmo de Shor, que podría reducir la complejidad computacional de la factorización semiprime a una clase lo suficientemente baja para que podamos factorizar números muy grandes en un tiempo más corto que con los algoritmos clásicos .
• Es un gran "si". No sabemos si realmente reducirá la complejidad computacional, ni tampoco sabemos si es posible una implementación eficiente. Incluso si podemos lograr ambas cosas, no sabemos cuánta reducción en la complejidad obtendremos. La esperanza es que obtendremos O ((log N) ³ ), pero no sabemos realmente si alguna vez podemos alcanzar eso en una implementación real. E incluso si ese es el caso, aún requiere una cantidad de cómputo masiva , lo que nos lleva al segundo punto que mencioné: no sabemos qué tan rápido pueden ser las computadoras cuánticas realmente.
• Incluso rompemos problemas de factorización de semiprime como RSA, Quantum Crypto trae nuevos problemas que no se pueden resolver fácilmente, lo que significa que todavía tendremos una nueva forma de mantener las cosas seguras.

No entendí completamente tu pregunta, pero lo intentaré. Por lo que recuerdo, esa computadora cuántica le permitirá resolver de manera eficiente una clase de problema que es BQP (por el factor de conocimiento actual en BQP), que es más grande que P, pero no consta de todo NP. Así que no te permitirán resolver NP de manera eficiente.

Grovers dará una aceleración de sqrt (n) para problemas NP-completos. Entonces, si tienes 2 ^ n estados, aplicando el algoritmo Grovers podrás reducirlo a 2 ^ (n / 2), lo que es realmente bueno, pero aún exponencial.

Hay otros algoritmos que ya se pueden usar. Si bien la factorización primaria relativa es el problema más comúnmente usado para la criptografía asimétrica, hay una serie de otros problemas conocidos (que no puedo recordar de la parte superior de mi cabeza en este momento) que actualmente no tienen un algoritmo cuántico conocido para resolver . Así que a corto plazo, si / cuando existen las computadoras cuánticas, todavía tenemos una serie de algoritmos que se consideran seguros.

La otra cara de esto es que si se generalizan, podríamos utilizar criptografía cuántica de gran distribución, como Quantum Key Distribution. Según tengo entendido, la idea básica es que puede utilizar los principios de la mecánica cuántica para garantizar que solo haya un transmisor y un solo receptor de la información, de modo que sea realmente físicamente imposible para un atacante obtener un acceso significativo a la información, ya que si existe. Si dos personas leyeran los datos, se convertiría en un desastre confuso.