Sobre clases de complejidad y oráculos

La superioridad de los ordenadores cuánticos

En mayo de este año, 2018, dos teóricos de la computación han demostrado que entre lo que puedan llegar a hacer los ordenadores cuánticos y los clásicos hay una brecha insalvable.

Los ordenadores cuánticos ya existen aunque de tamaño muy pequeño y desde luego no con aplicaciones industriales. Todavía es una tecnología embrionaria, pero dos teóricos de la computación acaban de demostrar lo que muchos en el campo intuían. Aun suponiendo que los ordenadores clásicos actuales aumentasen en capacidad, velocidad etc. de una forma prácticamente inimaginable en una civilización futura no van a poder resolver problemas que los ordenadores cuánticos sí podrán. Ya el mero nombre, ordenador cuántico, parece demostrar su superioridad, pero no se había demostrado hasta ahora ni siquiera en el terreno teórico.

Los ordenadores cuánticos se basan en lo que se conoce como qubit (quantum bit) en contraposición con los bits binarios de los ordenadores clásicos que toman los valores 0 y 1. Un qubit es un sistema cuántico de dos estados como pueda ser la polarización de un único fotón. En este caso los dos estados serían la polarización vertical y la polarización horizontal. En un ordenador normal o se tiene un estado o se tiene el otro. Hay corriente eléctrica o no la hay. En uno cuántico lo normal es que exista una superposición de esos dos estados.“La encriptación de datos funciona porque la factorización en números primos es muy difícil”

De entrada el que pueda ser una superposición muestra que puede contener mucho más información que un único bit, pero podría ser que teniendo suficientes bits se pudiese compensar el poder del qubit. Para muchas cuestiones esto puede ocurrir y hace 25 años cuando empezó el estudio de los ordenadores cuánticos los teóricos de la computación se preguntaron si habría problemas irresolubles para los ordenadores que tenemos ahora, que sí se podrían resolver con ordenadores cuánticos.

25 años más tarde en mayo de este año Ran Raz de la Universidad de Princeton y Avishay Tal de la Universidad de Stanford han conseguido la demostración teórica de que hay toda una categoría de problemas con esas características.

La demostración es bastante abstracta, pero vamos a tratar de esbozar algunos elementos que le permitan al lector entender por dónde van los tiros y además ver cómo los ordenadores y las matemáticas están íntimamente ligadas. No se trata de un avance tecnológico sino de un avance conceptual.

Clases de complejidad

En teoría de computación se habla de clases de complejidad. Hay una clase de complejidad que se denomina P y otra que se denomina NP. La primera clase P son problemas que los ordenadores pueden resolver de forma rápida, en términos técnicos en tiempo polinomial. Un ejemplo es saber si un número es primo o no.

Los problemas NP son problemas que no se pueden resolver necesariamente de forma rápida, pero sin embargo dada una posible solución, se puede calcular rápidamente si es solución o no. Un ejemplo sería la factorización en números primos. Dado un número los ordenadores no saben calcular rápidamente los factores, pero sí pueden calcular rápidamente, dada una factorización, si es correcta o no.

Esto aunque parezca muy abstracto está en la base de aplicaciones prácticas directas. Por ejemplo la encriptación de datos. La base de la encriptación actual está en el hecho de que es muy fácil multiplicar dos números primos enormes. Ahora, si uno no tienes esos dos factores, dado el resultado de esa multiplicación, es muy difícil calcular esos dos factores. Osea multiplicación fácil, factorización difícil. Tan difícil que la encriptación de datos funciona porque se utilizan números tan grandes que la factorización en números primos es prácticamente imposible. No hay tiempo suficiente para hacer esa factorización que implicaría descifrar el mensaje.

Volviendo a las clases de complejidad P y NP, los teóricos de la computación creen que son dos clases bien distintas, pero de hecho no se ha demostrado todavía. Es uno de los 7 ¨problemas del milenio¨ y al que lo resuelva le espera un millón de dólares.

Los científicos que han demostrado la superioridad del ordenador cuántico no se han metido en ese problema del milenio. De hecho han mostrado que aunque resulte que los problemas de clase NP se puedan resolver rápidamente por los ordenadores clásicos, aun así los ordenadores cuánticos son superiores.

La clase cuántica

En 1993 los teóricos de la computación Ethan Bernstein y Umesh Vazirani introdujeron la clase de complejidad cuántica BQP. Ese mismo año mostraron que todos lo problemas que un ordenador clásico puede resolver rápidamente también los puede resolver uno cuántico de manera eficiente. Sin embargo como hemos dicho, hasta ahora no estaba claro que la clase cuántica BQP verdaderamente contenía problemas que no se pueden resolver de ninguna manera por uno clásico.“Ningún país puede permitirse quedar atrás en la tecnología cuántica.”

Raz y Tal para su demostración consideraron el problema siguente. Supongamos que tenemos dos generadores diferentes de números aleatorios que producen una secuencia de números. La pregunta al ordenador es: ¿son las dos secuencias totalmente independientes una de la otra, o están relacionadas de alguna manera? En 2009 Scott Aaronson demostró que era un problema resoluble por un ordenador cuántico aunque esa relación de una secuencia con la otra sea bastante oculta. Ahora Raz y Tal han demostrado que este problema no se puede resolver con un ordenador al uso.

Para ello han tenido que utilizar un artilugio, un argumento de tipo ¨oráculo¨ que no vamos a poder explicar en más detalle. Una forma de medir la complejidad de un problema es el tiempo que se necesita para resolverlo. Otra forma es cuántas ¨pistas¨ necesitas de un ¨oráculo¨ para resolver el problema. Demostraron que para el ordenador cuántico una pista sería suficiente, mientras que para uno clásico ni con el oráculo délfico sería suficiente.

Las tecnologías cuánticas en España

No hace falta ser un oráculo délfico para intuir que las tecnologías cuánticas son el futuro.

Un campo estratégico para la comunicación y encriptación, por tanto también de aplicaciones militares. Sólo hace falta recordar los ataques cibernéticos. Sin embargo la financiación de éstas es muy, muy lamentable en España como nos ha comentado recientemente Juan José García Ripoll en una entrevista para De Verdad TV. García Ripoll es líder del grupo sobre información y fundamentos cuánticos del Instituto de Fisica Fundamental del CSIC.

Se ha dado un paso importante a nivel teórico en la computación cuántica. Según García Ripoll los físicos teóricos españoles de la información cuántica son muy reconocidos a nivel mundial. Esperemos que con los vientos de cambio que soplan esto ocurra en mayor medida también a nivel nacional y se puedan explorar mejor las posibilidades del mundo cuántico y sus aplicaciones. Ningún país puede permitirse quedar atrás en la tecnología cuántica. Menos un país que tiene a teóricos de vanguardia en ese campo.

2 comentarios sobre “La superioridad de los ordenadores cuánticos”

Deja una respuesta