Computación cuántica

Iba a escribir sobre algo entretenido -ahora si- pero de nuevo me sale algo aburrido, que diablos, pero tenía como piedra en el zapato un comentario de hace poco días en este mismo Templo del Ocio. Me estaba dando vueltas la pregunta de Wilson en los comentarios de La encriptación RSA ¿qué diablos es la computación cuántica y para que sirve? Como tenía una idea muy superficial del asunto eludí hábilmente la respuesta, porque como todo buen chileno odio decir "no tengo idea". A propósito, no se si se han fijado que no hay nada que irrite más a un extranjero en Chile que cuando pregunta una dirección lo mandan a cualquier parte, solo por no decirle "no se". La cosa es que me quedó dando vuelta la duda, así es que me puse a curiosear por Internet y esto es más o menos lo que encontré

La computación cuántica se ha desarrollado para mejorar los cálculos de fuerza bruta con computador, que consisten en examinar todas las posibles combinaciones hasta dar con un resultado correcto. Por eso el problema de la factorización de los números grandes es ideal y es probable que todo este desarrollo en principio haya surgido para resolver ese problema.

Los métodos numéricos
Supongamos que queremos averiguar los factores primos del número 18 con un computador normal. Usando fuerza bruta, lo que hacemos es simplemente multiplicar todas las combinaciones posibles de dos números y cuando tenemos los números que multiplicados dan 18 repetimos el proceso con ellos hasta que llegamos a los factores primos, que no pueden seguirse descomponiendo.

Así empezaríamos multiplicando 2*2, 2*3, 2*4....etc, 3*2, 3*3, 3*4... etc, Así hasta que encontramos que 6*3=18, luego tomamos el 6 y repetimos el proceso hasta encontrar que 2*3=6, entonces 2*3*3=18, son los factores de 18, descartando el 3 que se repite los factores primos son 2 y 3. Noten que es una secuencia de muchos cálculos, para este ejemplo sencillo deben hacerse unos cientos, tal vez miles de cálculos, uno tras otro (un matemático que recuerde combinatoria puede decirnos cuantos exactamente), la cosa es que son muchos. ¿Y qué? Los computadores son muy rápidos y pueden hacer miles de cálculos en milisegundos.

Eso fue lo que me enseñaron en "métodos numéricos" cuando lo estudié en 1979 más o menos, me gustó mucho esa idea y el año siguiente llegue a ser ayudante de esa asignatura, era todo cuestión de poner a la estúpida máquina a hacer millones de cálculos, uno tras otro, vigilando bien hacia donde convergía y descartando la dirección donde divergían del resultado buscado.

Fíjense que en estos problemas nosotros conocemos el resultado al que queremos llegar, pero necesitamos saber el cálculo intermedio, eso mismo pasa con todos los problemas de optimización, donde conocemos el óptimo que queremos alcanzar pero necesitamos saber como diablos alcanzarlo, con que combinación de datos.

Hasta aquí todo muy bien, esto funciona con números bastante grandes como cientos, miles y millones, pero ¿qué pasa con los billones, trillones o números de 500 cifras o más? Bueno, por más rápido que sean los computadores, factorizar un número de estos haciendo cálculos, uno tras otro, les puede tomar la edad del universo (sos 13.187 millones de años, más o menos) o incluso mucho más.

¿Para qué neeesitamos factorizar números tan grandes?
En realidad no necesitamos, pero estamos obligados a intentar hacerlo. El problema fundamental de seguridad en Internet es que necesitamos intercambiar claves con seguridad por un canal inseguro. Imaginemos que tenemos un sistema de encriptación inviolable (como es hoy en la práctica el AES por ejemplo), si nos podemos juntar con el destinatario y nos ponemos de acuerdo en usar la clave "TomoParaNoEnamorarmeMeEnamoroParaNoTomar"
Todo será perfecto porque intercambiamos a clave de palabra, pero en la mayoría de los casos prácticos no podemos hacer eso en Internet y necesitamos enviar la clave usando la misma Internet que es insegura.

Para eso se inventó el algoritmo RSA con pares de claves para cada uno, y como hemos visto antes esas claves las podemos intercambiar con seguridad porque es matemáticamente muy difícil factorizar números grandes. Pero difícil no significa imposible, así es que debemos estar constantemente tratando de romper las encriptaciones, antes que otro lo logre y se ponga silenciosamente a robar las claves de otros.

Computación cuántica
Los algoritmos cuánticos se han diseñado pensando en hacer más eficientes y factibles los ataques de fuerza bruta y la idea en general es más o menos simple, aunque endiabladamente difícil de implementar. Se trata de en lugar de hacer cálculos secuenciales, uno tras otro, calcular ondas de probabilidad de cada evento y hacerlas interferir. En la interferencia los eventos de menos probabilidad se anulan y los de más probabilidad se refuerzan, así, en teoría, se podría calcular las mayores probabilidades en un tiempo razonable, porque el cálculo no es secuencial, y después esas mayores probabilidades se comprueban en un computador común y corriente, hasta dar con los factores primos.

Para los que han leído sobre el experimento de la doble rendija, un clásico de la física cuántica experimental que mostró como se comportan los fotones y electrones como ondas, no tendrán mucho problema en entender esto de las interferencias y probabilidades.  Para los que no es interesa el asunto les dejo la idea que la computación cuántica permite obtener ondas de probabilidad con todos los estados posibles simultáneamente así no hay necesidad de hacer trillones de cálculos uno tras otro.

Si se fijan ben, el "mecanismo" de la computación cuántica tiene cierto parecido con la intuición, cuando intuimos algo no calculamos todas las combinaciones sino que saltamos directamente a las combinaciones que nos parecen más probables, por eso la intuición es una especie de lógica abreviada, menos exacta pero muchísimo más rápida.

 Que pasará cuando resuelvan el problema de la factorización y el RSA no sirva
No pasará nada muy terrible, simplemente habrá que buscar otro método para intercambiar las claves y si el RSA se rompe con computación cuántica, más que seguro que esos mismos métodos servirán para hacer un algoritmo mucho más seguro. RSA ha mostrado ser muy robusto en los casi 40 años que se lleva usando, probablemente pasarán muchos años antes que lleguen a romperlo, porque los prototipos de computadores cuánticos que existen hoy son complicadísimos, requieren temperaturas cercanas al cero absoluto, etc. De aquí  que puedan resolver el problema tienen para rato.

Si quieren entretenerse con una buena charla de estas cosas les recomiendo esta de Eduardo Sáenz de Cabezón que se llama "El número que los ordenadores nunca podrán calcular", toda la charla es entretenida pero es muy larga, si quieren ver lo que atañe al RSA vayan directo al minuto 24:18