 |
| Alan Turing |
En una
entrevista en la Contra de la Vanguardia publicada el 27 de julio de 2019,
David Pérez García, investigador en física cuántica, dice esto: Sólo [estamos en] el principio de unas tecnologías que
aún hoy no sabemos hasta dónde llegarán. Tiene razón, porque el
futuro es difícilmente predecible, pero cuando se habla de computación cuántica
se tiende a pensar que estos ordenadores, si algún día son viables, nos
permitirán resolver problemas muy distintos de los que pueden abordar los
computadores tradicionales a los que estamos acostumbrados, y esto sí es algo
en que las matemáticas pueden ayudar a distinguir entre lo que se puede hacer,
y lo que es completamente imposible.
Aunque la
computación cuántica es un concepto bastante moderno, su fundamentación teórica
fue establecida por Alan Turing durante los años 30 del siglo XX. Es
interesante revisar lo que él demostró entonces, porque así podremos subsanar
algunas ideas demasiado optimistas que suelen esparcir los medios de
comunicación, a menudo impulsados por expertos que abordan la
cuestión desde puntos de vista muy diferentes al de Turing.
Alan Turing diseñó
un tipo especial de máquina de cómputo que, en su honor, se llama máquina de Turing determinista. Aunque no se suele construir con hardware, resulta fácil de simular con una computadora electrónica.
Esencialmente consta de una cinta infinita en la que se pueden grabar
símbolos, y de un cabezal que permite leerlos y
escribirlos. Los símbolos que contiene la cinta al principio del proceso forman
la entrada de la máquina, que estará en un estado escogido
entre varios posibles. Al leer un símbolo de la cinta, la máquina de Turing escribe
otro símbolo en la misma posición, cambia de estado, y desplaza (o no) el
cabezal para leer el símbolo situado en la casilla siguiente, o en la anterior,
o en la misma. La máquina es determinista, porque si está en un estado
determinado y lee un símbolo concreto de la cinta, su acción es siempre la
misma.
 |
| Máquina de Turing construida con Lego |
Cada máquina de
Turing determinista está diseñada para ejecutar un solo programa. Sin embargo,
Turing demostró que es posible diseñar una máquina especial (la máquina de Turing universal), que puede simular
el funcionamiento de cualquier otra máquina de Turing si se le proporcionan,
como datos de entrada, la definición de esta (su matriz de transición de
estados) y los datos de entrada de la máquina simulada. La máquina de Turing
universal tiene una capacidad de cálculo equivalente a la de nuestras
computadoras electrónicas tradicionales, a las que se adelantó en casi una
década. En puridad, es aun más potente, porque se supone que tiene memoria
infinita. Pero esta diferencia ha perdido importancia, teniendo en cuenta el
tamaño que alcanza la memoria de las computadoras modernas.
Por otra parte,
Turing diseñó otro tipo de máquina de cómputo, la máquina de Turing no determinista, que tiene la
particularidad de que, al leer un símbolo de la cinta, puede realizar varias
acciones diferentes (pasar a varios estados, escribir distintos caracteres y
moverse en diversas direcciones). Y no se trata de que elija una entre esas acciones
posibles, sino que realiza todas a la vez, en paralelo. Esta máquina proporciona
una buena aproximación de los computadores cuánticos de los que se habla hoy,
que en tiempos de Turing eran impredecibles.
Pues bien, Turing
no se limitó a definir esas dos máquinas, que representan los ordenadores
actuales y los cuánticos, sino que demostró un teorema según el cual
cualquier máquina de Turing no determinista puede simularse mediante una
determinista equivalente, que resuelve exactamente el mismo problema
(eso sí, mucho más despacio). Una demostración informal de este teorema puede
encontrarse en el apartado 2.3.1 del libro Teoría de Autómatas y Lenguajes
Formales (McGraw Hill 2007) que escribí junto con mi hijo Enrique y el
profesor Roberto Moriyón, para que sirviera de texto en la titulación de
Ingeniería Informática.
La consecuencia de
este teorema es evidente: los ordenadores cuánticos no podrán resolver
problemas nuevos, que hasta ahora no se había podido resolver. Simplemente es
posible que resuelvan con rapidez algunos problemas que ya podíamos resolver
con las máquinas tradicionales, aunque más despacio. Sí, de acuerdo, algunos de
esos problemas (que se llaman NP-completos)
tardan mucho en resolverse (a veces demasiado) con los ordenadores que
utilizamos corrientemente, y quizá podamos resolverlos en tiempo razonable con
los ordenadores cuánticos, pero está completamente excluido que con ellos
puedan resolverse problemas nuevos. Las matemáticas lo demuestran.
La Wikipedia inglesa expresa
esta idea de una forma clara y terminante:
Los problemas que son
indecidibles utilizando computadores clásicos siguen siendo indecidibles
utilizando computadores cuánticos.
Hilo Inteligencia natural y artificial: Anterior Siguiente
Manuel Alfonseca
Agradezco a Gonzalo
Génova, que me sugirió este artículo
Estoy completamente de acuerdo, la computación cuántica es simplemente un paradigma diferente al de la computación clásica, con el que se podrá resolver problemas de forma más rápida y eficiente.
ResponderEliminarOlvidaba, si a alguien le interesa este tema, aqui dejo el enlace a un articulo de revisión publicado por mi:
ResponderEliminarhttps://www.mdpi.com/2073-431X/5/4/24/htm
Interesante artículo, aunque me desvió algo del tema. Algunos parecen críticos con la inteligencia artificial entre ellos Elon Kusk. Aunque ya se ha tratado en otros artículos de Divulciencia parecen tener temor de que la inteligencia artificial suppere a la del ser humano, y acabemos como en Terminator, Matrix, o la saga Berserker de Fred Saberhagen PD. Iré leyendo los otros artículos, y contestándolos poco a poco mientras leo, y escribo críticas literarias :-).
ResponderEliminarMuchas gracias, Manuel, por recoger el guante y no olvidar este tema que surgió hace unos meses.
ResponderEliminar>> Y no se trata de que [la máquina de Turing no determinista] elija una entre esas acciones posibles, sino que realiza todas a la vez, en paralelo.
Lo que me descuadra un poco es que se la denomine "no determinista", que sugiere algún tipo de aleatoriedad o indeterminación. Pero no es eso lo que ocurre, sino que realiza, de modo determinista, varias acciones a la vez. Este "determinismo de la máquina no determinista" es confirmado por el teorema de equivalencia. Más bien habría que denominarla, entonces, "máquina de Turing concurrente", "multimáquina de Turing", o algo semejante.
>> La consecuencia de este teorema es evidente: los ordenadores cuánticos no podrán resolver problemas nuevos, que hasta ahora no se había podido resolver.
Bueno, con matices, ¿no? Porque antes has dicho que "Esta máquina proporciona una buena aproximación de los computadores cuánticos de los que se habla hoy". Luego, en la medida en que la aproximación deja de ser válida, queda abierta la posibilidad a que los ordenadores cuánticos resuelvan problemas no computables al modo tradicional.
Quede claro que no soy nada partidario del halo de misticismo con que los medios tratan ciertas noticias sobre ciencia y tecnología. Todo lo contrario, la labor del divulgador es desmitificar, o sea, poner en su lugar a la ciencia y la tecnología, y en este caso a la computación cuántica.
Volviendo a la duda que planteé originalmente, si un ordenador cuántico es, no solo aproximadamente, sino totalmente equivalente a una máquina de Turing no determinista, entonces no puede calcular o computar de forma diferente (salvo cuestiones de eficiencia), y por tanto la expresión "algoritmo cuántico" es equívoca, porque todo algoritmo cuántico es en realidad (equivalente a) un algoritmo tradicional, tal como se definen desde de Turing.
1. Es evidente que el nombre "máquina no determinista" puede ser susceptible de mejora, pero es el que se le dado desde el principio, así que no parece fácil cambiarlo. Por otra parte, lo que propones (máquina con aleatoriedad) tiene un nombre diferente: "máquina de Turing probabilística".
Eliminar2. Dije lo de "es una buena aproximación" para curarme en salud, porque Deutsch ha propuesto un nuevo tipo de máquina de Turing (la máquina de Turing cuántica) que en vez de bits tiene qubits en su memoria. Pero sospecho que esta máquina es equivalente a la máquina de Turing no determinista, en cuyo caso mi frase podría sustituirse por "es totalmente equivalente a". No soy consciente de que se haya demostrado la equivalencia, pero la frase de la Wikipedia inglesa que he citado parece indicar que sí lo ha sido.
Sigo dándole vueltas, gracias a que en estas dos últimas semanas he tenido que estudiar el tema.
Eliminar1. No me convence todavía el término "algoritmo cuántico". Lo que he visto son formas de conectar qubits (bits cuánticos) a través de puertas cuánticas (que son las análogas a las puertas lógicas en la electrónica digital clásica). Si tuviera que dar un nombre a esto, lo llamaría "circuito lógico cuántico", o más brevemente "circuito cuántico".
Ciertamente, un circuito lógico clásico implementa un determinado algoritmo, es decir, una transformación "mecánica" (basada en reglas lógicas) en la información que se le da como entrada. En ese sentido, la diferencia entre circuito lógico y algoritmo no es tajante. Aun así, me parece que un ingeniero informático tiene otra cosa en la cabeza cuando habla de algoritmo.
En resumen, lo acepto como término correcto, pero creo que esta explicación no sobra.
2. Un circuito (o algortimo) cuántico acepta información en forma de bits clásicos en su entrada (como un algoritmo convencional), y produce a la salida igualmente una serie de bits clásicos (el resultado de medir los qubits y colapsarlos).
No tengo claro todavía si el resultado es determinista, o si tiene carácter probabilista, o si es a veces una cosa y a veces otra.
En el primer caso estamos ante una máquina que transforma, siempre de la misma manera, una entrada en forma de bits en una salida en forma de bits, lo cual responde perfectamente a la definición de Máquina de Turing, y por tanto, sea cual sea su construcción interna, es una Máquina de Turing, y solo puede calcular lo que éstas pueden calcular, en el sentido en que lo explicabas en tu artículo.
En el segundo caso, tal vez se pueda decir que es una Máquina de Turing Probabilística. Mis conocimentos no llegan a tanto por el momento.
Tu análisis es correcto, con la única anotación de que el resultado del algoritmo (o circuito) cuántico siempre es determinista. En el algoritmo de Shor (por ejemplo) cuyo objetivo es dividir un número compuesto en sus factores primos (15=3*5) el propósito del algoritmo es manipular las probabilidades de las distintas posibilidades cuánticas con el fin de que una de ellas (la solución correcta buscada) pase al final a tener probabilidad 1, mientras todas las demás pasan a tener probabilidad cero. Así, cuando se provoca el colapso cuántico, no tenemos más remedio que obtener el resultado correcto deseado. En consecuencia, no se trata de una máquina de Turing probabilística, porque el resultado siempre es determinista, como en los ordenadores ordinarios.
Eliminar