La computación cuántica es una de esas tecnologías que es tan arcana que los personajes de TV la abandonan cuando quieren sonar inteligentes.
La computación cuántica como una idea ha existido por un tiempo; la posibilidad teórica fue presentada originalmente por Yuri Manin y Richard Feynman en 1982. Sin embargo, en los últimos años, el campo ha estado acercándose preocupantemente más cerca de lo práctico.
Empresas como Google y Microsoft, así como agencias gubernamentales como la NSA han estado buscando febrilmente computadoras cuánticas desde hace años. Una compañía llamada D-Wave ha producido y está vendiendo dispositivos que (si bien no son computadoras adecuadas, y solo pueden ejecutar algunos algoritmos) explotan las propiedades cuánticas, y son otro paso gradual en el camino hacia un completo Turing completo. ¿La prueba de Turing y alguna vez será vencida? ¿Qué es la prueba de Turing y alguna vez será vencida? La prueba de Turing está destinada a determinar si las máquinas piensan. ¿El programa Eugene Goostman realmente pasó la prueba de Turing, o los creadores simplemente hicieron trampa? Leer más máquina cuántica.
No parece irrazonable decir que pueden ocurrir avances que permitirán construir la primera computadora cuántica a gran escala dentro de una década.
Entonces, ¿por qué todo el interés? ¿Por qué debería importarte? Las computadoras se vuelven más rápidas todo el tiempo ¿Qué es la ley de Moore y qué tiene que ver contigo? [MakeUseOf Explains] ¿Cuál es la ley de Moore y qué tiene que ver contigo? [MakeUseOf Explains] La mala suerte no tiene nada que ver con la Ley de Moore. Si esa es la asociación que tenía, la está confundiendo con la Ley de Murphy. Sin embargo, no estabas muy lejos porque la Ley de Moore y la Ley de Murphy ... Leer más: ¿qué tienen de especial las computadoras cuánticas?
Para explicar por qué estas máquinas son tan importantes, vamos a tener que dar un paso atrás y explorar exactamente qué son las computadoras cuánticas y por qué funcionan. Para comenzar, hablemos de un concepto llamado "complejidad de tiempo de ejecución".
¿Qué es la Complejidad de Runtime?
Una de las grandes sorpresas en los primeros días de la informática fue el descubrimiento de que, si tiene una computadora que resuelve un problema de cierto tamaño en un cierto período de tiempo, doblar la velocidad de la computadora no necesariamente le permite abordar los problemas. el doble de grande
Algunos algoritmos aumentan el tiempo de ejecución total muy, muy rápido a medida que aumenta el tamaño del problema: algunos algoritmos pueden completarse rápidamente dados 100 puntos de datos, pero completar el algoritmo dado 1000 puntos de datos requeriría una computadora del tamaño de la Tierra corriendo por un mil millones de años. La complejidad del tiempo de ejecución es una formalización de esta idea: mira la curva de cuán rápido crece la complejidad de un problema y usa la forma de esa curva para clasificar el algoritmo.
Generalmente, estas clases de dificultad se expresan como funciones. Un algoritmo que se vuelve proporcionalmente más difícil cuando el conjunto de datos trabaja (como una función de conteo simple) se dice que es una función con una complejidad de tiempo de ejecución de " n" (como en, toma n unidades de tiempo para procesar n puntos de datos) )
Alternativamente, podría llamarse "lineal", porque cuando lo graficas, obtienes una línea recta. Otras funciones podrían ser n ^ 2 o 2 ^ n o n! (n factorial). Estos son polinomios y exponenciales. En los últimos dos casos, los exponenciales crecen tan rápido que en casi todos los casos no pueden resolverse por nada excepto por ejemplos muy triviales.
Complejidad de tiempo de ejecución y criptografía
Si estás escuchando esto por primera vez y parece absurdo y arcano, intentemos fundamentar esta discusión. La complejidad del tiempo de ejecución es crítica para la criptografía, que se basa en hacer que el descifrado sea mucho más fácil para las personas que conocen una clave secreta que para quienes no la conocen. En un esquema criptográfico ideal, el descifrado debe ser lineal si tiene la clave, y 2 ^ k (donde k es el número de bits en la clave) si no lo hace.
En otras palabras, el mejor algoritmo para descifrar el mensaje sin la clave debe ser simplemente adivinar las posibles claves, que es difícil de manejar para claves de solo unos cientos de bits de longitud.
Para la criptografía de clave simétrica (en la que las dos partes tienen la posibilidad de intercambiar un secreto de forma segura antes de iniciar la comunicación), esto es bastante fácil. Para la criptografía asimétrica, es más difícil.
La criptografía asimétrica, en la que las claves de cifrado y descifrado son diferentes y no se pueden calcular fácilmente entre sí, es una estructura matemática mucho más difícil de implementar que la criptografía simétrica, pero también mucho más poderosa: la criptografía asimétrica le permite tener conversaciones privadas, incluso sobre líneas golpeadas! También le permite crear "firmas digitales" para permitirle verificar de quién vino un mensaje y que no ha sido alterado.
Estas son herramientas poderosas y constituyen la base de la privacidad moderna: sin la criptografía asimétrica, los usuarios de dispositivos electrónicos no tendrían una protección confiable contra miradas indiscretas.
Debido a que la criptografía asimétrica es más difícil de construir que simétrica, los esquemas de cifrado estándar que se usan en la actualidad no son tan sólidos como podrían ser: el estándar de encriptación más común, RSA, se puede descifrar si se pueden encontrar de manera eficiente los factores primarios de un gran número. La buena noticia es que ese es un problema muy difícil.
El algoritmo mejor conocido para factorizar grandes números en sus primos de componente se llama filtro de campo de número general, y tiene una complejidad de tiempo de ejecución que crece un poco más lento que 2 ^ n . Como consecuencia, las claves tienen que ser unas diez veces más largas para proporcionar una seguridad similar, que es algo que la gente normalmente tolera como un costo de hacer negocios. La mala noticia es que todo el campo de juego cambia cuando las computadoras cuánticas se lanzan a la mezcla.
Computadoras cuánticas: cambiar el juego Crypto
Las computadoras cuánticas funcionan porque pueden tener múltiples estados internos al mismo tiempo, a través de un fenómeno cuántico llamado "superposición". Eso significa que pueden atacar diferentes partes de un problema simultáneamente, dividirse en posibles versiones del universo. También se pueden configurar de manera tal que las ramas que resuelven el problema terminen con la mayor amplitud, de modo que cuando abres la caja en el gato de Schrodinger, la versión del estado interno con la que es más probable que te presenten es una presunción gato que mira sosteniendo un mensaje descifrado.
Para obtener más información acerca de las computadoras cuánticas, consulte nuestro artículo reciente sobre el tema ¿Cómo funcionan las computadoras ópticas y cuánticas? ¿Cómo funcionan las computadoras ópticas y cuánticas? La edad de Exascale está llegando. ¿Sabe cómo funcionan las computadoras ópticas y cuánticas, y estas nuevas tecnologías se convertirán en nuestro futuro? Lee mas !
El resultado de esto es que las computadoras cuánticas no son solo linealmente más rápidas, como las computadoras normales: obtener dos o diez o cien veces más rápido no ayuda mucho cuando se trata de la criptografía convencional que eres cientos de miles de millones de veces demasiado lento para procesar. Las computadoras cuánticas admiten algoritmos que tienen complejidades de tiempo de ejecución de menor crecimiento de las que de otro modo serían posibles. Esto es lo que hace a las computadoras cuánticas fundamentalmente diferentes de otras tecnologías computacionales futuras, como el grafeno y el cálculo memrister. La última tecnología informática que tiene que ver para creer. La última tecnología informática que tiene que ver para creer. Vea algunas de las últimas tecnologías informáticas para transformar el mundo de la electrónica y las computadoras en los próximos años. Lee mas .
Para un ejemplo concreto, el Algoritmo de Shor, que solo puede ejecutarse en una computadora cuántica, puede factorizar grandes números en log (n) ^ 3 veces, lo cual es drásticamente mejor que el mejor ataque clásico. Usar el tamiz de campo de número general para factorizar un número con 2048 bits requiere aproximadamente 10 ^ 41 unidades de tiempo, lo que equivale a más de un trillón billón de billones. Usando el algoritmo de Shor, el mismo problema solo toma alrededor de 1000 unidades de tiempo.
El efecto se hace más pronunciado cuanto más largas son las teclas. Ese es el poder de las computadoras cuánticas.
No me malinterpreten: las computadoras cuánticas tienen muchos usos potenciales no malvados. Las computadoras cuánticas pueden resolver de manera eficiente el problema del vendedor ambulante, lo que permite a los investigadores construir redes de envío más eficientes y diseñar mejores circuitos. Las computadoras cuánticas ya tienen un uso poderoso en inteligencia artificial.
Dicho eso, su papel en la criptografía será catastrófico. Las tecnologías de encriptación que permiten que nuestro mundo siga funcionando dependen del problema de la factorización de enteros que es difícil de resolver. RSA y los esquemas de cifrado relacionados son los que le permiten confiar en que está en el sitio web correcto, que los archivos que descarga no están plagados de malware y que las personas no están espiando su navegación por Internet (si está utilizando Tor).
La criptografía mantiene segura su cuenta bancaria y asegura la infraestructura nuclear mundial. Cuando las computadoras cuánticas se vuelven prácticas, toda esa tecnología deja de funcionar. La primera organización en desarrollar una computadora cuántica, si el mundo todavía trabaja en las tecnologías que usamos hoy, estará en una posición terriblemente poderosa.
Entonces, ¿es inevitable el apocalipsis cuántico? Hay algo que podamos hacer al respecto? Como resultado ... sí.
Criptografía post-cuántica
Existen varias clases de algoritmos de cifrado que, hasta donde sabemos, no son significativamente más rápidos de resolver en una computadora cuántica. Estos son conocidos colectivamente como criptografía post-cuántica, y brindan cierta esperanza de que el mundo pueda hacer la transición a criptosistemas que permanecerán seguros en un mundo de encriptación cuántica.
Los candidatos prometedores incluyen encriptación basada en celosía, como Ring-Learning With Error, que deriva su seguridad de un problema de aprendizaje de máquina demostrablemente complejo y criptografía multivariada, que deriva su seguridad de la dificultad de resolver sistemas muy grandes de ecuaciones simples. Puede leer más sobre este tema en el artículo de Wikipedia. Cuidado: muchas de estas cosas son complejas, y es posible que descubras que tus conocimientos de matemática deben reforzarse considerablemente antes de que puedas profundizar en los detalles.
El resultado de mucho de esto es que los criptoschemes post-quantum son muy geniales, pero también muy jóvenes. Necesitan más trabajo para ser eficientes y prácticos, y también para demostrar que son seguros. La razón por la que podemos confiar en los criptosistemas es porque les hemos arrojado suficientes genios paranoicos clínicamente por el tiempo suficiente como para que ya se hayan descubierto las deficiencias obvias, y los investigadores han demostrado varias características que los hacen fuertes.
La criptografía moderna depende de la luz como desinfectante, y la mayoría de los esquemas criptográficos post-cuánticos son simplemente demasiado nuevos para confiar en la seguridad mundial. Están llegando allí, sin embargo, y con un poco de suerte y algo de preparación, los expertos en seguridad pueden completar el cambio antes de que la primera computadora cuántica se ponga en línea.
Sin embargo, si fallan, las consecuencias pueden ser nefastas. La idea de que alguien tenga ese tipo de poder es inquietante, incluso si eres optimista acerca de sus intenciones. La cuestión de quién desarrolla primero una computadora cuántica en funcionamiento es algo que todos deberían observar con atención a medida que avanzamos hacia la próxima década.
¿Le preocupa la inseguridad de la criptografía en las computadoras cuánticas? ¿Cuál es tu opinión? ¡Comparte tus pensamientos en los comentarios a continuación!
Créditos de las imágenes: Orbe binario Via Shutterstock