La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Posts Tagged ‘Computación Cuántica’

Nuevos modelos del problema del castor afanoso pueden conducir a un nuevo paradigma de computación

Posted by Carlos en diciembre 28, 2009

Ya hemos hablado con anterioridad acerca del castor afanoso y de su equivalencia con el problema de la parada que -recordemos- es el ejemplo paradigmático de problema no computable y sobre el que se asienta toda una jerarquía de clases de problemas basadas en oráculos para la resolución del mismo. El problema del castor afanoso enraiza pues de forma esencial en el modelo de computación de Turing, por lo que resulta fundamental avanzar en su compresión y resolución. Precisamente en este sentido hay que enmarcar un reciente trabajo de H.R. Peinetti y colaboradores -de la Universidad Nacional de La Pampa, la Colorado State University y el U.S. Geological Survey- titulado

y publicado en Ecological Modelling. En este trabajo Peinetti et al. presentan un modelo de las complejas interacciones del castor con su entorno y con su comunidad. Los resultados de simulaciones a largo plazo del modelo arrojan revelaciones de gran interés en relación con el comportamiento asintótico del castor afanoso, lo que a su vez constituye una información de enorme valor con vistas a la construcción de oráculos para el mismo. De llegar a sustanciarse estos oráculos estaríamos en puertas de un salto trascendente en los modelos de cómputo vigentes, lo que sugiere que quizás otras líneas actuales de investigación en computación cuántica o computación con ADN deberían irse paulatinamente redireccionando hacia el área del artículo reseñado.

Actualización: Como el lector habrá advertido con toda seguridad, este artículo es sólo una broma, cumpliendo con la tradición del 28 de diciembre. Por más que la vida social del castor pueda ser apasionante, los investigadores en computación cuántica pueden estar tranquilos: no es previsible que tengan que dedicarse a estudiar estados de superposición de estos simpáticos roedores.

Anuncios

Posted in Calculabilidad, Tradiciones | Etiquetado: , , | 1 Comment »

Evolución de Algoritmos Cuánticos

Posted by Carlos en julio 10, 2009

Una de sesiones más interesantes de lo que llevamos de conferencia ha sido la referida a evolución de algoritmos cuánticos. El ponente de la misma ha sido Lee Spector (uno de cuyos trabajos sobre inteligencia artificial comentamos aquí in ilo tempore), y durante aproximadamente 2 horas nos desgranó un tutorial sobre algoritmos cuánticos que desembocó en la interrelación de los mismos con la programación genética. Antes de llegar a este último punto, comenzamos recordando uno de los experimentos más clásicos (y no por ello menos sorprendente) de la mecánica cuántica, esto es, el interferómetro de Mach-Zehnder.

Interferómetro de MAch-Zender (credit: Danielmader)

Interferómetro de Mach-Zender (credit: Danielmader)

En este experimento se emplean dos espejos semi-reflectantes (abajo a la izquierda, y arriba a la derecha) que con una probabilidad del 50% dejan pasar un fotón incidente o lo reflejan en dirección perpendicular. La intuición clásica indica que dado que hay dos bifurcaciones, cada una de las cuales es equiprobable, un fotón tendría un 50% de probabilidades de llegar al segundo espejo semi-reflectante por el camino superior y un 50% de hacerlo por el camino inferior. Una vez en el mismo, tendría un 50% de probabilidades de ser reflejado y un 50% de atravesarlo. Sumando el 25% de probabilidad de que el fotón llegue por el camino superior y se refleje y el 25% de que llegue por el camino inferior y atraviese el espejo, llegamos a que un 50% de los fotones llegarían al detector 2. Sin embargo, esta intuición no es correcta ya que la realidad indica que el 100% de los fotones llegan al detector 1. Esto es debido a que al ser reflejado un fotón se produce un cambio de fase de media longitud de onda en el mismo. De resultas del mismo se produce una interferencia destructiva al superponer los estados que desembocan en el detector 2, por lo que ningún fotón puede llegar al mismo. La única posibilidad factible son los caminos que llevan al detector 1.

Este experimento admite una vuelta de tuerca muy interesante: imaginemos que tenemos bombas cuya espoleta se activa en el momento que detectan un fotón. Dada una de estas bombas, podemos saber si funciona correctamente (o por el contrario es defectuosa) simplemente exponiéndola a la luz, aunque obviamente esto conduciría a la pérdida de todas las bombas plenamente funcionales. Un procedimiento más astuto hace uso del montaje anterior, y da lugar a lo que se conoce como comprobador de bombas de Elitzur-Vaidman. Básicamente, sustituimos el reflector inferior derecho por la bomba. Ahora, si la bomba es defectuosa se comportará como un espejo y el sistema será equivalente al anterior, es decir, todos los fotones llegarán al detector 1. Sin embargo, si la bomba funciona correctamente el fotón no puede seguir en estado superpuesto camino superior/camino inferior, ya que la explosión de la bomba supone un proceso de medida, y la función de onda debe colapsar a uno de los dos estados. Por lo tanto, puede pasar que la bomba explote (si el estado al que el fotón colapsa es el camino inferior), o que no lo haga (si el estado es el camino superior). En este segundo caso, al llegar al segundo espejo semi-reflectante no se produce interferencia destructiva, y hay un 50%-50% de posibilidades de que llegue a un detector o al otro. Si llega al detector 2 estamos seguros de que la bomba es buena. En otro caso hay que repetir el experimento hasta que eventualmente la bomba explote, el fotón llegue al detector 2, o tengamos una certeza razonable de que la probabilidad de que la bomba sea defectuosa es despreciable.

Dándole otra vuelta más de tuerca al sistema, podemos sustituir la bomba por un computador que ejecutará un algoritmo y producirá o no un fotón de salida. Nuevamente, inspeccionando los detectores podemos determinar cuál sería la salida del algoritmo, sin necesariamente ejecutarlo. Este montaje fue propuesto por Onus Hosten et al. en un artículo titulado

publicado en Nature (véase también este comunicado de prensa). Toda esta discusión constituyó un punto de entrada para ilustrar el concepto de superposición de estados y -tras una breve disgresión sobre la mente humana, la consciencia y su computabilidad- entrar en la noción de qubits y puertas lógicas cuánticas.Estas últimas las vimos a través de su notación matricial. Por ejemplo, si tenemos un qubit con valor \alpha|0\rangle + \beta|1\rangle, la siguiente matriz representa un NOT:

\left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)

ya que al multiplicarla por el vector columna (\alpha,\beta) obtenemos el vector columna (\beta,\alpha) (puede verse por ejemplo que en el caso clásico en el que \alpha=1, \beta=0 o viceversa se obtiene el resultado complementario). Más interesante es la puerta lógica SNR (square root of NOT):

1/\sqrt{2}\left(\begin{array}{cc} 1 & -1 \\ 1 & 1 \end{array} \right)

Al aplicarla una vez a un qubit que es 1 ó 0 se obtiene una suerte de aleatorización, ya que se pasa a un estado de superposición equiprobable entre ambos valores. Al aplicarla por segunda vez, se obtiene sin embargo el complemento:

\left(\begin{array}{c} 1 \\ 0 \end{array} \right) \Rightarrow \left(\begin{array}{c} 1/\sqrt{2} \\ 1/\sqrt{2} \end{array} \right) \Rightarrow \left(\begin{array}{c} 0 \\ 1 \end{array} \right).

Una de las posibilidades para la aplicación de técnicas de programación genética es tratar de buscar puertas cuánticas ad hoc, mediante la evolución de las matriz que la define. Yendo más allá, se puede pensar en programación genética para combinar puertas lógicas preexistentes y obtener un circuito que desarrolla un cierto propósito buscado. Un ejemplo de esto nos lo dio con un trabajo (que hay que decir ya tiene unos años) en el que se consiguió una solución nueva y eficiente a un problema simple (pero por algo hay que empezar). El trabajo en cuestión es

del propio Lee Spector et al., y que apareció en las actas del CEC 1999. Otras líneas de desarrollo apuntan a la construcción de algoritmos híbridos que combinan elementos clásicos con elementos cuánticos. Un área apasionante sin duda.

Posted in Computación Evolutiva, Física | Etiquetado: , , | Comentarios desactivados en Evolución de Algoritmos Cuánticos

Computación cuántica más allá del Arco Iris

Posted by Carlos en octubre 14, 2008

La computación cuántica sigue siendo uno de los santos griales de la física y la informática, por más que algunas veces sus posibilidades se hayan sobredimensionado. Un computador cuántico operativo tendría grandes aplicaciones en campos particulares, como pueden ser la factorización de enteros o la simulación de estados cuánticos. Sin embargo, la construcción de un dispositivo de estas características se viene topando de bruces con limitaciones técnicas a la hora de vencer la decoherencia, y de ser escalable. Los esfuerzos por vencer estas limitaciones se vienen sucediendo, y quizás una de las líneas de ataque más prometedoras la constituye la computación cuántica unidireccional.

A diferencia de la computación cuántica “clásica” -que podemos imaginar como una extensión de los circuitos lógicos tradicionales a circuitos cuánticos que manipulan de manera reversible bits entrelazados- la computación cuántica unidireccional se basa en la realización de medidas -un proceso inherentemente irreversible- sobre un sistema cuántico adecuadamente preparado inicialmente, y que será destruido en el proceso. Así, mientras en el modelo clásico de computación cuántica la medida se realiza sólo sobre el estado final del sistema tras atravesar las puertas cuánticas, en este modelo se realizan de manera continua. Más aún, las medidas que se hagan en un momento determinado dependerán en general del resultado de las medidas anteriores. La gran ventaja de esto es que la dificultad tecnológica se concentra fundamentalmente en la construcción del estado inicial -el denominado (a falta de mejor traducción) estado racimo, que puede imaginarse como una malla muy compleja de estados entrelazados- ya que la realización de las medidas posteriores admite implementaciones prácticas aceptables.

En este contexto es en el que Nicolas C. Menicucci (de Princeton y la Universidad de Queensland), Steven T. Flammia (de la Universidad de Waterloo), y Olivier Pfister (de la Universidad de Virginia), han sugerido un mecanismo que puede suponer un gran paso adelante en la construcción de dichos estados racimo. Dicho mecanismo se describe en un trabajo titulado

publicado hace un par de semanas en Physics Review Letters. Parte de la idea de Menicucci et al. se basa en el empleo de fotones entrelazados. Dicho empleo no es nuevo en sí, ya que debido a su mayor resistencia a la decoherencia se han postulado como uno de los mejores candidatos a portadores de información. El problema de esto es que se requiere algún dispositivo óptico no lineal para que se produzca la interacción entre fotones en las puertas cuánticas, lo que es tecnológicamente complejo y costoso. En el sistema de Menicucci et al. se sugiere sin embargo un procedimiento más asequible, formado por una cavidad óptica en cuyos extremos hay espejos, y en cuyo interior hay un cristal capaz de dividir o unir pares de fotones de frecuencias específicas. Dichos pares de fotones quedarán entrelazados, y ahí reside el quid del asunto: mediante el empleo de 15 láseres de diferentes frecuencias se podrá construir una macromalla toroidal de estados entrelazados, un arco iris de información, que constituirá el estado inicial de la computación.

Menicucci et al. - Phys. Res. Lett. 101, 130501 (2008)

Menicucci et al. - Phys. Res. Lett. 101, 130501 (2008)

En su trabajo, Menicucci et al. muestran que una malla de este tipo es universal, y por lo tanto que es susceptible de ser la base para la realización de cualquier computación. ¿Será ésta la llave que permita abrir el cofre del tesoro cuántico? Habrá que esperar para ver si la escalabilidad del sistema es en la práctica tan parsimoniosa como el análisis teórico sugiere, pero nada impide mientras tanto ser optimistas.

Posted in Computadores, Física, Tecnología | Etiquetado: | 1 Comment »

Lo que la computación cuántica (no) puede hacer por nosotros

Posted by Carlos en febrero 13, 2007

Computador cuánticoHoy es el día en el que los muchachos de D-Wave planean hacer la presentación de su sistema cuántico Orión, tal como Alvy nos acaba de recordar en Microsiervos. Creo que puede ser entonces interesante analizar someramente qué es lo que la computación cuántica nos puede ofrecer, ya que se trata de un campo cuyas posibilidades en el ámbito de la computación están casi tan sobredimensionadas como las de Guti en el ámbito del mediocampo del Real Madrid. Para ponernos en situación, es necesario empezar por algunos preliminares que nos ayuden entender el nicho en el que los computadores cuánticos pueden ser útiles.

En primer lugar, vamos a comenzar por definir un marco computacional (puede hacerse una discusión en términos más abstractos, pero es más simple centrar las cosas en un modelo concreto). Hay diferentes posibilidades, pero vamos a ser clásicos e inclinarnos por las máquinas de Turing (MT). Una MT es un modelo formal del concepto de algoritmo que podemos imaginar como un dispositivo capaz de leer/escribir símbolos de/en una cinta, y de desplazarse por la misma (o hacer que la cinta se desplace, que tanto da una cosa como la otra). La cinta la podemos imaginar como de longitud ilimitada, y dividida en casillas, en cada una de las cuales puede haber un símbolo. La MT se halla en todo momento en un cierto estado interno (de entre un cierto conjunto de estados posibles) y dispone de una función de transición interna que le dice qué debe escribir, cómo debe moverse, y cómo debe cambiar el estado interno en función del estado actual y de lo que esté leyendo en cada momento de la cinta. La definición de la MT es completa si indicamos el alfabeto A que contiene a todos los símbolos que se pueden leer/escribir, el conjunto de estados posibles Q, el estado inicial q0, y la función de transición d. El funcionamiento de la MT termina en el momento que se alcanza un cierto estado de parada. Los contenidos iniciales de la cinta corresponden a la entrada del algoritmo, y los contenidos finales a su salida.

Esta definición de MT es suficiente para abarcar cualquier algoritmo (de hecho un algoritmo se define como una MT). En particular, un algoritmo cuántico es simulable en una MT, por lo que un supuesto ordenador cuántico no nos va a permitir nada que no podamos hacer con nuestro PC, Mac, o -ya puestos- ZX-81. Por supuesto, es posible que -aunque no pueda hacer nada nuevo- un algoritmo cuántico sí pueda ser más eficiente que un algoritmo clásico. Nos adentramos entonces en los vericuetos de la complejidad computacional, y necesitamos definir algunos conceptos adicionales, empezando por el de MT no determinista (nMT).

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.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Calculabilidad, Complejidad, Matemáticas | Etiquetado: | 31 Comments »