La computación cuántica tiene algo “mágico” que llama la atención de casi todo el mundo. Los avances parecen lentos pero, vistos con cierta perspectiva, son muy rápidos. El presente de los computadores cuánticos son los procesadores de propósito específico. El futuro de la computación cuántica serán los computadores cuánticos programables. Hace unos meses fue “Fabricado el primer circuito integrado cuántico aunque sólo de 2 cubits.” Ahora se publicará en Nature Physics la fabricación del primer chip cuántico programable de 2 cubits. Un computador cuántico universal capaz de implementar cualquier algoritmo cuántico de 2 cubits. Parece un avance pequeño, pero en seis meses es un avance enorme. Además, este nuevo dispositivo podría ser la base para el desarrollo de una matriz de puertas cuánticas programable (programmable quantum gate array o PQGA). El trabajo técnico ha sido desarrollado en el NIST (National Institute of Standards and Technology) en Boulder, Colorado, EEUU y publicado como D. Hanneke, J. P. Home, J. D. Jost, J. M. Amini, D. Leibfried, D. J. Wineland, “Realization of a programmable two-qubit quantum processor,” Nature Physics, Published online, 15 November 2009. En español se han hecho eco de este avance varios foros, entre ellos destaca el blog de nuestro amigo MiGUi, “Presentan el primer ordenador cuántico universal programable,” 15 Nov. 2009, entrada cuya lectura desde aquí recomiendo. Mi idea es complementar dicha entrada con una figura (arriba) y un comentario personal (abajo). Nada más. Por cierto, la noticia ya ha sido meneada como “El NIST devela el primer procesador “universal” programable de información cuántica,” como no, por el prodigioso mezvan, a quien desde aquí hay que agradecer su gran labor divulgativa en Menéame.
Lo que hay que tener más claro sobre la computación cuántica es que es una computación probabilística (o estocástica), por lo que no puede pretenderse una fiabilidad del 100% (como se exige a la computación clásica determinista). El nuevo chip cuántico universal de 2 cubits alcanza una fiabilidad promedio cercana al 80% lo que es mucho. La figura que abre esta entrada muestra el circuito de dos computadores cuánticos universales, de 1 y 2 cubits, así como la fiabilidad del mismo para algunos (4) circuitos lógicos cuánticos concretos. Como se ve en la parte derecha de la figura, la fiabilidad del computador cuántico universal depende de la salida del circuito programado.
Un gran trabajo que dará mucho que hablar en el futuro. ¿Podrán estos investigadores combinar varios circuitos de 2 cubits para obtener un computador de, digamos, 4 cubits? Yo quiero creer que sí. No es nada fácil. Tiempo al tiempo.
El campo magnético de la Tierra está generado por los movimientos del fluido del manto fuera de su núcleo gracias a un efecto parecido al de una dinamo de un coche. Para verificar esta hipótesis razonable es necesario realizar simulaciones por ordenador de la magnetohidrodinámica del manto y las condiciones de contorno utilizadas en dichas simulaciones son muy importantes. Las simulaciones que suponen que el núcleo está a una temperatura fija (condiciones de Dirichlet) producen un campo magnético mucho más débil que el observado. Nuevas simulaciones han demostrado que un flujo de calor constante (condiciones de Neumann) resultan en un campo magnético dipolar que permite explicar el campo magnético terrestre mediante ordenador y estudiar su dinámica. El vídeo que abre esta entrada ilustra utilizando una proyección de Mollweide uno de los resultados obtenidos mostrando claramente la bipolaridad del campo magnético (radial) y su dinámica durante unos 7.000 años [más vídeos aquí]. La imagen de abajo muestra cortes transversales del manto también obtenidos con estas simulaciones por ordenador. Un gran trabajo de Ataru Sakuraba y Paul H. Roberts, publicado en “Generation of a strong magnetic field using uniform heat flux at the surface of the core,” Nature Geoscience 2: 802-805, 2009, que nos comenta en detalle Bruce Buffett, “Geodynamo: A matter of boundaries,” Nature Geoscience 2: 741-742, 2009.
Los aficionados a este blog ya sabéis mi gusto personal por la física computacional y por la belleza de las figuras y gráficas que ilustran los resultados de las simulaciones. La de abajo es una buena muestra de ello. Muestra tanto las componentes del campo de velocidades como del campo magnético, vista desde el norte, a una altura un décimo del radio terrestre. En concreto las componentes radiales de la velocidad (c,d), azimutales (e,f) y las componentes azimutales del campo magnético (g,h).
Por cierto, los interesados en el geomagnetismo terrestre disfrutarán con la mayoría de las conferencias del KITP Program: Dynamo Theory (May 5 – July 18, 2008), coordinador por Chris Jones, Daniel Lathrop, Steven Tobias, y Ellen Zweibel. Incluyen transparencias, audio y vídeo de la mayoría de conferencias y discusiones. Que además sirven para practicar el inglés científico.
Esta entrada es sólo para lanzar la liebre a ver si alguien sabe algo más que yo sobre lo que opinan los expertos al respecto de este nuevo candidato a demostración breve del teorema de los cuatro colores.
El dinero electrónico tiene dos problemas graves, cómo evitar su falsificación y cómo garantizar el anonimato de su propietario. La teoría del cifrado cuántico de información permite desarrollar monedas cuánticas con estas propiedades. Todas las monedas cuánticas tienen la misma denominación y están representadas por estados cuánticos idénticos. La idea del dinero cuántico no es nueva, fue propuesta en 1983, pero hasta 2003 no se logró que el dinero cuántico garantizara el anonimato, eso sí, a costa de ser vulnerable a ciertas falsificaciones. Los autores proponen dos nuevos modelos para el dinero cuántico basados en ideas previas de Scott Aaranson (2005) que garantizan la propiedad de anonimato y no son falsificables. Un gran avance en cifrado cuántico desde el punto de vista teórico que quizás en un futuro no muy lejano sea realizado de forma práctica en laboratorio. El artículo técnico es Michele Mosca, Douglas Stebila, “Quantum Coins,” ArXiv, 6 Nov 2009.
El ISI Web of Science es la herramienta bibliométrica más utilizada en la actualidad. Aún así, tiene sus limitaciones. Por ejemplo, sólo permite buscar hasta 100.000 documentos. ¿Qué pasa si buscamos toda la producción española? ¿Y si buscamos toda la producción de los EEUU? Obviamente, no parece fácil. Aunque tampoco es difícil si uno le da un poco al “coco”. Quizás merezca la pena pensar un poco al respecto antes de seguir leyendo… ¿Cómo buscarías toda la producción española?
Los que no quieran pensar pueden recurrir directamente a una posible respuesta de un cubano y sus coautores en el artículo Ricardo Arencibia-Jorge, Loet Leydesdorff, Zaida Chinchilla-Rodriguez, Ronald Rousseau, Soren W. Paris, “Retrieval of very large numbers of items in the Web of Science: an exercise to develop accurate search strategies,” ArXiv, Submitted on 6 Nov 2009. Por cierto, el ejemplo de Cuba es curioso y nos permite conocer de primera mano la magnitud de la producción científica de este “pequeño” país en el año 2007.
¡Que no te quieres leer dicho artículo y quieres conocer la respuesta! Operaciones elementales de conjuntos… ¿recuerdas los diagramas de Venn que te enseñaron en la escuela?
El hidrato de un gas es el material que se obtiene al congelar una mezcla de agua y gas, de tal forma que la retícula molecular del hielo encierre a dicho gas. El “hielo de metano” o hidrato de metano es el ejemplo más habitual y se encuentra bajo las capas de lodo marino. Sorprendentemente es un material inflamable, arde al acercar una llama, y podría ser utilizado como combustible, pero el metano es un gas de invernadero. ¿Cómo se forma el hidrato de metano? Matthew R. Walsh y sus colaboradores de la Colorado School of Mines, EEUU, han utilizado simulaciones dinámicas moleculares para estudiar la formación espontánea del hidrato de metano y su crecimiento. Los resultados del ordenador permiten seguir el proceso en detalle en una escala de microsegundos. El proceso se basa en la formación de “jaulas” moleculares en las que se ven encerrados los átomos de metano que se van autoorganizando hasta formar una estructura ordenada similar a un cristal. Este proceso es espontáneo porque es energéticamente favorable. Los dos vídeos que acompañan esta entrada ilustran este proceso de nucleación y “enjaulamiento” del metano en la retícula de hielo. El artículo técnico es Matthew R. Walsh, Carolyn A. Koh, E. Dendy Sloan, Amadeu K. Sum, David T. Wu, “Microsecond Simulations of Spontaneous Methane Hydrate Nucleation and Growth,” Science Express, Published Online October 8, 2009. Los detalles de las simulaciones por ordenador realizadas se encuentran en la Información Suplementaria.
Las simulaciones han requerido un día de trabajo cada 75 ns (nanosegundos) de simulación en un supercomputador de 23 TFLOP (“billones” de operaciones en coma flotante por segundo), constituido por un cluster de procesadores. Se han simulado 512 átomos de metano y 2944 moléculas de agua (hielo) enfriados a una temperatura de 305 K y a una presión de 10 MPa (megapascales). El dominio tridimensional simulado es un cubo con un lado de 5 nm (nanómetros) con condiciones de contorno periódicas. Se ha utilizado un paso de tiempo de 2 fs (femtosegundos).
El vídeo que abre esta entrada muestra un detalle de las fases iniciales de formación de las “jaulas” de hielo que encierran a las moléculas de metano dando lugar al crecimiento y formación del hidrato de metano. Sólo se muestran algunas de las moléculas de agua (esferas pequeñas) y de metano (esferas grandes). Han sido seleccionadas las que acaban formando parte de la estructura que se observa al final. Los enlaces de hidrógeno entre las moléculas de agua se muestran como líneas rojas a trazos.
El vídeo que cierra esta entrada muestra una visualización durante de 2 μs de tiempo real de la nucleación del hidrato de metano y su crecimiento a una temperatura de 250 K y una presión de 50 MPa. Las moléculas de agua se muestran como línes sólidas negras, los enlaces de hidrógeno entre las moléculas de agua se muestran como líneas a trazos rojas y las moléculas de metano como esferas sólidas azules, que cuando quedan “enjauladas” pasan a tener un color verde claro.
Vinton G. Cerf, actualmente vicepresidente de Google y entonces uno de los programadores jefe del proyecto, nos cuenta hoy en Nature como nació la Internet cuando Charley Kline, un estudiante del Network Measurement Center de la Universidad de California, Los Angeles (UCLA), envió el primer mensaje desde un ordenador a otro utilizando la red ARPANET. El otro ordenador se encontraba a 500 km. en el Stanford Research Institute. Kline quería enviar la palabra “login” pero sólo logró teclear la “l” y la “o” momento en que ambas máquinas se colgaron. La red ARPANET es el gérmen de lo que hoy en día es la Internet. Un artículo muy emotivo que podréis leer en Vinton G. Cerf, “The day the Internet age began,” Nature 461:1202-1203, 29 October 2009.
A mitad de los 1960, Robert Taylor, director del Information Processing Techniques Office de la Advanced Research Projects Agency (entonces llamada ARPA, ahora llamada DARPA) del departamento de Defensa de los EEUU lanzó como proyecto experimental el desarrollo de una red de comunicaciones basada en conmutación de paquetes. El proyecto fue liderado por Lawrence Roberts. El 2 de septiembre de 1969, el primer nodo de esta red fue instalado en el Network Measurement Center. El 29 de octubre Kline realizó su primer test del funcionamiento de esta red, que falló estrepitosamente. En diciembre de 1969 ya había 4 nodos de la ARPANET. Vinton G. Cerf era entonces uno de los programadores jefe que desarrollaron el software de comunicaciones para la Internet, programas para el acceso a ordenadores remotos, transferencia de ficheros entre ellos, correo electrónico, etc.
Robert Kahn de la compañía Bolt Beranek and Newman (BBN) encargada de diseñar los protocolos de comunicación (interfaces de procesado de mensajes les llamaban entonces) fue el encargado de la primera demostración pública de la ARPANET en la primera International Conference on Computer Communication, en Washington DC, octubre de 1972. Los programadores del Xerox Palo Alto Research Center decidieron desarrollar una red local de comuncaciones (LAN) inventando la Ethernet.
Kahn y Cerf colaboraron juntos en el desarrollo de un protocolo de control de la transmisión (transmission control protocol o TCP) y la arquitectura básica de la Internet. En septiembre de 1973 presentaron un artículo que se publicó en 1974 (V. Cerf, R. Kahn, “A Protocol for Packet Network Interconnection,”, IEEE Trans. on Communications 22: 637-648, May 1974, gratis aquí) que describía cómo interconectar un número arbitrariamente grande de redes de conmutación de paquetes y ordenadores conectados a ellas. Con financiación de la ARPA el nuevo protocolo empezó a ser implementado en 1975. En noviembre de 1977 se hizo un test en una red con tres concentradores (gateway). En 1978 estos protocolos y otros para e-mail, FTP y acceso remoto a terminales ya estaban completamente operativos en una primitiva Internet. El protocolo actualmente en uso, TCP/IP, fue implementado por primera vez en 1982.
En 1983 la red ARPANET fue dividida en dos redes, una militar MILNET, y otra civil (universidades, ONGs, centros de investigación y centros del gobierno). En 1986 se lanzó la red NSFNET de la National Science Foundation y en 1990 ARPANET oficialmente “murió.” Todos sus nodos y concentradores se incluyeron en la NSFNET. En 1995, NSFNET fue retirada ya que la Internet comercial ofrecía un servicio similar para la comunidad académica norteamericana a mucho menor coste. La Internet actual se “comió” a las redes que fueron sus “padres.”
Ni ARPANET ni Internet se desarrollaron para un propósito en particular. Eran redes abiertas a todo lo que se quisiera colgar en elllas. La filosofía de “la libertad ante todo” ha sido la clave del éxito de Internet.
PS (29 octubre 2009): El artículo de Miquel Barceló, “Internet, un proyecto militar fracasado. La conexión que supuso el inicio de la Red se logró, hoy hace 40 años, entre dos instituciones académicas de Estados Unidos,” El País, 29 otubre 2009, es el complemento ideal a lectura de esta entrada.
La ley de Moore afirma que casi cada 2 años se duplica la velocidad de procesamiento de información de los microprocesadores, los cerebros de los ordenadores. Así se ha cumplido en los últimos 40 años. Y seguirá cumpliéndose si nuevos ”transistores cuánticos” sustituyen a los transistores actuales. ¿Hasta cuándo? ¿Hay algún límite teórico? Lev Levitin y Tommaso Toffoli de la Universidad de Boston, Massachusetts, EEUU, han refinado los límites teóricos actuales que dependen del tiempo mínimo que necesita una partícula para cambiar de un estado cuántico a otro. Este tiempo depende de la energía involucrada, lo que implica que existe un límite teórico máximo a la velocidad de procesamiento de un ordenador dependiendo de la cantidad de energía que utilice. Si la ley de Moore se sigue aplicando dicho límite indica que entre 75 y 80 años se alcanzará la velocidad máxima físicamente posible para el procesamiento de información (utilizando ordenadores cuánticos si es que llegan a construirse). Nos lo han contado en muchos foros, como “In 75 years will reach the maximum possible processing speed,” ntra-net, 16-10-2009, y en “Physics: Quantum speed limit,” Nature, Research Highlights, October 29, 2009. El artículo técnico es Lev B. Levitin, Tommaso Toffoli, “Fundamental Limit on the Rate of Quantum Dynamics: The Unified Bound Is Tight,” Phys. Rev. Lett. 103: 160502, 2009 [gratis en ArXiv].
Técnicamente los autores han unificado dos desigualdades ya conocidas. Por un lado, una desigualdad obtenida a partir de un resultado de Mandelstam y Tamm (1945), obtenida por Fleming (1973), Anandan y Aharonov (1990) y Vaidman (1992), que afirma que el mínimo tiempo necesario para cambiar el estado cuántico de un sistema está acotado por donde , es el hamiltoniano del sistema y su función de onda. Por otro lado, una desigualdad obtenida por Margolus y uno de los autores, Levitin, en 1998, dada por donde es la energía media del sistema cuántico (supuesto que el estado de menor energía tiene asignado un valor cero). Levitin y Toffoli en el nuevo artículo generalizan ambas desigualdades demostrando que
,
donde . Esta desigualdad generaliza las dos anteriores de una forma aparentemente trivial, pero requiere un análisis cuidadoso. Para las dos desigualdades anteriores coinciden entre sí. Para han demostrado que para todo existe una familia de estados tales que , y que para existe una familia de estados tales que . Esto completa el círculo y muestra que la nueva desigualdad comprende a los dos anteriores como casos particulares y las unifica.
La escala de integración más alta posible para un transistor es utilizar una única molécula. El problema de este tipo de transistores monomoleculares es la presencia de estados cuánticos espurios para la conductancia que penalizan su funcionamiento. Una manera de evitar estos efectos es utilizar contactos superconductores. Investigadores franceses han logrado el primer transistor monomolecular fiable basado en una molécula del fulereno C60 entre dos electrodos de Alumino/Oro cuyo único inconveniente es que funciona a una temperatura por debajo de 1 Kelvin. El artículo técnico es Clemens B. Winkelmann, Nicolas Roch, Wolfgang Wernsdorfer, Vincent Bouchiat, Franck Balestro, “Superconductivity in a single-C60 transistor,” Nature Physics, Published online 25 October 2009 [versión gratis en ArXiv, que no incluye la información suplementaria disponible aquí].
Las clases de complejidad clásicas y cuánticas se relacionan entre sí de una forma complicada que todavía no conocemos en detalle y por ahora todo son hipótesis. Las clases P y BQP son las clases de problemas resolubles de forma eficiente (polinómica) en ordenadores clásicos y cuánticos, resp. Las clases NP y QMA contienen los problemas de decisión que creemos que son más difíciles para ordenadores clásicos y cuánticos, resp., para los que existen algoritmos eficientes, clásicos y cuánticos, resp., que permiten decidir si una solución es correcta o no. Un artículo reciente en Nature Physics ha demostrado que las clases QMA, NP y P colapsarían (serían iguales entre sí), resolviendo la conjetura P versus NP con una igualdad, si se puede resolver de forma eficiente la simulación de sistemas cuánticos descritos por la teoría del funcional densidad (DFT). Por ejemplo, si un modelo concreto, el modelo cuántico de Hubbard, se puede simular en tiempo polinómico. Nadie cree que esto sea posible, pero carecemos de una demostración, todavía. Nos lo cuenta el experto en la teoría de la complejidad cuántica Scott Aaronson, “Computational complexity: Why quantum chemistry is hard,” Nature Physics 5: 707-708, 2009, haciéndose eco del artículo técnico de Norbert Schuch & Frank Verstraete, “Computational complexity of interacting electrons and fundamental limitations of density functional theory,” Nature Physics 5: 732-735, 2009.
La clase de complejidad del Protocolo Merlín-Arturo (MA) es la clase de problemas de decisión resolubles por el protocolo siguiente. Merlín tiene recursos computacionales ilimitados y envía a Arturo una demostración de tamaño polinómico que prueba que la respuesta es “sí.” Arturo puede verificar dicha prueba en la clase BPP (en tiempo polinómico con un algoritmo probabilístico). Si la respuesta es “sí” existe una demostración que Arturo aceptará como correcta con una probabilidad mayor que 2/3 y si la respuesta es “no” todas las demostraciones serán aceptadas por Arturo con una probabilidad menor que 1/3.
La clase de complejidad cuántica del Protocolo Merlín-Arturo (QMA) es la versión cuántica de MA y corresponde a un Merlín que envía una mensaje con una prueba cuántica que Arturo puede verificar en la clase BQP (en tiempo polinómico utilizando un algoritmo cuántico). Si la respuesta es “sí” existe un estado cuántico (demostración) que Arturo aceptará como correcta con una probabilidad mayor que 2/3 y si la respuesta es “no” todos los estados (demostraciones) serán rechazados por Arturo con un probabilidad mayor que 2/3.
El modelo de Hubbard describe un gas de electrones fuertemente acoplados por potenciales de Coulomb en la retícula de un sólido y permite comprender la transición entre un material conductor y uno aislante. La técnica matemática más utilizada para simular este modelo físico es la llamada teoría del funcional densidad (density functional theory). El nuevo artículo demuestra que si dicho problema se puede simular de forma eficiente, las clases de complejidad QMA y P serán iguales. Esto implica un gran avance en dos frentes. Por un lado, en la propia teoría de la complejidad de algoritmos cuánticos. Y por otro lado, impone un límite fundamental a la propia teoría del funcional densidad ya que una demostración de que P =!= NP (lo que todo el mundo cree) implicaría que nunca podremos simular eficientemente problemas “aparentemente” tan sencillos como el modelo de Hubbard incluso utilizando ordenadores cuánticos.
Esto sorprenderá a muchos ya que la mayoría pensaba que la utilidad más importante de los ordenadores cuánticos (cuando los haya) será la simulación de sistemas cuánticos. Pero si un sistema cuántico tan sencillo como el modelo de Hubbard es tan complejo de simular en un ordenador cuántico como en uno clásico, dicha ventaja se cae por su propio peso. Los avances en computación cuántica no cesan y cada día nos sorprenden más a los que somos aficionados a este “arte,” a esta ciencia.
El libro de Edward N. Lorenz, el padre científico del efecto mariposa, titulado “The Essence of Chaos,” es una lectura obligada a los interesados en el caos determinista. Prácticamente sin fórmulas (salvo el capítulo sobre métodos numéricos) nos presenta muchos resultados interesantes. Uno de ellos es la caída caótica en una ladera ondulada, similar al efecto de la nieve llamado mogul en la jerga del esquí. Para los interesados en la formulación matemática detrás de las gráficas y comentarios de Lorenz, hemos de recomendar el trabajo en el software Mathematica desarrollado por (el ya emérito) Robert M. Lurie, “A Review and Demonstration of The Essence of Chaos by Edward N. Lorenz,” ArXiv, 12 Oct 2009 [publicado originalmente en Mathematica in Education and Research 11: 404-422, 2006]. El artículo incluye los códigos en Mathematica que permiten reproducir sus resultados. Los que sólo quieran jugar con el software pueden recurrir a “Chaos While Sledding on a Bumpy Slope,” Wolfram Demostrations Project, que incluye el código fuente. Los aficionados al caos, la matemática aplicada y/o Mathematica, que disfruten.
El físico británico J. J. Thomson ganó el Premio Nobel en 1906 por el descubrimiento del electrón. En 1904 propuso un problema matemático muy difícil de resolver en general: ¿cuál es la configuración de mínima energía para N electrones (con una fuerza repulsiva 1/r2) en una superficie esférica? Para N pequeño obtener la solución óptima a este problema es fácil. Para 4, 6, y 12 corresponden a los vértices de un sólido platónico. Hasta N=400 se conocen las soluciones óptimas. Sin embargo, para N>400 sólo se conocen algunas pocas, el resto son sólo las mejores candidatos obtenidas por ordenador. Wales, McKay y Altschuler han obtenido por simulación las mejores configuraciones hasta el momento en el rango N de 400 a 4000. La vídeo muestra cinco de los nuevos resultados para N=400, 752, 1632, 3952, y 4352. Los tres primeros son configuraciones simétricas. Los dos últimos son configuraciones asimétricas ligeramente de menor energía que las simétricas observadas. ¿Serán óptimas? Nadie lo sabe pero la búsqueda de la demostración por ordenador continúa. Nos lo cuenta Tony Phillips, “Progress on the Thomson problem,” Take on Math in the Media, September, 2009.
En una configuración de mínima energía cada electrón está rodeado de 6 vecinos cercanos (hexágonos verdes en el vídeo) resultando en una carga efectiva nula, excepto ciertos electrones que están rodeados de 5 vecinos (pentágonos rojos) con una carga efectiva de +1, o de 7 vecinos (heptágonos azules) con una carga efectiva de -1. Siendo Ci el número de los vecinos cercanos al electrón i-ésimo, la red que conecta los electrones más cercanos entre sí define una triangulación de la superficie de la esfera con V=N vértices, E = (1/2) Σi Ci aristas y F = 2 E/3 caras. El teorema de Euler, V-E+F=2, aplicado a esta tringulación nos da Σi (6-Ci) = 12, es decir, la suma de las cargas efectivas debe ser igual a 12. El problema de optimización a resolver es dónde hay que colocar las cargas efectivas para minimizar la energía total.
Como se observa en el vídeo, para las configuraciones con N = 400, 752, 1632, 3952, y 4352, conforme N crece, el número de heptágonos también crece. Las tres primeras configuraciones son (aproximadamente) simétricas, con una simetría icosaédrica aproximada que en algunos casos, como para N=1632, es exacta. Lo más sorprendente es que en muchos casos, como los dos últimos ilustrados en el vídeo, las configuraciones simétricas no son siempre las de menor energía. La energía potencial se define geométricamente como P = Σi>j |ri – rj|-1, donde se ha representado el electrón i-ésimo con un vector unitario ri in R3. Por ejemplo, para N=4352 la configuración cuasi-óptima tiene energía potencial P = 9311276, mientras que la configuración con 12 rosetas colocadas simétricamente (algo parecido a la configuración con N=1632 del vídeo) sólo alcanza un valor de P = 9311299. Es decir, una configuración más simétrica cercana a la mejor es sólo ligeramente peor. Realmente sorprendente.
La propagación de ondas en un medio sólido se puede simular utilizando una matriz de masas unidas por muelles (y en ciertas regiones, amortiguadores). Estas simulaciones son muy sencillas de implementar en un ordenador, basta simular la segunda ley de Newton, y conducen a resultados realmente espectaculares si incluimos obstáculos (regiones sin masas y muelles) o variaciones del índice efectivo de refracción (regiones donde cambie la masa en los nodos o la constante de Hooke de los muelles). Como ilustra la figura de arriba se puede simular la propagación de ondas mecánicas planas mediante la introducción de una oscilación forzada en las masas del extremo izquierdo de la matriz (se han introducido amortiguadores en los lados superior, inferior y derecho para evitar reflexiones no deseadas). Con un número suficientemente grande masas, que depende de la frecuencia de la señal armónica de excitación según el teorema del muestreo de Nyquist–Shannon, se logran simular efectos tan espectaculares como la reflección, refracción, difracción e interferencia de ondas. Si eres profesor de física y no te dan miedo los experimentos en el laboratorio de informática de tu centro, anímate, tus alumnos disfrutarán como críos y aprenderán mucha física. Por cierto, los profesores de física en carreras de informática no tienen excusa. El responsable de estas simulaciones es el argentino A. E. Dolinko de la Universidad Nacional de Rosario que ha publicado “From Newton’s second law to Huygens’s principle: visualizing waves in a large array of masses joined by springs,” Journal European Journal of Physics 30: 1217-1228, 8 September 2009. Un gran trabajo a imitar.
La figura muestra una puerta lógica OR implementada mediante dos factores de transcripción distintos (arriba) o dos quinasas (abajo). La plasticidad en la regulación de la transcripción de genes y la fosforregulación de proteínas permite emular circuitos lógicos combinacionales muy complejos. Poco a poco los biólogos están utilizando técnicas de lógica booleana y circuitos combinacionales para desvelar los secretos de esta plasticidad de la regulación en las redes genéticas y de transcripción que controlan a las células, que les permite adaptarse a un entorno que cambia continuamente. Aún así, todavía estamos lejos de comprender estos procesos en toda su complejidad. Por ejemplo, Liam J. Holt et al. “Global Analysis of Cdk1 Substrate Phosphorylation Sites Provides Insights into Evolution,” Science 325: 1682-1686, 25 September 2009 (de cuya información suplementaria he extraído la figura), han identificado en una molécula, 308 Cdk1, hasta 547 posiciones de fosforilación in vivo, es decir, esta molécula podría encontrarse in vivo hasta en 2547 configuraciones posibles. ¡Y sólo es una molécula! Afortunadamente la evolución no hace uso de todas estas configuraciones. Aún así, el número de posibles configuraciones cuando tenemos en cuenta múltiples moléculas es enorme. Una red booleana más compleja que la de un Pentium. Quizás, como en el caso del Pentium, su estructura modular es suficientemente sencilla como para que podamos soñar que algún día la comprenderemos.
Hay artículos con un título que nos obliga a leerlos sin excusa. Aunque sabemos que poco podremos aprender, nadie puede resistir la tentación. Ese es el caso de Abhijnan Rej, “Turing’s Landscape: decidability, computability and complexity in string theory,” ArXiv, Submitted on 10 Sep 2009, artículo enviado al 2º FQXI Essay Contest, cuyo foco es “What is Ultimately Possible in Physics?” Muchos se preguntarán “¿qué tiene que ver la informática teórica con el problema del vacío en teoría de cuerdas?” Poco quizás, pero el autor conjetura una conexión íntima entre ambas y trata de argumentarla de manera que sea “fácil” de leer para todos. Permitidme que os abra la boca al respecto.
La teoría de cuerdas proclama la unificación a alta energía (en la escala de Planck) de la mecánica cuántica y de la gravedad, sin embargo, a baja energía nadie ha sido capaz de obtener el modelo estándar, la realidad que conocemos. El mayor problema de la teoría de cuerdas es que permite prácticamente cualquier cosa a baja energía. A este problema se le llama “el problema del vacío” (string landscape problem). Os recuerdo que el vacío es el universo sin cuerdas, es decir, no está vacío, está relleno de las partículas elementales (puntuales) que constituyen la materia y la energía que observamos. El espacio de configuraciones para el vacío en teoría de cuerdas tiene una cardinalidad estimada de 10500 (un número inmenso e inimaginable). Como lo predice todo, la teoría de cuerdas no predice nada. Es por lo que algunos afirman que es una teoría no falsable.
¿Se podrá determinar alguna vez el vacío correcto de la teoría de cuerdas? El autor siguiendo ideas previas de Nabutovsky, Weinberger y otros, propone que el espacio de configuración de los posibles vacíos tiene una estructura fractal discreta, lo que le lleva a considerar el problema de su calculabilidad (o computabilidad). ¿Es calculable el vacío correcto? Dados dos puntos del espacio de configuración, ¿se puede decidir si corresponden a la misma física? El autor argumenta que estos problemas son computacionalmente intratables.
El modelo estándar utiliza simetrías gauge descritas mediante grupos de Lie (en concreto, SU(3)×SU(2)×U(1) módulo Z/6Z) para describir todas las partículas elementales mediante las representaciones de sus álgebras de Lie (generadores del grupo) asociadas. El autor recuerda que la descomposición de un grupo de Lie en sus subgrupos es un problema NP-completo (resultado un teorema clásico de la teoría de la complejidad computacional). Por lo que saber si el modelo estándar está incluido en el grupo de simetrías de un vacío dado es computacionalmente muy costoso.
¿Es continuo o discreto el espacio de configuración para los posibles vacíos en teoría de cuerdas? Un artículo de Acharya y Douglas en 2006 argumentó en base a la teoría M que es discreto, por lo que existiría una distancia mínima en el espacio de configuración entre cada par de vacíos que representan física diferente. Sin embargo, el problema de determinar si entre dos vacíos hay una distancia mínima es no decidible, en base a un teorema de Novikov que afirma que en más de 5 dimensiones es imposible decidir si dos variedades diferenciables son difeomorfas (“iguales” entre sí).
Cada posible vacío en el espacio de configuración corresponde a una compactificación (una variedad de Calabi-Yau) que está caracterizada por unos números llamados periodos. ¿Qué números reales pueden ser periodos de una variedad de Calabi-Yau? Un artículo de Yoshinaga ha demostrado que todos los periodos (reales) son números calculables en el sentido de Turing. ¿Se puede determinar si dos conjuntos de periodos corresponden a la misma variedad de Calabi-Yau, o sea, son equivalentes entre sí? Este problema, según el autor del artículo, tiene visos de ser computacionalmente intratable, aunque no hay resultados matemáticos concluyentes al respecto. En su caso, decidir computacionalmente cuál es el vacío correcto resultará prácticamente imposible.
En resumen, un artículo curioso que nos recuerda lo profundo de las matemáticas en la física moderna.
Conjecture: “Golden rule” of quantum-classic information. A gain in quantum algorithms is outweighed by losses in classical I/O and programing.
Los algoritmos cuánticos son sólo una parte de los ordenadores cuánticos. Además se requiere la entrada de datos (preparación de los cubits en el estado adecuado), programar (construir) la secuencia de puertas cuánticas que ejecuta el algoritmo y la salida de datos (lectura del estado final de los cubits). Estos procesos, hoy en día, son clásicos y requieren un alto costo en tiempo. Lo que se gana por un lado, se pierde por otro. Kisil conjetura que teniendo en cuenta el tiempo total los computadores cuánticos nunca serán más eficientes que los clásicos. Quizás se equivoque, quizás no. Nos lo cuenta en Vladimir V. Kisil, “Computation and Dynamics: Classical and Quantum,” ArXiv, Submitted on 8 Sep 2009.
Kisil nos recuerda que toda implementación física del algoritmo de factorización de Peter Shor requiere que reensamblar un circuito cuántico cada vez que en la entrada del algoritmo se introduce un número (pseudo)aletario. El coste de este reensamblaje (programación en palabras de Kisil) debe ser incluido en el coste total y en la práctica es muy alto. Lo mismo nos recuerda para el algoritmo de Grover para la búsqueda de números que requiere múltiples repeticiones en cada una de las cuales se destruye el contenido de la base de datos (cuando se mide, el estado cuántico colapsa). El resultado es que reescribir la base de datos (volver a preparar su estado cuántico) múltiples veces, con un costo mucho mayor que la ventaja obtenida con el algoritmo cuántico.
¿Podrán ser superadas estas barreras algún día? ¿Se podrán construir ordenadores cuánticos que no requieren de la intervención constante de procesos clásicos para su ejecución? Kisil es pesimista al respecto, de ahí su conjetura. La Mula Francis, por el contrario, se encuentra entre los optimistas.
El estado actual del problema P versus NP se resume en que el problema sigue abierto. Aunque se han hecho grandes avances, no se atisba que una demostración vaya a ser obtenida en las próximas décadas. ¿Pueden los computadores cuánticos resolver los problemas NP completos en tiempo polinomial? Nadie lo sabe, pero la respuesta oficial es que parece que no pueden. El millón de dólares para quien demuestre que P≠NP seguirá generando intereses. ¿Qué pasaría si alguien demuestra que P=NP? Según los estatutos del Premio del Milenio, no recibirá ni un solo dólar, aunque sí fama mundial. Bueno, en serio, recibiría 5 millones de dólares ya que podría resolver el resto de los 7 problemas del Milenio en un tiempo razonable con un demostrador automático si las correspondientes demostraciones tienen, digamos, 100 páginas de longitud. Nos lo cuenta Lance Fortnow, “Review article. The Status of the P Versus NP Problem,” Communications of the ACM 52: 78-86, 2009 [versión gratis html]. Un resumen breve en la presentación PowerPoint de la reciente charla de Scott Aaronson del MIT en “Has There Been Progress on the P vs. NP Question?” (visto en su blog ”Barriers to snarky blogging,” Shtetl-Optimized, August 27th, 2009).
¿Qué es el problema P versus NP? Un algoritmo para resolver un problema es eficiente si su coste en tiempo es un polinomio dado en el tamaño de los datos de entrada. La clase de problemas para los que existen algoritmos que los resuelven de forma eficiente se denomina clase P (problemas resolubles en tiempo polinómico). Hay problemas para los que una posible solución se puede verificar en tiempo polinomial (hay un algoritmo en P que decide la validez de una solución). Este tipo de problemas se encuentran en la clase NP (problemas resolubles de forma no determinista en tiempo polinómico). El problema P versus NP trata de estudiar si es cierto o no que P=NP, es decir, que todo problema para el que se puede verificar eficientemente su solución es un problema para el que se puede calcular su solución de forma eficiente.
La clase de problemas NP completos (NP-c) es una clase de problemas que son equivalentes entre sí de tal manera que si alguien encuentra un algoritmo eficiente para uno de ellos, automáticamente obtiene una algoritmo eficiente para todos los demás problemas en NP-c, más aún, también lo será para todos los problemas en NP. Es decir, un algoritmo eficiente para un problema NP-c automáticamente implica que P=NP. Hoy en día se conocen cientos de problemas NP-c (y cientos de demostraciones falsas (“fake“) de que se encuentran en P).
La mayoría de los investigadores en informática teórica cree que P≠NP, pero desde 1972 múltiples intentos de demostrar esta conjetura han sido infructuosos. En el año 2000, uno de los problemas del milenio del Instituto Clay de Matemáticas donará un millón de dólares a quien demuestre que P≠NP, aunque ni un solo dólar a quien demuestre que P=NP. En un mundo donde P=NP muchos estarían contentos, habría algoritmos eficientes (“rápidos”) para muchos problemas, sin embargo, muchos otros estarían tristes, la criptografía (cifrado) de clave pública sería inútil (habría algoritmos que desvelarían las claves secretas “rápidamente”). La mayoría de los expertos en teoría de la complejidad creen que P≠NP y que su demostración sólo es cuestión de tiempo.
¿Cómo se puede demostrar que P≠NP? Se han estudiado muchísimos caminos prometedores en los que se ha llegado a un callejón sin salida. Se ha avanzado mucho, pero todavía no se ve la luz al final del camino. Por ejemplo, si alguien encontrara un algoritmo en NP capaz de simular todos los problemas en P, entonces se podría utilizar un argumento de diagonalización (similar al usado por Turing para el Problema de la Parada) para demostrar que P≠NP. Los avances más importantes en los últimos años vienen en la línea que utiliza la geometría algebraica y la computación con números reales. Más detalles en el artículo de Fortnow, que se lee fácil para cualquier informático.
¿Pueden los ordenadores cuánticos resolver problemas NP completos? Peter Shor demostró que el problema de factorizar números enteros en factores primos y el problema de calcular logaritmos discretos se pueden resolver en tiempo polinómico con un algoritmo cuántico. Sin embargo, nadie sabe si estos problemas se encuentran en NP-c. De hecho, los expertos creen que el trabajo de Shor apunta a una demostración de que no lo están. Más aún, los trabajos de Grover parecen indicar que los algoritmos cuánticos (salvo excepciones como el algoritmo de Shor) sólo pueden lograr un speed-up cuadrático.
Para acabar, ¿en qué se ha avanzado en el problema P versus NP las últimas décadas? Básicamente se han obtenido resultados particulares (algunos con demostraciones muy complicadas), que según los expertos deberán estar incluidos en cualquier demostración del resultado general. Estos resultados permiten saber rápidamente si cualquier nueva “demostración” es correcta o no sólo echándole un vistazo. Si no incluye estos resultados particulares, debe ser incorrecta y los expertos “pasan” de prestarle más atención. Según Scott Aaranson es como el problema de la gravedad cuántica, cualquier propuesta debe demostrar que incluye la mecánica cuántica y la gravedad de Einstein, si no lo hace, nadie creerá que es la respuesta correcta.
Un ordenador analógico es un sistema físico que resuelve un problema en su búsqueda de un estado de equilibrio, por ejemplo, los ordenadores de burbujas. Una solución supersaturada de acetato de sodio o hielo caliente (hot ice) también se comporta como un ordenador analógico masivamente paralelo durante el proceso de su cristalización en un entorno en el que se han introducido ciertos obstáculos. Se pueden implementar puertas lógicas (and/or), el cálculo de diagramas de Voronoi y resolver el problema del camino de longitud mínimo sin colisiones en un grafo. Lo bueno de los ordenadores analógicos es que resultan muy curiosos y se implementan fácilmente. Lo malo es que no son escalables y sólo pueden resolver problemas de pequeño tamaño. Para los interesados en la informática y la computación de lo curioso disfrutarán con el artículo de fácil lectura de Andrew Adamatzky, “Hot Ice Computer,” ArXiv, Submitted on 30 Aug 2009, y con los vídeos de su página web “Videos of experiments.”
La gran ventaja de los ordenadores de hielo caliente es que son baratos, fáciles de construir, requieren un número muy pequeño de recursos, son muy rápidos y capaces de resolver gran número de problemas prácticos. En el computador de hielo caliente se utiliza una solución supersaturada de acetato de sodio (tri)hidratado (CH3COONa-3H3O) colocadas en placas de petri y enfriadas a unos -5oC, cuya cristalización se induce mediante una serie de pivotes de aluminio. Los informáticos disfrutarán viendo cómo se implementan con este mecanismo físico puertas lógicas de tipo “y” (and) y “o” (or). ¿Cómo implementar puertas “no” (not)? A los que os leáis el artículo, os dejo que lo penséis.
PS (3 sep. 2009): Interesante lectura relacionada en ArXiv blog, “First Hot Ice Computer Created,” Wednesday, September 02, 2009.
La ley de Moore no está demostrada. Más aún, es indemostrable que “el número de transistores integrados en un chip se duplica cada 24 meses,” (en los 1970 cada 18 meses). Evidencia empírica, que algún dejará de ser válida. Una “ley” que no es una ley. Una ley indemostrable. La ley de Rock afirma que cada 4 años el coste de una fábrica de chips se duplica (luego algún día dejará de ser económicamente rentable). La ley de Wirth afirma que el software se ralentiza más deprisa de lo que acelera el hardware (por eso, para hacer lo mismo, cada día se necesita un ordenador más potente); algunos la llaman ley de Page. La ley de Machrone afirma que el próximo ordenador personal que querrás comprarte siempre tiene el mismo precio, unos 1000 euros (ahora parece que habrá que bajarlo a 500 euros). La ley de Metcalfe afirma que el valor económico de una red crece con el cuadrado del número de usuarios (a más usuarios, más beneficios). Leyes que no son leyes, sólo evidencia empírica; leyes que algún día dejarán de ser válidas. Nos cuenta las 5 leyes de la informática Philip E. Ross, “5 Commandments. The rules engineers live by weren’t always set in stone,” IEEE Spectrum, December 2003. En inglés a este tipo de leyes les llaman “rule-of-thumb” algo que podríamos traducir al español como “la cuenta de la vieja.” Reglas (elevadas a “leyes”) que nos permiten estimar cosas.
¿Matará la ley de Rock a la ley de Moore? Sí, según Jack Schofield, que afirma en ”When the chips are down,” The Guardian, 29 July 2009, que la economía y no la física (ingeniería) parará la ley de Moore, aludiendo a la ley de Rock. Un ejemplo, Intel se está gastando (ha presupuestado) 7000 millones de dólares para la mejora (upgrade) de sus 7 plantas de fabricación de chips en EEUU. Global Foundries (chips AMD) ha empezado a construir una planta en Saratoga en el Estado de New York, por 4200 millones de dólares que empezará a funcionar en 2012.
Intel ha pasado de fabricar chips con transistores cuyo canal tenía 3000 nm. (3 micrómetros) a finales de los 1970, hasta los actuales 45 nm., con un objetivo a corto plazo en los 22 nm. Algunos proclaman que el límite teórico son los 18 nm., que se alcanzarán en 2014. Leo Jelinek, analista jefe la fábrica de semiconductores iSuppli afirma que la barrera de 18 nm. no es física en 2014 no es física sino económica: será demasiado caro fabricar chips más integrados.
Si el canal de los transistores no puede ser más pequeña, la única manera de fabricar chips con más transistores es hacer las obleas (y los chips) más grandes. La tecnología actual utiliza obleas de 30 cm. y se espera que para 2017 ya haya obleas de 45 cm. Otra posibilidad es hacer chips en 3D (tres dimensiones).
Obviamente, el futuro es impredecible. Yo recuerdo que tuve que aprender (cuando estudiaba en 1990) que el límite teórico (según la física) eran los 200 nm. (0,2 micrómetros).
La interpretación de los datos experimentales de los detectores de ondas gravitatorias como LIGO, Virgo y LISA requiere un uso intensivo de métodos numéricos en relatividad general. El proyecto NINJA (Numerical INJection Analysis) tiene por objeto desarrollar dichas técnicas que dependen fuertemente del detector considerado. Se acaba de publicar su primer artículo en Classical and Quantum Gravity. Utilizando datos experimentales de ondas gravitatorias simuladas numéricamente por 10 grupos de investigación de todo el mundo, aunque sin incluir ruido en los datos, el artículo demuestra que los algoritmos están a punto y podrán conducir a la detección de ondas gravitatorias. ¿Serán suficientemente sensibles LIGO o Virgo para detectarlas? Los autores del artículo no se mojan y no quieren ofrecer conclusiones al respecto, pero lo que está claro es que si el ruido no degrada los resultados obtenidos por los algoritmos, sí serán capaces de lograrlo. Un primer trabajo alentador que será el punto de partida de futuros estudios que incluyan errores y ruido no gaussiano. Laura Cadonati et al. “Status of NINJA: the Numerical INJection Analysis project,” Class. Quantum Grav. 26: 114008, 2009 [ArXiv preprint].
La red mundial de detectores de ondas gravitatorias basadas en interferometría incluye los 3 detectores LIGO en EEUU, Virgo en Italia, TAMA en Japón, y GEO600 en Alemania. Junto a estos avances experimentales, se ha avanzado mucho en el desarrollo de códigos de relatividad numérica para la simulación de las ondas gravitatorias generados por fenómenos violentos en el universo, como la coalescencia de dos agujeros negros (Binary Black Hole, BBH) coalescences. El objetivo del proyecto NINJA es unir ambos mundos, experimento y simulación numérica, para facilitar la interpretación, siempre difícil de las señales que ofrezcan las instalaciones experimentales actualmente en en uso y las que se desarrollarán en los próximos años (como LISA). Con anterioridad al proyecto NINJA, se utilizaban simulaciones postnewtonianas, sólo válidas cuando dos agujeros negros en colisión están suficientemente alejados. El proyecto NINJA se inició en la primavera de 2008 estando formado por 10 grupos de relatividad numérica y 9 grupos de análisis de datos, con un total de 76 investigadores y 30 instituciones científicas.
necesario para cambiar el estado cuántico de un sistema está acotado por 
donde 
, 
es el hamiltoniano del sistema y 
su función de onda. Por otro lado, una desigualdad obtenida por Margolus y uno de los autores, Levitin, en 1998, dada por 
donde 
es la energía media del sistema cuántico (supuesto que el estado de menor energía tiene asignado un valor cero). Levitin y Toffoli en el nuevo artículo generalizan ambas desigualdades demostrando que
,
. Esta desigualdad generaliza las dos anteriores de una forma aparentemente trivial, pero requiere un análisis cuidadoso. Para 
las dos desigualdades anteriores coinciden entre sí. Para 
han demostrado que para todo 
existe una familia de estados 
tales que 
, y que para 
existe una familia de estados 
. Esto completa el círculo y muestra que la nueva desigualdad comprende a los dos anteriores como casos particulares y las unifica.
