¿Hacia el ordenador cuantico?

Desde que la Sociedad Matemática de Londres publicara el trabajo de Alan Turing titulado On Computable numbers, with an application to theEntscheidungsproblem en el año 1936, el mundo ha cambiado de forma radical. En ese trabajo, Turing definía una máquina compuestade una cinta infinita y un cabezal lector/escritor que la recorría leyendo los valores contenidos en ella de manera que el estado dela máquina y el valor leído daban como resultado el nuevo estado, un nuevo valor a escribir en la cinta y ladirección de movimiento del cabezal. Esta sencilla máquina no sólo daba respuesta a la pregunta suscitada por David Hilbert sobre si las matemáticas son decidibles, sino que ponía las bases para la construcción de una máquinareal que acabaría originando una revolución tecnológica sin precedentes: el computador digital.

La máquina determinista

Decimos que una máquina es determinista cuando para cada par valor-estado existe sólo una posibilidad de ejecución. Así ocurre en la lógica binaria, en que ladecisión será uno de los dos estados posibles. Un ordenador actual es, en este aspecto, una máquina de Turing determinista y, por tanto, sigue un sólo camino computacional. Una máquina de Turing determinista permite abordar la mayoría delos problemas, pero algunos resultan intratables en un tiempo razonable siguiendo un sólo camino computacional. De esta manera, podemos afirmar que la actual computación tiene un límite importante en el tiempo que necesita para resolver algunos problemas. ¿De qué nos serviría intentar calcular un problema cuyo resultado obtendríamos dentro de quinientos años? Seguramente, el ordenador noduraría tanto.

La máquina indeterminista.

En el caso en que un par valor-estado tenga más de una posibilidad de ejecución (es decir, que la decisión pueda tomar más de un camino computacional) nos encontramos ante una máquina de Turing indeterminista. Esto convierte el camino computacional en un árbol computacional, y la solución al problema estaría en alguna de las ramas del árbol. Un máquina de este tipo podría resolver un problema que actualmente se resolvería en tiempo exponencial en un tiempo polinómico. Dicho de otra manera, podría convertir problemas intratables en problemas tratables. Sin embargo, no disponemos de ordenadores no deterministas porque la tecnología actual está basada en la física de dos estados que manipula los valores positivo y negativo de los electrones. Así, la unidad de información informática, el bit, puede tomar valor 0 ó 1.

Los límites de la integración

Podría pensarse que llegará un momento en que, con la rápida evolución de la tecnología, la integración de circuitos alcanzará niveles tales de miniatuarización y, por tanto, de velocidad de cómputo, que los problemas actualmente intratables se convertirán en tratables, pero resulta que estamos ya cerca de alcanzar un límitefísico absoluto, el de la escana nanométrica, en el cual se produciría un efecto túnel al permitir a los electrones, que por su cualidad cuántica se comportan como ondas, escapar a los canales en los que deberían estar restringidos y los chips dejarían defuncionar bien.

Física cuántica: el tercer estado

La mecánica cuántica es una rama de la física que explica el comportamiento de la materia y de la energía pero que, en el mundo subatómico, sus predicciones divergen de las de la física tradicional de forma radical. Las partículas subatómicas generan un campo magnético al girar sobre su propio eje, determinado por sumomento angular, denominado espin. El espin tiene un valor fijo para cada tipo departícula porque siempre rotan ala misma velocidad. EI valor del espin toma signo positivo o negativo según la dirección en la que se mide el campo, sin embargo, por un efecto cuántico el espin puede tener los dos signos a la vez en lo que se ha llamado superposición coherente. De esta manera, el espín de un electrón podríatener tres estados diferentes.

El computador cuántico

En 1981, Paul Benioff hizo pública su teoría para aprovechar en computación la característica cuántica de los tres estados que proporciona el espín de una partícula subatómica. En ella, el bit tradicional se sustituye por el qubit, que además de losestados 0 y 1 puede tener también el estado 2. Un registro de tres bits puede tomar un valor entre ocho posibles (2^3), pero un vector de tres qubits puede tener ocho valores distintos a la vez gracias a la superposición cuántica, lo que permitirían ocho operaciones paralelas. Esto supondría pasar de la máquina de Turing determinista ala máquina de Turing indeterminista, por lo que se podrían tratar problemas que hoy en día resultan intratables al calcular no en un sólo camino computacional, sino en un árbol computacional. Para la tecnología actual, el horizonte del ordenador cuántico aún está lejano por las dificultades que entraña Controlar de forma efectiva las características cuánticasde las partículas subatómicas. Por ejemplo, existe un tiempo de decoherencia por elcual cualquier operación realizada en un tiempo mayor haría imposible revertir el algoritmo o, lo que es lo mismo, deshacer el cálculo, con lo que se produciría una incoherencia. Cada vez hay más equipos de investigadores trabajando en el campo de la computación cuántica y, aunque se presume aún lejano el día en que se dispongade un verdadero ordenador cuántico funcional, poco a poco van apareciendo trabajos que avanzan en ese sentido. Un hito importante sucedió cuando IBM pudofactorizar el número 15 en 3*5 mediante computación cuántica, algo que parece trivial pero que supone un salto importante en este campo. En febrero de 2007, la empresa canadiense D—WAVE presentó su primer ordenador cuántico de 16 Qbitsque, aunque muy discutido por la comunidad internacional, puede ser un buen ejemplo de lo que está por llegar, pero el verdadero trabajo está en el desarrollo decomponentes específicos como registros, buses o memorias y en ello se trabaja enmuchos laboratorios de las principales universidades y de los más potentesfabricantes de ordenadores.

¿Un futuro distinto?

El desarrollo de máquinas deterministas nos han situado en una rampa de evolución tecnológica que ni los más osados podían imaginar y que ha acabado cambiandolos modelos sociales, económicos, culturales, etc. ¿Puede alguien imaginar haciadónde nos llevaría el desarrollo de máquinas indeterministas gracias a lacomputación cuántica? Seguramente, no, aunque ya comienzan a aflorar algunos desus problemas. Por ejemplo, todos los mecanismos de encriptación actuales sevendrían abajo y las comunicaciones dejarían de ser seguras, aunque quizás no haga falta esperar porque la mayoría de algoritmos actuales ya están seriamenteamenazados, como el SHA-1 que utiliza nuestro nuevo y flamante e-dni bajo lamayoría de los sistemas operativos. De esta manera, la computación cuántica tendrá que llegar forzosamente de la mano de soluciones para que no se venga abajo todoaquello basado en computación tradicional y algunos comienzan a estarpreocupados. Pero, sin duda, si algún día llega supondrá una nueva e imprevisiblerevolución tecnológica.

Enric Coll PedrónDelegación

Especial de llles Balears

Problema del viajante de comercio

El problema del viajante de comercio es un clásico representante del grupo deproblemas NP-completos, que son aquellos imposibles de resolver en tiempo polinomial cuando la entrada alcanza un cierto tamaño. El planteamiento del problema se basa en encontrar la ruta más corta que enlace varias ciudadespasando sólo una vez por cada una de ellas. Como para N ciudades existen N! rutas distintas, para tan solo 12 ciudades tenemos casi 480 millones de rutas posibles. Las soluciones mediante computación actual sólo son aproximaciones porque el tiempo de cálculo se convierte rápidamente en exponencial. Para una veintena deciudades se podrían tardar decenas de miles de años con un ordenador personal.