nihil alienum

dándole vueltas a la computación cuántica

dandan | 16 Julio, 2008 00:14 | Share and Enjoy:

Ayer Rez me evió unos links sobre los sistemas Turing Completo (aquellos que tiene un poder computacional equivalente a la máquina universal de Turing) y la Tesis de Church-Turing. La tesis de Church-Turing fuerte supone que el universo es computable, y computable en este caso quiere decir (tal como lo entiendo) que podría responder a una secuencia determinada (y determinista) de funciones:

"La tesis de Church-Turing tiene además profundas implicaciones. Cuando la tesis es aplicada a la física tiene diversos significados: que el universo es una máquina de Turing y por lo tanto no es posible construir físicamente una máquina con mayor poder computacional o que compute funciones no recursivas (la capacidad de cómputo que puede contener el universo está acoplado al tipo de universo en el que vivimos). A esto se le ha llamado tesis de Church-Turing fuerte. Otra posible interpretación es que el universo no es una máquina de Turing, es decir, las leyes del universo no son computables pero esto no afecta la posibilidad de crear una máquina más poderosa que una máquina de Turing (universo desacoplado al poder computacional de los dispositivos que contiene). Otra posibilidad es que el universo sea una hipercomputadora y entonces sea posible la construcción de máquinas más poderosas que las máquinas de Turing usando como entrada los resultados de dicha súper computadora: el universo o la naturaleza. Para ello posiblemente bastaría con que el universo fuera continuo e hiciera uso de esa continuidad (otra pregunta es qué tan densa es su continuidad)" (wikipedia dixit).

El tema de si el universo es computable me llevó a pensar en Laughlin, en los procesos de organización como paso entre la física cuántica y la newtoniana, y en su desconfianza sobre la capacidad de la computación cuántica:

"Así, con el entusiasmo por la computación cuántica se pasa por alto un factor clave: la base física de la fiabilidad computacional es la newtonianidad emergente. Podemos pensar en una computación que no se valga de esos principios, así como probar por la fuerza que la ruptura de la simetría existe, pero lo más probable es que sea imposible eliminar los errores computacionales, porque la base física es inexistente".

No estoy seguro de que las dudas de Laughlin sean insalvables, pero el tema me planteó una cuestión interesante (al nivel muy amateur en que me muevo en esto): ¿cómo puede ser posible computar fenómenos organizativos o emergentes? Le contesté a Rez lo siguiente:

"una línea que me interesa: ¿son la complejidad, o los fenómenos de emergencia, computables?, es decir, ¿se puede rastrear y formalizar con un algoritmo su rango de aparición? Esto supondría un algoritmo que es capaz de abarcar un rango más o menos extenso de posibilidades de las cuales solo una encajaría con la manera en que los dados acaban cayendo (como los múltiples universos de la teoría de las cuerdas, pero solo vivimos en éste). La ventaja es que cuando hiciera bingo podría encajar lo "accidental" en una jerarquía".

Bueno, pues hoy he acabado de leer un estupendo artículo de Markus Aspelmeyer y Anton Zeilinger, "A quantum renaissance", en donde entre muchas otras cosas he encontrado este párrafo:

In this scheme, called "one-way" quantum computing, a computation is
performed by measuring the individual particles of the entangled cluster
state in a specific sequence that is defined by the particular
calculation to be performed. The individual particles that have been
measured are no longer entangled with the other particles and are
therefore not available for further computation. But those that remain
within the cluster state after each measurement end up in a specific
state depending on which measurement was performed. As the measurement
outcome of any individual entangled particle is completely random,
different states result for the remaining particles after each
measurement. But only in one specific case is the remaining state the
correct one. Raussendorf and Briegel's key idea was to eliminate that
randomness by making the specific sequence of measurements depend on the
earlier results. The whole scheme therefore represents a deterministic
quantum computer, in which the remaining particles at the end of all
measurements carry the result of the computation.

El tema es un poco denso (y no estoy seguro de si lo acabo de entender del todo), pero cuando he leido "But only in one specific case is the remaining state the correct one" me ha hecho diana en lo que le comentaba ayer a Rez, computar de una manera determinista la aleatoriedad de las respuestas cuánticas, en este caso creando una jerarquía en la secuencia de cálculo a partir de resultados anteriores. Tal como lo entiendo, en el artículo no se refieren a algoritmos, sino a la fiabilidad de las señales que cruzan las puertas lógicas, pero el problema es similar (creo). Puede ser una manera de despejar las dudas de Laughlin. Fin.