Sólo para frikis que quieran usar un ordenador cuántico

El gran problema de los ordenadores cuánticos es la falta de algoritmos. Muchos jóvenes frikis desarrollarían gratis algoritmos cuánticos si pudieran, pero no tienen acceso a un ordenador cuántico donde ejecutarlos. El profesor Jeremy O’Brien de la Univ. de Bristol lo sabe y ha anunciado hoy, 6 de septiembre, el proyecto Qcloud: Acceso gratis a un simulador de su ordenador cuántico (que utiliza tecnologías fotónicas). Los algoritmos que funcionen de forma correcta en el simulador podrán solicitar ser ejecutados en su ordenador cuántico de verdad de forma gratuita. Gracias a ello cualquier joven friki podrá desarrollar algoritmos cuánticos y ejecutarlos en un ordenador cuántico de verdad. ¿Te animas? ¿A qué estás esperando? Regístrate en la web bristol.ac.uk/quantum-computing, donde podrás leer los manuales y las guías de usuario del simulador, dale al coco y ponte a desarrollar algoritmos cuánticos, ¿no te gustaría ser el primero en usar un ordenador cuántico gracias a Qcloud? Nos lo cuentan en «Quantum in the Cloud,» Press release, Univ. Bristol, 6 Sep. 2013; me he enterado gracias a un tuit de Jorge Barreto (@GHKBarreto).

Por qué el ordenador «cuántico» D-Wave Two no es cuántico

Lo he dicho en varias ocasiones en este blog, pero conviene repetirlo. Un ordenador montado a base de conectar 512 cubits (bits cuánticos) superconductores no es un ordenador cuántico. Para serlo además debe demostrar que durante su operación estos cubits están entrelazados entre sí; si no lo están, estos cubits se comportan como bits probabilísticos y es un ordenador clásico no determinista sin paralelismo cuántico. La compañía canadiense D-Wave no ha demostrado que su ordenador D-Wave Two con 512 cubits sea un ordenador cuántico, por tanto es un ordenador clásico no determinista. Esta hipótesis queda confirmada al analizar con ojos críticos los resultados de D-Wave Two que han sido publicados por la propia compañía. Más aún, ni siquiera es un ordenador de propósito general, capaz de ejecutar un algoritmo no determinista arbitrario; se trata de un ordenador de propósito específico que ejecuta un único algoritmo, el recocido cuántico, la versión con cubits del recocido simulado (simulated annealing). Esta entrada viene a colación por el artículo de Jesse Dunietz, «Quantum Computing Disentangled: A Look behind the D-Wave Buzz,» Scientific American, Aug 27, 2013.

Nuevo algoritmo de corrección de errores en recocido cuántico

El recocido cuántico («quantum annealing») es una forma de computación cuántica para la resolución de problemas de optimización combinatoria que presenta grandes ventajas (speedups) en algunos algoritmos respecto a las implementaciones basadas en el recocido simulado clásico («simulated annealing»). Pero esta técnica no es ventajosa con un gran número de cubits sino se usan técnicas de corrección de errores. La nueva técnica llamada QAC se ha mostrado usando 344 cubits superconductores en los ordenadores D-Wave One («Rainier») y D-Wave Two («Vesuvius») de la compañía canadiense D-Wave Systems. El problema resuelto se codifica con 86 cubits, siendo el resto de los cubits necesarios para la corrección de errores. El artículo técnico, para los interesados en los detalles, es Kristen L. Pudenz, Tameem Albash, Daniel A. Lidar, «Error corrected quantum annealing with hundreds of qubits,» arXiv:1307.8190, Subm. 31 Jul 2013.

Comparan experimentos y simulación SPH para saltos hidráulicos

Los que trabajamos en métodos numéricos disfrutamos con los artículos que comparan resultados numéricos con resultados experimentales. Me han gustado los resultados sobre saltos hidráulicos y rotura de ondas obtenidos en la ETSI Navales de la Universidad Politécnica de Madrid. Más abajo os presento un vídeo de los resultados experimentales (su web incluye muchos más). Supongo que los lectores poco interesados en física computacional de fluidos no apreciarán este tipo de estudios comparados, pero quizás alguno sea aficionado a los gráficos por ordenador y a la simulación de fluidos para películas de Hollywood, en cualquier caso, no me resisto a recomendar la lectura de los dos artículos de Benjamin Bouscasse, Andrea Colagrossi, Antonio Souto-Iglesias, José Luis Cercós Pita, «Mechanical energy dissipation induced by sloshing and wave breaking in a fully coupled angular motion system. Part II: Experimental Investigation,» arXiv:1307.6064, 23 Jul 2013, y «Mechanical energy dissipation induced by sloshing and wave breaking in a fully coupled angular motion system. Part I: Theoretical formulation and Numerical Investigation,» arXiv:1307.6064, 23 Jul 2013.

Factorizan un número entero de 20.000 bits utilizando el algoritmo cuántico de Shor pero con «truco»

El paradigma de los algoritmos cuánticos es el algoritmo de Shor para factorizar números enteros. Para reducir el número de cubits necesarios se puede utilizar un truco llamado «precompilación» basado en conocer a priori los factores del número. Gracias a esta técnica, usando dos cubits en una implementación semiclásica, se han factorizado el número RSA-768 (de 768 bits) y el llamado N-20000 (de 20.000 bits). Sin el truco de la precompilación del algoritmo de Shor hubieran sido necesarios 1.154 cubits y 30.002 cubits, resp. Dicho truco no es aplicable cuando no se conocen los factores del número por lo que no puede utilizarse en criptoanálisis de claves públicas. Además, dicho truco puede utilizarse incluso en una implementación clásica del algoritmo de Shor utilizando números aleatorios generados tirando monedas (que salga cara H o cruz T); el nuevo récord se ha obtenido usando dicho truco. Pero lo importante a destacar es que, hasta el momento, el algoritmo de Shor nunca ha sido implementado en un ordenador cuántico de forma completa (sin «precompilación»). El artículo técnico es John A. Smolin, Graeme Smith, Alexander Vargo, «Oversimplifying quantum factoring,» Nature 499: 163–165, 11 Jul 2013. Este artículo me viene ni que pintado porque el viernes 12 de julio imparto el curso «Presente y futuro de la computación cuántica» en un curso de verano «Alan M. Turing: Enigmático, visionario y condenado,» coordinado por Ernesto Pimentel, director de la E.T.S.I. Informática de la Universidad de Málaga, que se imparte en Veléz Málaga.

El juego de la vida de Conway implementado con filosilicatos

El juego de la vida es un ejemplo de un autómata celular, diseñado por el matemático británico John Horton Conway en 1970. Un filosilicato es un mineral formado por capas de tetraedros de (SiO₄)^4- unidos entre sí por los tres oxígenos de la base del tetraedro formando una red hexagonal y con el cuarto oxígeno de cada tetraedro apuntando hacia afuera de la capa. Los átomos de silicio y oxígeno pueden estar en su estado fundamental (0) o en un estado excitado (1). En la figura de arriba los átomos de silicio y oxígeno excitados se  representan por un punto negro y un círculo, resp. Los oxígenos pueden cambiar su estado en función del estado de sus 6 oxígenos vecinos y los silicios en función de sus 3 silicios vecinos. Las reglas son similares a las del juego de la vida de Conway. El estado de los átomos de oxígeno y silicio puede cambiar con las siguientes reglas: un nodo de silicio en estado 0 pasa a estado 1 sólo si tiene 1 o 3 vecinos en estado 1, y uno en estado 1 permanece en dicho estado sólo si tiene 2 vecinos en estado 1; un nodo de oxígeno en estado 0 pasa a estado 1 sólo si tiene dos vecinos en estado 1, y uno en estado 1 permanece en dicho estado sólo si no tiene vecinos en estado 1, o si tiene 6 (regla R65), 4 (regla R68) o 3 (regla R72) vecinos en estado 1. Los patrones robustos en este juego de la vida con filosilicatos corresponden a defectos estables. Más información y ejemplos en Andrew Adamatzky, «Game of Life on Phyllosilicates: Gliders, Oscillators and Still Life,» Physics Letters A 377: 1597-1605, 2013 [arXiv:1306.0253].

Cuando el fin justifica los medios

El dogma central de la biología molecular, propuesto por Francis Crick en 1958, reza que todo gen (codificante) se transcribe en ARN mensajero que se traduce en una proteína. Hoy sabemos que las cosas nunca fueron tan sencillas. Un estudio del ADN de la levadura de la cerveza (S. cerevisiae) ha mostrado que, aunque contiene unos 6000 genes codificantes de proteínas, produce 1,88 millones de transcritos de ARN. Estas moléculas de ARN se llaman isoformas de transcripción (TIF por sus siglas en inglés) y tienen diferentes secuencias de inicio (5′) y final (3′). ¿Cuál es su función biológica? Lo más fácil es decir que su papel es regular la expresión de otros genes, pero esta función ha sido demostrado sólo en unos cientos de casos. La mayoría de los TIF podrían no tener ninguna función biológica, siendo un subproducto irrelevante de la maquinaria de transcripción. ¿Podrían tener algún papel en la evolución? Como es obvio, el contenido de TIF en un momento dado de una célula dentro de una población la diferencia de todas las demás y quizás podría proporcionarle la oportunidad de estar mejor adaptada a cambios en su entorno. Quizás esta gran diversidad de ARN transcritos sea una de las razones por la que es difícil matar a todas las células cancerosas de un tumor. Así finaliza su News & Views, cuyo titulo he copiado, B. Franklin Pugh, «Molecular biology: The ends justify the means,» Nature 497: 48–49, 02 May 2013, quien se hace eco del artículo técnico de Vicent Pelechano, Wu Wei and Lars M. Steinmetz, «Extensive transcriptional heterogeneity revealed by isoform profiling,» Nature 497: 127–131, 02 May 2013.

El «arte» de la filogenética molecular

Cuando se habla de artes y ciencias (Arts & Sciences) la ingeniería se encuentra justo en la mitad, siendo en muchos casos arte y ciencia a partes iguales. Los algoritmos bioinformáticos utilizados en biología molecular para obtener un árbol filogenético son muy sencillos, pero la práctica del «arte de la filogenética molecular» sólo se aprende con la experiencia. Un buen arbol filogenético depende de qué genes (o secuencias dentro de ellos) se seleccionen y alineen, y de cómo se estime el efecto del entorno y de la evolución por selección natural en los organismos estudiados. Para el experto no hay ningún problema, por eso es un experto, pero la situación para el profesor que tiene que enseñar este arte no es fácil, pues incluso un gran «artista» puede que no sepa explicar de forma adecuada cómo decide cuando su obra es «perfecta» y está acabada. Un análisis filogénetico de 1070 ortólogos de 23 genomas de levadura ha permitido obtener 1070 árboles filogenéticos diferentes. ¿Cuál es el mejor entre todos ellos? ¿Existe el árbol filogenético óptimo? ¿Cómo debe lidiar el filogenetista molecular con este problema? Supongo que pensarás que me como mucho el coco, pero al menos no soy el único: Leonidas Salichos, Antonis Rokas, «Inferring ancient divergences requires genes with strong phylogenetic signals,» Nature 497, 327–331, 16 May 2013. Por cierto, los algoritmos bioinformáticos de filogenética molecular son parte del contenido que imparto a mis alumnos. ¡Cosas bolonias!

PS (17 mayo 2013): Por cierto, dos genes de dos especies de seres vivos son ortólogos si su origen evolutivo es un único gen de un ancestro común a ambos. La aplicación a los 1070 árboles filogenéticos diferentes obtenidos de las técnicas de bootstrap y de selección de árboles de consenso reduce las incongruencias, pero en ningún caso logra que en todos los nodos se supere un consenso del 50%. Más aún, cientos de estos árboles filogenéticos muestran «errores graves» agrupando especies «lejanas» como si hubieran divergido hace muy poco.

Simulación numérica multiescala de las burbujas de la espuma

La belleza de la espuma bajo luz diurna es indudable, pero el estudio mediante ordenador de la evolución (reología) de cada una de las membranas líquidas (películas de jabón)  que la forman no es nada fácil pues involucra escalas en espacio y tiempo que varían en seis órdenes de magnitud. Se publica en Science un nuevo modelo matemático que permite una simulación multiescala de gran precisión basada en tres etapas: en la primera se calcula la solución de equilibrio estático, en la segunda se estudia el drenaje del líquido a través de las membranas y las fronteras entre ellas, y en la última se calcula la posible rotura en las zonas más delgadas de las películas de fluido. Este proceso se repite de forma iterativa. El resultado es una simulación sin precedentes de la evolución de la espuma lejos del equilibrio. Las espumas tienen una gran variedad de aplicaciones en la industria y en el diseño de materiales. Por ello, la simulación multiescala de su física promete importantes repercusiones prácticas. Nos lo cuenta Denis Weaire, «A Fresh Start for Foam Physics,» Science 340, 693-694, 10 May 2013, que se hace eco del artículo técnico de Robert I. Saye, James A. Sethian, «Multiscale Modeling of Membrane Rearrangement, Drainage, and Rupture in Evolving Foams,» Science 340: 720-724, 10 May 2013.

Nota dominical: El problema del viajante

El problema del viajante consiste en encontrar el camino más corto que permite visitar una serie de ciudades conectadas por carreteras volviendo al punto de partida y visitando cada ciudad una sola vez. No hay ningún algoritmo eficiente para resolver este problema (que es NP-duro [1]). En 1950 los ordenadores permitían resolver un problema con 50 ciudades, en 1980 con unas 2300 ciudades y en 2006 se alcanzó el récord actual, 85900 ciudades (en la figura aparecen 13509 ciudades de EEUU). Los informáticos han tratado de descubrir algoritmos eficientes que aproximen la solución del problema. En 1976, Nicos Christofides (Imperial College, Londres) desarrolló un algoritmo eficiente que produce caminos cuyo coste excede al óptimo en menos del 50% [2]. ¿Se puede mejorar? En 2011, se logró mejorar el algoritmo de Christofides con un nuevo algoritmo eficiente que excede del óptimo en menos del 49,99999999999999999999999999999999999999999999999996 por ciento [3]. ¿Por qué ha costado tanto obtener una ventaja tan pequeña? Nadie lo sabe, pero resulta muy sugerente. Nos lo cuenta Erica Klarreich, «Computer Scientists Take Road Less Traveled. After decades without progress, new shortcuts are discovered in the traveling salesman problem,» Simons Foundation, Jan 29, 2013.

Referencias

[1] Richard M. Karp (Univ. California at Berkeley), «Reducibility among combinatorial problems,» pp 219-241 in «50 Years of Integer Programming 1958-2008,» Springer, 2010 [free pdf].

[2] N. Christofides, «Worst case analysis of a new heuristic for the traveling salesman problem,» Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.

[3] Shayan Oveis Gharan, Amin Saberiy, Mohit Singh, «A Randomized Rounding Approach to the Traveling Salesman Problem,» IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, pp. 550-559 [free pdf].