 |
| Búsqueda de la solución correcta. Imagen tomada por Lynne Hand. |
Esta semana el tema que escogido es la computación cuántica. Este es un tema complicado, por lo que el objetivo de esta entrada es otorgar una visión intuitiva del proceso y las posibilidades que éste abre a la computación. Para ello es necesario introducir ciertas nociones acerca de los sistemas cuánticos. Como esto es Internet, reino de los gatos, el ejemplo con el que comenzamos es el experimento mental llevado a cabo por Erwin Schrödinger en 1935. Sí señores, vamos a hablar del gato de Schrödinger.
Como este experimento ha sido explicado hasta la saciedad en distintos blogs, intentaré ser breve. Imaginemos que se dispone de una caja, en la cual se ha depositado un gato. Además se ha incluido un emisor de partículas alfa con su correspondiente detector, un martillo y un frasco de veneno. El proceso es el siguiente: cuando se detecta una partícula, el detector libera el martillo que golpea el frasco de veneno, lo cual libera su contenido, matando al animal. No obstante, hay que tener en cuenta los siguientes puntos:
- El gato no puede interferir en la emisión de las partículas, ni impedir que si se detecta alguna, la botella se rompa.
- La caja se encuentra completamente aislada del mundo exterior. No es posible saber lo que está sucediendo o lo que ha sucedido sin abrirla.
- El emisor de partículas en cada instante de tiempo puede, con la misma probabilidad, tanto emitir una partícula como no hacerlo.
El problema planteado es saber, sin mirar el interior de la caja, si el gato está vivo o muerto. Unos podrían pensar que el gato se encuentra vivo, porque el emisor no ha desencadenado la rotura del frasco de veneno. Pero es igualmente válido pensar lo contrario, que se encuentra muerto, ya que la probabilidad de que el veneno se derrame es idéntica a que permanezca intacto. Está claro que al ser incapaces de abrir la caja no podemos afirmar con certeza cual es el estado del gato. De manera algo más formal, el estado del gato puede verse en términos de la siguiente expresión:
Básicamente la expresión quiere decir que el gato está vivo con una probabilidad de un medio y muerto con la misma probabilidad. El estado final del gato es una superposición, con la misma probabilidad, de dos sucesos mutuamente excluyentes. Entonces, ¿significa ésto que el gato está vivo y muerto a la vez?
Un gato no puede estar vivo y muerto a la vez, por lo que existen varias interpretaciones a este fenómeno. Una de ellas (la interpretación de Copenhague de la mecánica cuántica) afirma que lo sucedido es fruto de la incapacidad de determinar en cual de los dos estados se encuentra el gato, sin realizar una observación del sistema, que en este caso, consiste en abrir la caja. Conocemos bien las condiciones iniciales, pero conforme el tiempo pasa sólo disponemos de probabilidades. Aún así, cuando abrimos la caja, el estado de la expresión (1) se colapsa a uno de los dos posibles: vivo o muerto, con la probabilidad correspondiente. Que quede claro, el gato no está vivo o muerto a la vez, es la incapacidad de conocer el estado real del sistema la que nos obliga a emplear probabilidades. Lo mismo sucede cuando manipulamos sistemas en los que intervienen partículas subatómicas, como si de una caja se tratara, no podemos conocer a ciencia cierta lo que está pasando hasta que tomamos la decisión de echar un vistazo al resultado.
Por ahora se ha visto que un sistema cuántico tiene un estado interno el cual no está completamente determinado y un estado observado, el cual se aprecia tras efectuar la medida correspondiente. Olvidémonos un rato del gato y asumamos que tenemos dos estados abstractos, 0 y 1. Realmente no importa el nombre, la clave es que sean mutuamente excluyentes. El significado de cada uno de los valores se deja a la imaginación del lector, puede significar vivo o muerto, encendido o apagado, verdadero o falso, etc.
Mediante dos estados claramente diferenciados, es posible almacenar un bit de información. Este sistema constituye el pilar de la teoría de la información en la computación clásica, por ello los ordenadores convencionales manejan bits, que pueden tomar valores de 0 o 1. Por el contrario, en la computación cuántica disponemos de otra unidad de información, el qubit, que se corresponde con un sistema cuántico regido por la siguiente expresión:
)
Hay una enorme similaridad estructural con la expresión que determinaba el estado del gato, de hecho sólo cambia el nombre de los estados (vivo ha pasado a llamarse cero y muerto ha pasado a llamarse uno), además de que los pesos pueden tomar cualquier valor. De hecho, el sistema cuántico del gato de Schrödinger sólo necesita un qubit para ser representado. La potencia de la expresión anterior viene de que un qubit puede encontrarse en una superposición continua. Entendemos por superposición a que los valores que puede tomar son una combinación de las posibles situaciones. Esta combinación también viene determinada por los valores que toman alfa y beta, que determinan la probabilidad del resultado de la medición. Es decir, si alfa toma un valor de 0.9 y beta de 0.1, al realizar la medición del sistema, 9 de cada 10 veces el resultado será cero y 1 de cada 10, será 1.
El primer reto que debe superar la computación cuántica es cómo operar con sus unidades básicas de información. En la computación clásica, las operaciones elementales son aquellas que provienen de la lógica, por lo general, un 1 representa cierto y un 0 representa falso, por lo que puede calcularse la conjunción de dos bits (a Y b), la disyunción (a O b) y la negación (NO a). En principio, con esas tres operaciones puede construirse cualquiera más compleja. Por eso se dice que esas tres operaciones, y su implementación física, son universales. Ahora bien, en el mundo cuántico un qubit puede contener información acerca de los dos estados simultáneamente, por lo que existen operaciones más complejas que aprovechen esta naturaleza. Por lo tanto, los algoritmos cuánticos deben aprovechar que un qubit puede estar tanto en el 0 como en el 1 para realizar cálculos en paralelo. Este tipo de paralelismo se basa en que mientras, por así decirlo, no "miremos" el estado, la información puede estar repartida en varios sitios a la vez. Un algoritmo que maneje un qubit podrá manejar dos valores en paralelo, pero si es de dos qubits el número se duplica, pasando a ser cuatro. En general, se incrementa el número de qubits en una unidad, las posibilidades se ven duplicadas. Esto incrementa el grado de paralelismo hasta niveles inimaginables por los computadores tradicionales. Eso si, al igual que cuando abríamos la caja del gato la magia desaparecía y conocíamos la salud del gato, aquí sucede lo mismo, por lo que las operaciones a realizar deben realizarse sin realizar observaciones sobre el estado.
Ahora bien, realmente no sabemos qué es un qubit. En principio, es posible afirmar que son un concepto matemático, al igual que sucede los bits clásicos. Mientras que estos últimos se llevan a la práctica mediante transistores (en la mayoría de los casos), en el caso de un qubit no se ha encontrado todavía una implementación física definitiva. En algunos casos se representan mediante el spin de un electrón, del núcleo atómico o incluso la polarización de un fotón. En cualquier caso, las magnitudes anteriores tienen dos valores definidos y mutuamente excluyentes pero su naturaleza cuántica (estamos al nivel de fotones y electrones) permiten una superposición de ambos estados, lo cual se corresponde con la idea matemática de un qubit.
Ahora bien, si esta implementación física de los qubits fuera tan sencilla, ya dispondríamos de ordenadores cuánticos comerciales, pero todavía existen muchos problemas que afrontar. Uno de los más importantes es el fenómeno conocido como decoherencia. Por así decirlo, el estado del sistema se filtra al entorno que le rodea, por lo que para evitar que las computaciones se desmoronen es necesario aislar completamente el sistema, o al menos hacer que éstas se realicen lo suficientemente rápido. Veamos qué papel juega la decoherencia en la computación
Idealmente la computación cuántica seguiría el proceso siguiente. En primer lugar se traduce la información clásica a qubits. Esto es posible porque un bit es un caso particular de qubit, en el que alguno de los coeficientes, ya sea alfa o beta, vale cero. A lo largo del computador se procesa la información. Mediante una serie de transformaciones, el estado cuántico se modifica, lo cual puede verse en un cambio de valores en los parámetros alfa y beta, por lo que aprovechan la naturaleza cuántica. Finalmente se realiza el proceso de observación, lo cual colapsa el estado cuántico en uno de sus posibles valores. Es vital mencionar que el procesamiento dentro del computador es completamente determinista. Existe una regla de evolución que dicta claramente como cambian los pesos de los distintos estados, mientras que el no determinismo surge al realizar la observación. Es por lo que los algoritmos diseñados para ejecutarse en un computador cuántico deben obtener una cierta probabilidad de obtener el resultado correcto, es decir de todos los posibles resultados que conforman el estado superpuesto, aquel que es correcto debe ser el que más probabilidad tenga antes de colapsar el estado.
El problema es que durante la computación, parte de la información del estado cuántico se intercambia con el entorno, es decir, la decoherencia echa a perder los resultados. En cierto modo un computador cuántico trabaja como un operario ciego en una cadena de montaje. Sabe perfectamente qué tiene que hacer, pero es incapaz de ver el resultado de sus acciones, además de que el resto del entorno debe de desconocer también qué es lo que se está haciendo. Para mitigar este fenómeno, (el problema no se encuentra ni mucho menos resuelto) no es de extrañar que el computador cuántico puesto a la venta por la empresa canadiense D-Wave se encuentre dentro de un armazón criogénico de 10 metros cuadrados y valga 10 millones de dólares. Serious Business.
Finalmente merece la pena comentar en qué situaciones se han encontrado algoritmos cuánticos que ofrecen (en teoría) mejores prestaciones que los clásicos. La primera de ellas, aunque parezca la más evidente, es la posibilidad de simular sistemas cuánticos. Actualmente simular la evolución de un sistema de este tipo es enormemente costosa, tanto en términos de tiempo como de memoria. Por el contrario, un computador cuántico es capaz de simular procesos cuánticos, ya que realiza las computaciones en los mismos términos que el sistema que simula. Otra aplicación vital es la descomposición de números en el producto de sus factores primos. De hecho, esta es la aplicación más notable, ya que llevada a la práctica destrozaría los procesos de cifrado que empleamos a diario. Nos recuperaríamos, pero habría que cambiar bastantes cosas. Curiosamente el año pasado se consiguió descomponer el número 15 en sus factores primos, 3 y 5. El experimento se repitió casi 150.000 veces y consiguió acertar el 48 % de las veces. Parece ridículo, pero es un comienzo.
Además de los dos casos anteriores, existen numerosos algoritmos cuánticos en distintos dominios, como pueden ser búsquedas en bases de datos, bioinformática, etc. Desgraciadamente, la mayoría de los logros han sido conseguidos en el ámbito teórico, siendo aún pocas las aplicaciones prácticas. De todas maneras, al igual que los computadores clásicos nos han ayudado a entender la mecánica clásica, sus homólogos cuánticos pueden constituir una valiosa guía para comprender cómo funciona la mecánica cuántica, la cual es un dominio bastante incierto. Realmente, mi opinión sobre el tema es que debido a la naturaleza probabilista de la mecánica cuántica, no creo que este nuevo paradigma reemplace al actual, sino que será empleado en aquellos dominios donde la computación tradicional no rinda lo suficiente.
Por ahora se ha visto que un sistema cuántico tiene un estado interno el cual no está completamente determinado y un estado observado, el cual se aprecia tras efectuar la medida correspondiente. Olvidémonos un rato del gato y asumamos que tenemos dos estados abstractos, 0 y 1. Realmente no importa el nombre, la clave es que sean mutuamente excluyentes. El significado de cada uno de los valores se deja a la imaginación del lector, puede significar vivo o muerto, encendido o apagado, verdadero o falso, etc.
Mediante dos estados claramente diferenciados, es posible almacenar un bit de información. Este sistema constituye el pilar de la teoría de la información en la computación clásica, por ello los ordenadores convencionales manejan bits, que pueden tomar valores de 0 o 1. Por el contrario, en la computación cuántica disponemos de otra unidad de información, el qubit, que se corresponde con un sistema cuántico regido por la siguiente expresión:
Hay una enorme similaridad estructural con la expresión que determinaba el estado del gato, de hecho sólo cambia el nombre de los estados (vivo ha pasado a llamarse cero y muerto ha pasado a llamarse uno), además de que los pesos pueden tomar cualquier valor. De hecho, el sistema cuántico del gato de Schrödinger sólo necesita un qubit para ser representado. La potencia de la expresión anterior viene de que un qubit puede encontrarse en una superposición continua. Entendemos por superposición a que los valores que puede tomar son una combinación de las posibles situaciones. Esta combinación también viene determinada por los valores que toman alfa y beta, que determinan la probabilidad del resultado de la medición. Es decir, si alfa toma un valor de 0.9 y beta de 0.1, al realizar la medición del sistema, 9 de cada 10 veces el resultado será cero y 1 de cada 10, será 1.
El primer reto que debe superar la computación cuántica es cómo operar con sus unidades básicas de información. En la computación clásica, las operaciones elementales son aquellas que provienen de la lógica, por lo general, un 1 representa cierto y un 0 representa falso, por lo que puede calcularse la conjunción de dos bits (a Y b), la disyunción (a O b) y la negación (NO a). En principio, con esas tres operaciones puede construirse cualquiera más compleja. Por eso se dice que esas tres operaciones, y su implementación física, son universales. Ahora bien, en el mundo cuántico un qubit puede contener información acerca de los dos estados simultáneamente, por lo que existen operaciones más complejas que aprovechen esta naturaleza. Por lo tanto, los algoritmos cuánticos deben aprovechar que un qubit puede estar tanto en el 0 como en el 1 para realizar cálculos en paralelo. Este tipo de paralelismo se basa en que mientras, por así decirlo, no "miremos" el estado, la información puede estar repartida en varios sitios a la vez. Un algoritmo que maneje un qubit podrá manejar dos valores en paralelo, pero si es de dos qubits el número se duplica, pasando a ser cuatro. En general, se incrementa el número de qubits en una unidad, las posibilidades se ven duplicadas. Esto incrementa el grado de paralelismo hasta niveles inimaginables por los computadores tradicionales. Eso si, al igual que cuando abríamos la caja del gato la magia desaparecía y conocíamos la salud del gato, aquí sucede lo mismo, por lo que las operaciones a realizar deben realizarse sin realizar observaciones sobre el estado.
Ahora bien, realmente no sabemos qué es un qubit. En principio, es posible afirmar que son un concepto matemático, al igual que sucede los bits clásicos. Mientras que estos últimos se llevan a la práctica mediante transistores (en la mayoría de los casos), en el caso de un qubit no se ha encontrado todavía una implementación física definitiva. En algunos casos se representan mediante el spin de un electrón, del núcleo atómico o incluso la polarización de un fotón. En cualquier caso, las magnitudes anteriores tienen dos valores definidos y mutuamente excluyentes pero su naturaleza cuántica (estamos al nivel de fotones y electrones) permiten una superposición de ambos estados, lo cual se corresponde con la idea matemática de un qubit.
Ahora bien, si esta implementación física de los qubits fuera tan sencilla, ya dispondríamos de ordenadores cuánticos comerciales, pero todavía existen muchos problemas que afrontar. Uno de los más importantes es el fenómeno conocido como decoherencia. Por así decirlo, el estado del sistema se filtra al entorno que le rodea, por lo que para evitar que las computaciones se desmoronen es necesario aislar completamente el sistema, o al menos hacer que éstas se realicen lo suficientemente rápido. Veamos qué papel juega la decoherencia en la computación
Idealmente la computación cuántica seguiría el proceso siguiente. En primer lugar se traduce la información clásica a qubits. Esto es posible porque un bit es un caso particular de qubit, en el que alguno de los coeficientes, ya sea alfa o beta, vale cero. A lo largo del computador se procesa la información. Mediante una serie de transformaciones, el estado cuántico se modifica, lo cual puede verse en un cambio de valores en los parámetros alfa y beta, por lo que aprovechan la naturaleza cuántica. Finalmente se realiza el proceso de observación, lo cual colapsa el estado cuántico en uno de sus posibles valores. Es vital mencionar que el procesamiento dentro del computador es completamente determinista. Existe una regla de evolución que dicta claramente como cambian los pesos de los distintos estados, mientras que el no determinismo surge al realizar la observación. Es por lo que los algoritmos diseñados para ejecutarse en un computador cuántico deben obtener una cierta probabilidad de obtener el resultado correcto, es decir de todos los posibles resultados que conforman el estado superpuesto, aquel que es correcto debe ser el que más probabilidad tenga antes de colapsar el estado.
El problema es que durante la computación, parte de la información del estado cuántico se intercambia con el entorno, es decir, la decoherencia echa a perder los resultados. En cierto modo un computador cuántico trabaja como un operario ciego en una cadena de montaje. Sabe perfectamente qué tiene que hacer, pero es incapaz de ver el resultado de sus acciones, además de que el resto del entorno debe de desconocer también qué es lo que se está haciendo. Para mitigar este fenómeno, (el problema no se encuentra ni mucho menos resuelto) no es de extrañar que el computador cuántico puesto a la venta por la empresa canadiense D-Wave se encuentre dentro de un armazón criogénico de 10 metros cuadrados y valga 10 millones de dólares. Serious Business.
Finalmente merece la pena comentar en qué situaciones se han encontrado algoritmos cuánticos que ofrecen (en teoría) mejores prestaciones que los clásicos. La primera de ellas, aunque parezca la más evidente, es la posibilidad de simular sistemas cuánticos. Actualmente simular la evolución de un sistema de este tipo es enormemente costosa, tanto en términos de tiempo como de memoria. Por el contrario, un computador cuántico es capaz de simular procesos cuánticos, ya que realiza las computaciones en los mismos términos que el sistema que simula. Otra aplicación vital es la descomposición de números en el producto de sus factores primos. De hecho, esta es la aplicación más notable, ya que llevada a la práctica destrozaría los procesos de cifrado que empleamos a diario. Nos recuperaríamos, pero habría que cambiar bastantes cosas. Curiosamente el año pasado se consiguió descomponer el número 15 en sus factores primos, 3 y 5. El experimento se repitió casi 150.000 veces y consiguió acertar el 48 % de las veces. Parece ridículo, pero es un comienzo.
Además de los dos casos anteriores, existen numerosos algoritmos cuánticos en distintos dominios, como pueden ser búsquedas en bases de datos, bioinformática, etc. Desgraciadamente, la mayoría de los logros han sido conseguidos en el ámbito teórico, siendo aún pocas las aplicaciones prácticas. De todas maneras, al igual que los computadores clásicos nos han ayudado a entender la mecánica clásica, sus homólogos cuánticos pueden constituir una valiosa guía para comprender cómo funciona la mecánica cuántica, la cual es un dominio bastante incierto. Realmente, mi opinión sobre el tema es que debido a la naturaleza probabilista de la mecánica cuántica, no creo que este nuevo paradigma reemplace al actual, sino que será empleado en aquellos dominios donde la computación tradicional no rinda lo suficiente.
Si quieres saber más
Una clase íntegra de introducción a la computación cuántica, impartida por el Instituto de Computación Cuántica (Institute for Quantum Computing, IQC) de la Universidad de Waterloo en Canada. Lleva matemáticas de las chulas, avisados estáis.
http://bit.ly/XcYdX8
Wikipedia muestra las distintas interpretaciones del resultado del experimento mental de Schrödinger. Puede consultarse en el siguiente enlace:
Pepe "Puertas de Acero" Pérez
El libro "An Introduction to Quantum Computing" por los autores Philip Kaye, Raymond LaFlamen y Michele Mosca. Es un libro serio, de hecho, el que imparte la clase anterior es uno de los autores.
Wikipedia muestra las distintas interpretaciones del resultado del experimento mental de Schrödinger. Puede consultarse en el siguiente enlace:
Un video de TED que introduce bastante bien la barrera a la que se enfrenta la industria del hardware y como la computación cuántica puede superarla.
http://youtu.be/cugu4iW4W54
En este vídeo, un señor británico de dudosa dicción da un breve repaso sobre cómo representar los qubits, sus problemas y las aplicaciones que este modelo de computación puede aportar a la humanidad
Pepe "Puertas de Acero" Pérez
No hay comentarios:
Publicar un comentario