El Sistema Cuántico Orión no está ni vivo ni muerto, sino todo lo contrario

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.