Hoy es el día en el que los muchachos de D-Wave planean hacer la presentación de su sistema cuántico Orión, tal como Alvy nos acaba de recordar en Microsiervos. Creo que puede ser entonces interesante analizar someramente qué es lo que la computación cuántica nos puede ofrecer, ya que se trata de un campo cuyas posibilidades en el ámbito de la computación están casi tan sobredimensionadas como las de Guti en el ámbito del mediocampo del Real Madrid. Para ponernos en situación, es necesario empezar por algunos preliminares que nos ayuden entender el nicho en el que los computadores cuánticos pueden ser útiles.
En primer lugar, vamos a comenzar por definir un marco computacional (puede hacerse una discusión en términos más abstractos, pero es más simple centrar las cosas en un modelo concreto). Hay diferentes posibilidades, pero vamos a ser clásicos e inclinarnos por las máquinas de Turing (MT). Una MT es un modelo formal del concepto de algoritmo que podemos imaginar como un dispositivo capaz de leer/escribir símbolos de/en una cinta, y de desplazarse por la misma (o hacer que la cinta se desplace, que tanto da una cosa como la otra). La cinta la podemos imaginar como de longitud ilimitada, y dividida en casillas, en cada una de las cuales puede haber un símbolo. La MT se halla en todo momento en un cierto estado interno (de entre un cierto conjunto de estados posibles) y dispone de una función de transición interna que le dice qué debe escribir, cómo debe moverse, y cómo debe cambiar el estado interno en función del estado actual y de lo que esté leyendo en cada momento de la cinta. La definición de la MT es completa si indicamos el alfabeto A que contiene a todos los símbolos que se pueden leer/escribir, el conjunto de estados posibles Q, el estado inicial q0, y la función de transición d. El funcionamiento de la MT termina en el momento que se alcanza un cierto estado de parada. Los contenidos iniciales de la cinta corresponden a la entrada del algoritmo, y los contenidos finales a su salida.
Esta definición de MT es suficiente para abarcar cualquier algoritmo (de hecho un algoritmo se define como una MT). En particular, un algoritmo cuántico es simulable en una MT, por lo que un supuesto ordenador cuántico no nos va a permitir nada que no podamos hacer con nuestro PC, Mac, o -ya puestos- ZX-81. Por supuesto, es posible que -aunque no pueda hacer nada nuevo- un algoritmo cuántico sí pueda ser más eficiente que un algoritmo clásico. Nos adentramos entonces en los vericuetos de la complejidad computacional, y necesitamos definir algunos conceptos adicionales, empezando por el de MT no determinista (nMT).
Una nMT es una MT en la que la función de transición puede estar sobre- o sub-especificada, es decir, se puede indicar más de un comportamiento en una determinada situación o ninguno en absoluto. Lógicamente, lo primero es más interesante. Podemos imaginarnos que cuando se produce una de estas situaciones en la que la función de transición indica más de una posibilidad, la nMT se ramifica, produciendo copias de la máquina que exploran estas posibilidades en paralelo. Contrariamente a lo que una primera impresión pudiera hacer pensar, este paralelismo masivo no nos permite nuevamente hacer nada que no pueda hacer una MT determinista, pero sí que permite realizar una tarea mucho más deprisa (exponencialmente más rápido). Podemos emplear esta posibilidad para realizar una clasificación de los problemas computacionales de decisión (problemas para los que tenemos que encontrar una respuesta SÍ o NO) en dos clases: P y NP. La primera comprende aquellos problemas para los que una MT determinista puede encontrar la respuesta en un número polinomial (en el tamaño del problema) de pasos, es decir, en algo del orden de nc, donde n es dicho tamaño y c es una constante que no depende de n. Análogamente, NP es el conjunto de problemas de decisión para los que una nMT puede encontrar la respuesta en un número polinomial de pasos (es decir, basta con que una de las ramas encuentre la solución en tiempo polinomial). Hay numerosos problemas prácticos de optimización cuya versión decisional (e.g., la que tiene por respuesta SÍ o NO) está en la clase NP. Por ejemplo, el problema del viajante de comercio (TSP): dado un conjunto de ciudades, encontrar una ruta de longitud mínima que pase por todas las ciudades, sin repetir ninguna, y vuelva a la ciudad de partida. La versión decisional de este problema sería plantear: ¿existe un camino de las características requeridas cuya longitud sea inferior a K?
En relación al ejemplo anterior, no consta que el TSP (entre otros muchos problemas) esté en P, lo que hace plantearse la cuestión de si es que no se conoce aún un algoritmo polinomial para él, o es que realmente el problema es intrínsecamente no-polinomial. En otras palabras, dado que P está claramente contenida en NP (porque toda MT determinista es una nMT también), se ignora si la inclusión es estricta o no, esto es, si hay problemas en NP que no estén en P. Se cree que sí los hay, pero no hay demostración en un sentido o en otro (hay un premio de 1,000,000$ para quien lo consiga demostrar). Lo que sí se sabe es que o bien P = NP (en cuyo caso la necesidad de computadores cuánticos pasa a ser muy cuestionable), o bien hay tres tipos de problemas en NP: los problemas en P, y otros dos tipos que veremos a continuación, una vez se defina el concepto de completitud para una clase.
Se dice que un problema X es completo para la clase C, si X es un problema que pertenece a la clase C, y cualquier otro problema en C es reducible a X. A grandes rasgos, esto último quiere decir que dada una instancia de un problema Y perteneciente a C, podemos usar un cierto procedimiento R para convertirlo en una instancia del problema X. Si esto es así, X representa el mayor grado de dificultad dentro de la clase (cualquier otro problema es a lo sumo tan complejo de resolver como X). En el caso particular de NP requerimos que la transformación anterior se haga con un algoritmo polinomial. El problema de la satisfacibilidad es un problema completo para NP. Hay otros muchos que pueden consultarse aquí.
Bajo la suposición de que P no es igual a NP, los problemas NP-completos están lógicamente fuera de P, pero también hay problemas que ni están en P, ni son NP-completos. No consta que un algoritmo cuántico, gracias a la aceleración que el uso de estados superpuestos permita, pueda resolver en tiempo polinomial un problema NP-completo, y de hecho se piensa que no podrá. La utilidad de los computadores cuánticos será entonces para problemas no NP-completos como la factorización de enteros (una utilidad mucho más reducida de lo que los optimistas de D-Wave afirman). En otro artículo ya trataremos esto con más detalle, y lo cuantificaremos más formalmente. Vamos a esperar mientras tanto a ver en qué queda la presentación de Orión.
