Que son las Computadoras Cuánticas y como pueden romper los cimientos de la criptografía actual

La base de la criptografía moderna, es decir, de la confidencialidad de la información que enviamos por internet, se basa en la encriptación asimétrica, que permite compartir las llaves de encriptación de manera pública. Diffie-Hellman (DH) y RSA son los algoritmos más usados para este propósito.

Romper un algoritmo de encriptación RSA, por ejemplo, implica encontrar los factores primos de un numero enormemente grande (más de 500 dígitos). No existe ningún algoritmo conocido para factorizar números primos eficientemente. Intentar romperlo por fuerza bruta implica probar una descomunal cantidad de opciones que, incluso a la supercomputadora más potente, le tomaría más tiempo que el que lleva existiendo el universo.

Existe, no obstante, un método que explota una propiedad especifica de la factorización y nos permite traducir el problema de la factorización en otro. Esta estrategia, que se basa en el teorema de Euler, es algo difícil de explicar con palabras (es más fácil como un ejemplo), pero lo intentaremos.

Si tenemos un número N que es el producto de 2 primos p y q, siempre podemos encontrar un numero r, para cualquier g que elijamos (siempre que g sea menor que N y no comparta divisores con N) tal que:
g^r = k∙N + 1 (y k es un número natural).

Es decir, si multiplicamos g por sí mismo, r veces, en algún momento el resultado será múltiplo de N más 1. En otras palabras, el resto de (g^r)/N, será 1. Y, además, si seguimos multiplicando por g, la secuencia de restos de la división se repetirá eternamente con un periodo r.

Esta propiedad es clave porque puede demostrarse que, si podemos obtener r, podremos, por medio de aritmética sencilla, averiguar los números primos p y q, que es lo que necesitamos para romper la encriptación RSA.

Pero este nuevo problema, sigue siendo un problema intratable para una computadora clásica, es decir, que el tiempo de resolución del problema mediante un algoritmo crece exponencialmente con la complejidad del problema. Esa es la clave de la encriptación asimétrica: no existe un algoritmo efectivo que pueda resolverlo en un tiempo razonable. Sin embargo, el escenario es diferente en una computadora cuántica. Alli sí existe un algoritmo (algoritmo de Shor, propuesto en 1994), que hace que este problema no sea intratable y pueda resolverse en tiempos muy breves.

Una computadora cuántica utiliza las leyes de la mecánica cuántica para implementar el qbit. No vamos a entrar en detalles técnicos sobre mecánica cuántica aquí, solo aceptemos que un qbit es una propiedad especifica de una partícula elemental, como el electrón (su polarización por ejemplo). Y al igual que su equivalente clásico, el bit, es la unidad de procesamiento de información. Pero a diferencia del bit, que solo puede valer 0 o 1, el qbit puede estar en una superposición arbitraria de ambos estados.

La superposición cuántica es la clave de la computación cuántica y a la vez su talón de Aquiles. Nos permite en cierta forma una paralelización exponencial de cómputo (en múltiples universos, si aceptamos la interpretación de “Muchos Mundos” de la mecánica cuántica, como sostiene David Deutsch, uno de los pioneros y principales contribuyentes de la computación cuántica). Esta paralelización exponencial de cómputo es la que permite transformar un problema de complejidad exponencial en un problema de complejidad polinómica, es decir, permite ser tratable y obtener un resultado en tiempos razonables.

Pero también es su talón de Aquiles porque esa computación exponencialmente paralela tiene un problema que es intrínseco a la mecánica cuántica. La superposición no puede ser observada en simultaneo, pues esos “mundos” son ortogonales. Para obtener un resultado concreto es necesario observar la superposición y, al hacerlo, la destruimos y solo podremos observar un elemento de esta superposición, los demás, se pierden. Por esta razón es clave la implementación de un algoritmo cuántico adecuado que permita recuperar de entre todos los elementos de la superposición el o los elementos que necesitamos.

Para implementar el algoritmo de Shor, que es el que permite factorizar números primos rapidamemte, es necesario poner en superposición unos pocos miles de qbits.
Con esta superposición calculamos los restos de (g^r)/N (normalmente expresado como g^r mod N). Sabemos que estos restos se repetirán cíclicamente con un periodo r (que en un ejemplo real puede tener cientos de dígitos) y que puede ser encontrado aplicando una función matemática llamada transformada de Fourier, que en este caso será una transformada cuántica de Fourier (QFT).
Luego mediante una serie de cálculos que surgen del teorema de Euler podremos obtener 2 números que comparten divisores con los 2 números primos que queremos encontrar. Y finalmente usando el algoritmo de Euclides podemos encontrar esos divisores que serán precisamente los números primos que buscamos.

En resumen, la computación cuántica, a través de la superposición cuántica permite realizar un número increíblemente enorme de cálculos en paralelo (y cuando digo increíblemente, me quedo corto, inimaginablemente, sería más apropiado). Y el algoritmo de Shor, a través de la transformada cuántica de Fourier (QFT) nos permite extraer de esa inimaginablemente enorme cantidad de información superpuesta (que no puede ser observada sin destruirla) una aguja en un pajar que es el periodo r de repetición de restos y con ellos calcular de manera simple (podríamos hacerlo con una computadora hogareña) los numero primos p y q que forman N y así romper el algoritmo de encriptación que sustenta las bases de la confidencialidad de la información que compartimos en internet.

Ahora bien, ¿cuánto falta para que podamos hacer esto? No lo sabemos con certeza, pero con la tendencia actual, se estima que entre 10 y 30 años.

¿Qué alternativas hay para cuando llegue este momento? Hace tiempo que se están ideando, desafíos matemáticos que sean intratables incluso para una computadora cuántica. Y hay muchas opciones.

Más allá del hype creado por artículos de divulgación, una computadora cuántica no puede resolver cualquier problema. Un problema que no puede ser resuelto por una computadora clásica (máquina de Turing) sigue siendo incomputable en una computadora cuántica. Simplemente, las computadoras cuánticas permiten resolver algunos problemas específicos en tiempos exponencialmente menor.