La Singularidad Desnuda

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

Archive for 31 julio 2009

La sombra de Pandora

Posted by Carlos en julio 31, 2009

Pandora es uno de los 52 satélites de Saturno con nombre propio, pero no es una más. Se trata de una masa de hielo oblonga de más de 100 km de longitud en su semieje mayor que pastorea junto con su compañero Prometeo el anillo F del viejo Cronos. Su órbita es caótica -precisamente de resultas de la interacción con Prometeo- y presenta una inclinación de unos 3 minutos de arco con respecto al ecuador del planeta. Por este motivo, su sombra incide oblicuamente sobre los anillos, oscureciendo fugazmente los principales pero obviando el anillo F, tal como se ve en la imagen inferior (Pandora es la pequeña esfera en la parte inferior de la fotografía).

PIA11543: Shadow Misses a Ring

NASA/JPL/Space Science Institute

Escenas como éstas son especiales, ya que sólo se producen durante unos meses antes y después del equinoccio saturnino, una vez cada 15 años terrestres.

Posted in Astronomía, Fotografía | Etiquetado: , , , , , , , | Comentarios desactivados

Resuelve problemas NP-completos mientras juegas

Posted by Carlos en julio 29, 2009

La clase NP -de la que ya hemos hablado en alguna ocasión- abarca aquellos problemas de decisión que pueden resolverse en tiempo polinómico no determinista, o lo que es lo mismo, aquellos problemas para los que es posible verificar en tiempo polinómico la validez de una solución dada. Esta clase ha sido tradicionalmente empleada como sucedáneo de la idea de intratabilidad computacional. No se trata de la mejor caracterización, ni siquiera de la más apropiada, puesto que admite mucha patología y en ocasiones tiene un impacto práctico limitado, pero eso será tema de algún futuro post. Sea como fuere, es común que allá donde nos enfrentemos a un problema NP-hard se emplee este hecho como justificación para el empleo de algún tipo de (meta)heurística.

Nuestra comprensión sobre cómo aplicar metaheurísticas para resolver problemas específicos ha avanzado enormemente en la última década. Una de las claves está en ser capaces de explotar conocimiento del problema durante el proceso de búsqueda. Técnicas tales como los algoritmos meméticos se basan fundamentalmente en esta idea. Evidentemente no se trata de algo trivial de conseguir, y aquí es donde es posible que la mente humana eche una mano y no en la ingeniería del proceso sino contribuyendo capacidad de búsqueda pura y dura. No se trata por supuesto de cálculo numérico ni de búsqueda sistemática, sino de explotar algunas de las cualidades que nuestros cerebros han ido desarrollando durante millones de años de evolución: estrategia y procesamiento visual.

La capacidad de extraer información de un torrente de datos visuales es una de nuestras grandes bazas. Estamos programados para buscar orden en el caos, patrones en el ruido blanco, formas conocidas en el desorden. Áreas tales como la minería de datos visual intentan explotar precisamente esta característica. Por otra parte nuestra visión estratégica, la capacidad de trazar planes y seleccionar heurísticamente las ramificaciones más relevantes es también bien conocida en el ámbito -por ejemplo- de los juegos de tablero. Es precisamente en este área en el que investigadores de la Universidad de Michigan han intentado aunar ambas capacidades y dirigirlas hacia la resolución de problemas NP-completos. Andrew DeOrio y Valeria Bertacco, del departamento de ingeniería eléctrica e informática de la citada universidad, han desarrollado un entorno en el que se pueden resolver instancias del problema de la satisfacibilidad lógica mediante un juego lejanamente relacionado con el clásico lights off.

FunSAT - Pulsa sobre la imagen para jugar

FunSAT - Pulsa sobre la imagen para jugar

En el tablero tenemos una matriz de burbujas que representan las cláusulas de la instancia del problema (esto es, las restricciones que debemos satisfacer). Estas cláusulas dependen de un conjunto de variables, representadas como rectángulos en los bordes del tablero. Pulsando sobre éstos podemos fijar una cierta variable a cierto/falso o dejarla indefinida. De resultas de cualquiera de estas acciones algunas cláusulas pasarán a estar satisfechas (lo que se indicará mediante el color verde) o insatisfecha (un tono grisáceo, tanto más oscuro cuantas menos variables que puedan afectar a dicha cláusula nos queden sin asignar). El tamaño de cada burbuja indica el número de variables que intervienen en ella (se puede jugar también a 3-SAT, variante clásica en la que todas las cláusulas tienen 3 variables involucradas).

Lo interesante es que las instancias de SAT que se plantean en este juego corresponden supuestamente a problemas de diseño VLSI.  El análisis de lo que el juego puede dar de sí lo han publicado en un artículo titulado

  • Human computing for EDA

que presentarán en la próxima Design Automation Conference, que se celebra en San Francisco en estos días. El artículo aún no está disponible, por lo que se puede añadir poco más a lo ya comentado. Esperaremos a leerlo para ver cuál es el planteamiento a largo plazo del invento, que a priori diríase que adolece de un problema de escalabilidad. Y es que el ser humano es extraordinario, pero dentro de un límite.

Posted in Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , | 2 Comments »

Los incidentes del LHC y la inmortalidad cuántica

Posted by Carlos en julio 27, 2009

Observación y función de onda son dos de los elementos de más sinuosa interpretación ontológica en el ámbito de la mecánica cuántica, y sobre los que el debate filosófico no cesa. Son múltiples los experimentos mentales concebidos a colación de la traslación a nivel macroscópico de fenómenos cuánticos en los que los citados conceptos juegan un papel central. El gato de Schrödinger es posiblemente el más conocido a nivel popular, y sobre la base del mismo se han construido escenarios más complejos en los que la participación de observadores adicionales pone a prueba la sutileza de los conceptos mencionados. Por ejemplo, ya comentamos hace tiempo el experimento del amigo de Wigner, una especie de versión matrioshka del gato de Schrödinger en el que se construye una cadena de observadores conscientes en cajas concéntricas, y que pone el acento en la relación entre consciencia y observación. Otro experimento relacionado con este extremo es el denominado suicidio cuántico.

El experimento del gato de Schrödinger

El experimento del gato de Schrödinger

La disposición de este experimento puede variar, pero para simplificar podemos imaginarnos que sustituimos al gato de Schrödinger por el propio Schrödinger, y que observamos el experimento desde su punto de vista. Supongamos por ejemplo que lo que hace Schrödinger es activar un dispositivo que incorpora un generador cuántico de números aleatorios que provocará o no el disparo de un cierto dispositivo letal incluido en la caja. El bueno de Schrödinger tiene una cierta probabilidad de sobrevivir, pero si repite el experimento una y otra vez la ruleta cuántica terminará por tocarle y su existencia tocará a su fin… o no. Y es que de acuerdo con la interpretación de los múltiples universos, cada vez que se activa el dispositivo se produce una ramificación en un universo en el que Schrödinger muere y otro en el que sobrevive. Es únicamente en este segundo universo en el que Schrödinger puede jugar de nuevo, y en el que se produce una nueva bifurcación. Eso quiere decir que existe un universo en el que –para incredulidad de Schrödinger, que llegará a sentirse invulnerable– siempre sobrevive. En este caso se puede hablar apropiadamente de inmortalidad cuántica. Nótese la reminiscencia antrópica del experimento, ya que el razonamiento sobre la propia existencia requiere que se sobreviva al experimento.

LHC black hole

Credit: Ecuador Ciencia

Viene todo esto a cuento de un comentario en Accelerating Future acerca de los nuevos problemas detectados en el LHC y que una vez más provocan un retraso en su puesta en funcionamiento. Concretamente, en esta ocasión se han detectado dos fugas entre el circuito de helio y el aislamiento de vacío, lo que en principio provocará que el reinicio del LHC no se produzca hasta mediados de noviembre. Recordemos que este es el tercer incidente serio que afecta a la fecha de entrada en estado operacional del LHC, tras la explosión de la envoltura criostática de uno de los gigantescos imanes cruadrupolos el 27 de marzo de 2007, y de un escape masivo de helio líquido el 19 de septiembre de 2008. Estos incidentes en modo alguno comprometen la seguridad del LHC, y de hecho no tienen nada que ver con los hipotéticos riesgos existenciales (e.g., creación de microagujeros negros estables, materia extraña, etc.) del mismo, cuidadosamente estudiados y descartados. No obstante, si hay alguien que aún abriga algún temor (o está deseando hacerlo), aquí puede encontrar una fuente adicional de inquietud: si el LHC fuera un dispositivo que desencadenara el Apocalipsis una vez activado, y de ser correcta la interpretación de los múltiples universos de la mecánica cuántica, estaríamos en la misma disposición que Schrödinger en el experimento del suicidio cuántico. Existiría entonces un universo en el que veríamos que el LHC fallaría persistentemente (en los universos en los que no fallara cesaría nuestra existencia). La ocurrencia de nuevos incidentes -tanto más si estos son cada vez más improbables- que continuaran retrasando la plena operatividad del LHC podría hacer que alguien se planteara si no estamos en la línea de universo “afortunada” (eso, y que los ingenieros del CERN serían como los mecánicos de Fernando Alonso, claro).

Si alguien ha llegado a inquietarse realmente con lo anterior, puede reconfortarse en el hecho de que está sujeto a la interpretación de los múltiples universos, de que lo acontecido hasta ahora no entra dentro de lo excepcional, y de que la puesta en marcha del LHC está prevista para otoño de este año, por lo que en el peor caso tenemos todo el verano por delante.

Posted in Física, What-if | Etiquetado: , , , , | 4 Comments »

Música para el domingo – Man on the Moon (R.E.M.)

Posted by Carlos en julio 26, 2009

El domingo es día de asueto y nada mejor que un poco de música para amenizarlo. Por ejemplo, este tema de R.E.M. de 1992 titulado “Man on the Moon“. Además de un recuerdo/homenaje a Andy Kaufman, la canción hace referencia al aterrizaje del hombre en la Luna (y en cierto modo a la conspiranoia en torno al evento), del cual estamos en estos días de aniversario. El vídeo corresponde a una actuación de R.E.M. con Bruce Springsteen. ¡que lo disfruten!

Posted in Música | Etiquetado: , , , | Comentarios desactivados

“Expendable” de James Alan Gardner

Posted by Carlos en julio 24, 2009

Expendable (James Alan Gardner)
Expendable es una novela de 1997 del escritor y matemático canadiense James Alan Gardner. Es de hecho la opera prima de Gardner, que ya había tenido anteriormente un cierto éxito (premio Aurora y candidaturas a Nebula y Hugo incluidos) con historias cortas. En ella entramos en contacto con el universo de la “Liga de los Pueblos”, telón de fondo de la obra de Gardner y que ha servido de escenario para siete títulos hasta la fecha.

La premisa argumental de este universo es la existencia de una suerte de organización a nivel galáctico –la mencionada Liga de los Pueblos– bajo cuya égida se encuentran aquellas especies con capacidad para el viaje interestelar. Esta organización tiene un imperativo existencial: proteger la vida inteligente. Cualquier especie que anhele expandirse más allá de su sistema estelar debe adherirse a esta directiva, lo que en la práctica implica que toda forma de violencia que conduzca o pueda conducir a la muerte de un ser inteligente (da igual si de la propia especie o de otra distinta) está absolutamente vedada; está prohibido incluso el transporte de armas potencialmente letales a bordo de naves interestelares. El castigo por infringir (por acción o inacción) esta norma básica es la destrucción del infractor tan pronto se encuentre fuera del pozo gravitatorio de su estrella de origen o, en caso de que la infracción sea cometida por la especie en su conjunto o por su cuerpo gobernante, el confinamiento de dicha especie en su sistema natal. Dado que la Liga de los Pueblos comprende a civilizaciones cuyo nivel tecnológico está más allá de toda comprensión, no es posible ocultar ningún acto contra la mencionada directiva, lo que se traduce en la efectiva desaparición de guerras y violencia física en aquellas especies que se acogen a la misma (y que a cambio obtienen el acceso al viaje interestelar, además de otro tipo de avances tecnológicos).

Indudablemente, la interiorización de la no-violencia conduce a profundos cambios sociales en numerosas especies, en particular en la humana (y más concretamente en la fracción de la especie humana que accedió a esta directiva, y que en recompensa obtuvo “Nueva Tierra”, un planeta terraformado virtualmente idéntico a la Tierra original; una parte de la especie humana prefirió seguir con sus usos habituales, y permanecen confinados en la “Vieja Tierra”). De resultas de los avances en ingeniería genética y medicina, combinados con la ausencia de violencia, una muerte humana se convierte en un suceso excepcional y profundamente traumático no sólo para los más cercanos sino incluso para la sociedad en conjunto. Esto supone un problema en relación con la exploración espacial, empresa extremadamente arriesgada y en la que pueden perderse vidas con cierta facilidad.

Enfrentados con esta situación, la Tecnocracia (el cuerpo gobernante de la Humanidad interestelar) encuentra una solución de pura ingeniería social. Dados los medios técnicos existentes es posible corregir cualquier tara física, y de hecho así se hace cuando el sujeto en cuestión tiene una discapacidad seria. Sin embargo, si la persona en cuestión no está inhabilitada física o intelectualmente, la tara (que puede incluir la simple fealdad) no es corregida. A pesar de su absoluta validez, estas personas son percibidas como diferentes por el resto de la sociedad, y de hecho cuando uno de ellos muere el impacto emocional de la sociedad es mucho menor: son los prescindibles a los que el título de la novela hace referencia. Estos prescindibles son seleccionados desde la infancia y asignados al cuerpo de exploradores, la sección de mayor riesgo dentro de la flota espacial, y cuyos deberes incluyen la exploración física de planetas desconocidos. En muchas ocasiones dicha exploración acaba con la muerte confirmada o simplemente con la desaparición del explorador (típicamente marcada por la expresión “Oh, shit”, últimas palabras que suelen oírse antes de que se corte la comunicación con el explorador). El duelo en esta situación es mínimo (“well, you know, that’s what expendable means”).

Festina Ramos, por Luis Royo

(c) Luis Royo

La protagonista de la historia es Festina Ramos, una exploradora cuya tara es una marca roja de nacimiento en una de sus mejillas. A bordo de la nave Jacaranda, Festina recibe una misión: ella y otro explorador deben acompañar a un almirante de la Flota en una exploración de superficie. Cuando dicho almirante llega a la nave se hace patente que sufre de demencia senil (las drogas anti-senectud dejan de ser efectivas eventualmente), y el destino de la misión parece sugerir claramente que la intención final es librar a la Flota de manera discreta de un alto oficial senil. Concretamente, su destino es Melanquin, un planeta aparentemente idéntico a la Tierra en condiciones ambientales, pero que por algún motivo desconocido es un pozo sin fondo de exploradores. Toda persona que puso pie en el planeta dejó de comunicar al cabo de pocos minutos.

Oar, por Luis Royo

(c) Luis Royo

Tras un futil intento de rebelión ante la muerte segura que dicha misión parece suponer, Festina y su compañero Yarrun (y el senil almirante Chee, cuya lucidez es mayor que la que el Alto Consejo imagina) entienden que su única posibilidad es descender a Melanquin bien pertrechados, y provocar un incidente que suponga que la misión se aborte. Sin embargo, esta posibilidad se verá truncada cuando lleguen a la superficie, y Festina se vea sola tras la muerte de sus dos acompañantes. No tardará sin embargo en entablar contacto con los habitantes de Melanquin, seres con remoto origen humano que con el paso del tiempo y a través de ingeniería genética se han convertido en criaturas autótrofas con aspecto de cristal traslúcido, y que a pesar de ser enormemente fuertes e inteligentes, se encuentran evolutiva y socialmente en un callejón sin salida. A través de Oar, uno de estos seres, Festina descubre que hay otros exploradores en Melanquin y acompañada de ella emprende el camino para encontrarse con éstos y buscar la manera de escapar del planeta. En este camino descubriremos el origen de la civilización de Melanquin, el pasado del almirante Chee, y las implicaciones de todos los eventos que ahí se desarrollan en relación con la directiva básica de la Liga de los Pueblos.

La novela tiene un ritmo ágil y una premisa que engancha. El escenario que se plantea una vez Festina está en la superficie provoca un pequeño bajón en las altas expectativas que un planeta con un peligro fatal y absolutamente desconocido creaba, pero el interés se recobra rápidamente cuando se comienza a desentrañar el porqué de Melanquin. Más aún, el viaje en busca de los exploradores tiene bastante acción y hay un clímax final de amplitud planetaria. Un epílogo bastante satisfactorio redondea una novela que se puede calificar de recomendable e interesante (y si alguien se encariña de Oar o de Festina, podrá reencontrarse con ellas en otros títulos de la saga).

Posted in Ciencia Ficción, Libros, Space Opera | Etiquetado: , , | 2 Comments »

Si las revistas científicas fueran blogs…

Posted by Carlos en julio 23, 2009

… sus artículos tendrían una sección de comentarios:

phd052709s

Lamentablemente no se ha puesto en práctica, ya que los pingbacks serían muy interesantes.

Por otra parte, eso supondría cambiar el Science Citation Index por Digg (o puede que Reddit o Slashdot) …

… y llegarías a catedrático cuando tuvieras suficiente karma.

Posted in Ciencia, Comic, Internet, Universidad | Etiquetado: , | 2 Comments »

Música para el domingo – We all stand together (Paul McCartney and the Frog Chorus)

Posted by Carlos en julio 19, 2009

El domingo es día de asueto y nada mejor que un poco de música para amenizarlo. Por ejemplo, este tema de 1984 titulado “We all stand together“. Se trata de una canción que Paul McCartney compuso para un corto de animación infantil titulado “Rupert and The Frog Song“. Es un tema amable, recordado por su pegadiza melodía y por los coros de ranas, y apropiado para las cálidas noches de verano junto a un lago. ¡Que lo disfruten!

Posted in Cine, Música | Etiquetado: , , , | 1 Comment »

Montreal, wrapping up…

Posted by Carlos en julio 18, 2009

Eggspectation Montreal es una ciudad que podría decirse tiene trastorno bipolar, aunque ha sabido adaptase a ello y lo lleva con soltura y naturalidad. Coexisten por un lado las realidades anglófona y francófona, y basta desplazarse algunas calles para ver cómo el centro de gravedad lingüístico pivota de un idioma al otro. El viejo Montreal es indudablemente francófono, aunque permeado por la influencia anglosajona, lo que ha dado lugar a efectos secundarios muy positivos en algunos casos: ¿dónde si no se pueden encontrar raciones de tamaño made-in-USA de platos franceses? No hace falta esforzarse mucho para encontrar buenos restaurantes, y aunque si bien los precios no parecen bajos (quizás afectados por la inflación de la temporada jazzística), la fortaleza del euro no los hace descabellados. Junto a la Place des Arts, lugar en el que se desarrolla la actividad al aire libre (y gratuita) del festival de jazz encontramos un restaurante llamado Eggspectation, cuya especialidad puede imaginarse. Los platos tienen nombres como “eggcitement”, “eggsuberant” o “eggstravaganza”, y pudimos dar cuenta de unos cuantos proto-embriones de pollo con los más diversos acompañamientos.

Monster in the FestivalBig Bird

La Plaza de las Artes es durante la celebración del festival un lugar con una atmósfera acogedora en el que se pueden encontrar extrañas criaturas y mejor música. El suave estío canadiense invita a pasear por el lugar con tranquilidad (otra manifestación de la bipolaridad de Montreal, ya que durante el atroz invierno la vida transcurre en gran medida a través de la laberíntica red de pasadizos subterráneos de kilómetros de longitud en la que es posible encontrar tiendas y restaurantes, además de poder desplazarse entre prácticamente cualesquiera edificios). Además de los numerosos escenarios preparados al efecto, es posible encontrarse con bandas de jazz tocando en casi cualquier esquina, y aunque las cervezas están a 5 CAN$ (en los vasos hay una leyenda que indica que ese precio ayuda a financiar los espectáculos al aire libre), merece la pena detenerse en cualquier terraza (o escalinata) y dejarte llevar por la música.

Jazz Band on Stage (I) Jazz Crowd Jazz Band on Stage (III) Jazz Band on Stage (II)

Al caer la noche la ciudad continúa con su pulso vital, y al llegar el sábado, fuegos artificiales (de cuya espectacularidad se ufanan orgullosos los locales). Por una vez, uno tiene la impresión de haber estado en el sitio justo en el momento adecuado.

Posted in Gastronomía, Lugares, Música, Viajar | Etiquetado: , , | 2 Comments »

Realidad Virtual y Vida Artificial: de la Biomecánica a la Inteligencia

Posted by Carlos en julio 14, 2009

Las charlas plenarias de las conferencias suelen navegar por la procelosa frontera que separa el tema central de la reunión con otros temas relacionados (y en ocasiones transcurren directamente al otro lado de la frontera). Suele ser una buena política, ya que en las zonas de confluencia las cosas se ponen divertidas, y de hecho este ha sido el caso de la primera de las charlas invitadas que hemos disfrutado. El orador era Demitri Terzopoulos, que estuvo involucrado en los comités de programa de estos saraos tiempo ha pero que nunca ha llegado a aplicar computación evolutiva a su área de trabajo. Era pues un gran desconocido a priori para el grueso de la audiencia -salvedad hecha de los que trabajan en visión por computador- a pesar de tener un currículo investigador talla XXL, y hay que decir que después de su charla los allí presentes recordaremos bien su nombre, pues fue una hora y media extremadamente interesante y entretenida.

El título de su charla fue “Artificial Life Simulation of Humans and Lower Animals: From Biomechanics to Intelligence”, y durante la misma intentó explicarnos algunas de las claves de la emergente fusión entre realidad virtual y vida artificial, cuyo objetivo final es la construcción de agentes biomiméticos autónomos. En sus diapositivas iniciales nos mostró lo que no es uno de dichos agentes, como por ejemplo los dinosaurios de Parque Jurásico, o los protagonistas de Toy Story por citar un par de ejemplos. Las cosas empezaron a calentarse un poco con los ejércitos de El Señor de los Anillos, que podríamos englobar dentro de la categoría de enjambres (animar manualmente cada uno de los miles de personajes en el ejercito es inasumible, por lo que cada uno de ellos está dotado de un sistema simple basado en reglas para determinar su comportamiento). En este punto fue donde nos presentó los diferentes niveles en los que hay que intervenir para construir un sistema biomimético autónomo, y que se organizan jerárquicamente como sigue:

Niveles para la simulación de un sistema biomimético. Credit: Demitri Terzopoulos

Niveles para la simulación de un sistema biomimético. Credit: Demitri Terzopoulos

La ilustración inicial de estas ideas corrió a cargo de una fauna submarina sintética que el propio Demitri desarrolló con sus colaboradores. El nivel más bajo de la jerarquía estaba definido en este caso por un armazón de cada uno de los peces, construido a partir de partículas unidas mediante una combinación de muelle y amortiguador. Algunos de los segmentos del pez hacen las veces de músculos, y en ellos la longitud natural del muelle puede modificarse a voluntad. El modelo resultante queda descrito por una colección de ecuaciones diferenciales que determinan la respuesta dinámica al movimiento del pez en el medio líquido. La locomoción del pez se optimizó mediante una técnica de búsqueda local (no entró en muchos detalles al respecto) para que resultara en el movimiento más fluido y energéticamente económico. En este punto, el movimiento de natación de peces y morenas resultante era extremadamente realista.

Para simular la percepción, los peces estaban dotados de sensores visuales que permitían cubrir un cierto ángulo en la dirección de orientación de la criatura. La información así obtenida era procesada según técnicas estándar de visión por computador, para proporcionar la entrada al siguiente nivel, el comportamiento. Éste es esencialmente reactivo, y está determinado por una red neuronal que determina la acción correspondiente a un determinado estímulo. Para la simulación de los animales marinos se incluyó un registro de memoria con capacidad unidad. Esto permite que el animal desarrolle un comportamiento básico -seguir un objeto, alimentarse, ..- que pueda ser interrumpido cuando por ejemplo se entre en modo huida al detectar un depredador, y luego reanudado cuando cese el peligro.

En el ejemplo del mundo submarino no había mucho lugar para el nivel más alto de la pirámide y que entronca plenamente con la inteligencia artificial. En el siguiente ejemplo que abordó -seres humanos sintéticos- sí que era más relevante, aunque no entró en él. Sí describió unos modelos muy interesantes relativos a la simulación de rostros humanos (quien haya visto Final Fantasy recordará el fotorrealismo de algunos de los personajes). Los niveles más bajos de la pirámide se abordan de la misma manera que en el caso de los peces, aunque más arriba se introduce un elemento más interesante: redes bayesianas para la determinación del comportamiento. Resultaba curioso ver cómo un rostro humano sintético era capaz de reaccionar a estímulos visuales, siguiendo la trayectoria de un objeto o mostrando enfado o satisfacción dependiendo de su patrón de movimiento.

La charla terminó con algunas ideas sobre lo que podemos esperar en el futuro. Alguien planteó si quizás en algunos años una versión virtual de Demitri podría dar esa misma charla ante una audiencia igualmente virtual. Él estuvo de acuerdo en que eso será factible, aunque no cree vivir para verlo (hay que decir que no es muy mayor, cuarenta y tantos según mi ojo de buen cubero). Yo soy sin embargo más optimista que él.

Posted in Aprendizaje Automático, Computación Evolutiva, Inteligencia Artificial, Vida Artificial | Etiquetado: , , , , | 6 Comments »

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