Impulsados por tecnologías de inteligencia artificial, los ordenadores actuales pueden hacer muchas cosas, pero todavía tienen sus límites, afirma un informático.
La computación cuántica está llamada a llevar la computación más allá de los algoritmos de una máquina de Turing.
Si tiene éxito, cambiará el panorama de la ciberseguridad, afirma el profesor.
Gracias a las tecnologías de inteligencia artificial, los ordenadores actuales pueden mantener conversaciones convincentes con personas, componer canciones, pintar cuadros, jugar al ajedrez y al go, y diagnosticar enfermedades, por citar solo algunos ejemplos de su capacidad tecnológica.
Estos logros podrían interpretarse como una indicación de que la computación no tiene límites. Para comprobar si esto es así, es importante entender qué hace potente a un ordenador.
La potencia de un ordenador tiene dos aspectos: el número de operaciones que su hardware puede ejecutar por segundo y la eficiencia de los algoritmos que ejecuta. La velocidad del hardware está limitada por las leyes de la física. Los algoritmos –básicamente conjuntos de instrucciones – son escritos por humanos y traducidos a una secuencia de operaciones que el hardware del ordenador puede ejecutar. Incluso si la velocidad de un ordenador pudiera alcanzar el límite físico, persisten obstáculos computacionales debido a los límites de los algoritmos.
Entre estos obstáculos se encuentran problemas que son imposibles de resolver para los ordenadores y problemas que son teóricamente resolubles pero que, en la práctica, están fuera de las capacidades incluso de las versiones más potentes de los ordenadores actuales que puedan imaginarse. Los matemáticos y los informáticos intentan determinar si un problema es resoluble probándolo en una máquina imaginaria.
Una máquina de computación imaginaria
La noción moderna de algoritmo, conocida como máquina de Turing, fue formulada en 1936 por el matemático británico Alan Turing. Se trata de un dispositivo imaginario que imita cómo se realizan los cálculos aritméticos con lápiz y papel. La máquina de Turing es la plantilla en la que se basan todos los ordenadores actuales.
Para acomodar cálculos que, si se hicieran manualmente, necesitarían más papel, se asume que el suministro de papel imaginario en una máquina de Turing es ilimitado. Equivale a una cinta imaginaria sin límites, o “cinta”, formada por casillas, cada una de las cuales está en blanco o contiene un símbolo.
La máquina se rige por un conjunto finito de reglas y comienza con una secuencia inicial de símbolos en la cinta. Las operaciones que puede realizar la máquina son desplazarse a una casilla contigua, borrar un símbolo y escribir un símbolo en una casilla en blanco. La máquina calcula mediante la ejecución de una secuencia de estas operaciones. Cuando la máquina termina, o “se detiene”, los símbolos que quedan en la cinta constituyen la salida o el resultado.
La computación suele tratar de decisiones con respuestas de sí o no. Por analogía, una prueba médica (tipo de problema) comprueba si la muestra de un paciente (una instancia del problema) presenta un determinado indicador de enfermedad (respuesta sí o no). La instancia, representada en una máquina de Turing en forma digital, es la secuencia inicial de símbolos.
Un problema se considera “resoluble” si puede diseñarse una máquina de Turing que se detenga para cada instancia, sea positiva o negativa, y que determine correctamente qué respuesta produce la instancia.
No todos los problemas pueden resolverse
Muchos problemas son resolubles mediante una máquina de Turing y, por tanto, pueden resolverse en un ordenador, mientras que muchos otros no lo son. Por ejemplo, el problema del dominó, una variante del problema de embaldosado formulado en 1961 por el matemático estadounidense de origen chino Hao Wang, no es resoluble.
El objetivo consiste en utilizar un conjunto de fichas de dominó para cubrir por completo una cuadrícula y, siguiendo las reglas de la mayoría de los juegos de dominó, haciendo coincidir el número de puntos de los extremos de las fichas contiguas. Resulta que no existe ningún algoritmo que, partiendo de un conjunto de fichas de dominó, pueda determinar si dicho conjunto cubrirá completamente la cuadrícula o no.
Mantenerlo razonable
Varios problemas resolubles pueden resolverse mediante algoritmos que se detienen en un tiempo razonable. Estos “algoritmos de tiempo polinómico” son algoritmos eficientes, lo que significa que es práctico utilizar ordenadores para resolver casos concretos de ellos.
No se sabe que miles de otros problemas resolubles tengan algoritmos de tiempo polinómico, a pesar de los intensos esfuerzos en curso por encontrar dichos algoritmos. Entre ellos se encuentra el problema del viajante.
El problema del viajante plantea si un conjunto de puntos, algunos de ellos conectados directamente, denominado grafo, tiene un camino que parte de cualquier punto, pasa por todos los demás puntos exactamente una vez y regresa al punto de origen. Imaginemos que un vendedor quiere encontrar una ruta que pase por todas las viviendas de un barrio exactamente una vez y regrese al punto de partida.
Estos problemas, denominados NP-completos, fueron formulados de forma independiente y se demostró que existían a principios de los años setenta por dos informáticos, el estadounidense de origen canadiense Stephen Cook y el ucraniano-estadounidense Leonid Levin. Cook, cuyo trabajo fue el primero, recibió por esta labor el Premio Turing de 1982, el más importante en informática.
El coste de saberlo con exactitud
Los algoritmos más conocidos para los problemas NP-completos consisten esencialmente en buscar una solución entre todas las respuestas posibles. El problema del viajante en un grafo de unos cientos de puntos tardaría años en ejecutarse en un superordenador. Estos algoritmos son ineficientes, lo que significa que no existen atajos matemáticos.
Los algoritmos prácticos que abordan estos problemas en el mundo real solo pueden ofrecer aproximaciones, aunque las aproximaciones están mejorando. Determinar si existen algoritmos eficientes de tiempo polinómico que puedan resolver problemas NP-completos es uno de los siete problemas abiertos del milenio propuestos por el Instituto Clay de Matemáticas a comienzos del siglo XXI, cada uno con un premio de 1 millón de dólares estadounidenses.
Más allá de Turing
¿Podría existir una nueva forma de computación más allá del marco de Turing? En 1982, el físico estadounidense Richard Feynman, premio Nobel, propuso la idea de la computación basada en la mecánica cuántica.
En 1995, Peter Shor, matemático aplicado estadounidense, presentó un algoritmo cuántico para factorizar enteros en tiempo polinómico. Los matemáticos creen que esto no es resoluble mediante algoritmos de tiempo polinómico en el marco de Turing. Factorizar un entero significa encontrar un entero menor que él, mayor que 1, que pueda dividirlo. Por ejemplo, el entero 688.826.081 es divisible por un entero menor, 25.253, porque 688.826.081 = 25.253 x 27.277.
Un algoritmo importante denominado algoritmo RSA, ampliamente utilizado para proteger las comunicaciones en red, se basa en la dificultad computacional de factorizar enteros grandes. El resultado de Shor sugiere que la computación cuántica, en caso de hacerse realidad, cambiará el panorama de la ciberseguridad.
¿Puede construirse un ordenador cuántico completo para factorizar enteros y resolver otros problemas? Algunos científicos creen que sí. Varios grupos de científicos de todo el mundo trabajan para construir uno, y algunos ya han construido ordenadores cuánticos a pequeña escala.
No obstante, como ocurre con todas las tecnologías novedosas inventadas anteriormente, es casi seguro que surgirán problemas con la computación cuántica que impondrán nuevos límites.
