miércoles, 22 de junio de 2011

Computación Cuántica (Teoría y algoritmos)

Como no podría ser de otra manera en un blog de un físico cuántico tenemos que hablar del tema estrella (o uno de ellos) de este campo. La cuestión es en principio sencilla, ya hemos hablado anteriormente sobre los efectos tan raros que se producen en el mundo cuántico (véase la coherencia y el entanglement), ahora la pregunta es natural ¿para qué sirve todo esto? 

Una de las aplicaciones más investigadas actualmente es sin duda la computación cuántica. Básicamente se trata en usar las propiedades cuánticas, como las dos citadas antes, para fabricar ordenadores que puedan hacer operaciones que los ordenadores actuales no puedan. Pero mejor vayamos paso por paso.


¿Cuál es el problema original?

La idea de construir un ordenador cuántico es bastante anterior a que se descubriera su potencial matemático. Viene de un problema con el que los físicos cuánticos nos encontramos a diario: La dificultad de estudiar sistemas cuánticos en un ordenador. Vamos a ver de donde proviene esta dificultad.

Imaginad que tenéis un sistema clásico normal, compuesto por un montón de monedas que pueden estar en "cara" o "cruz". Imaginaos que tenéis por ejemplo, un millón de monedas. Si queréis especificar en que estado se encuentra el sistema ¿qué necesitáis? La respuesta es sencilla, un millón de números "0" ó "1". Si en vez de tener monedas que sólo tienen dos posibilidades, tenéis algo más complejo, por ejemplo un millón de canicas, que tienen su posición y su velocidad cada una de ellas, ¿qué necesitáis? Pues también es simple, necesitáis un millón de números reales para la velocidad y otro millón para la posición.

Básicamente hay que quedarse con esto: En sistemas clásicos necesitas tantos datos como partículas tiene el sistema.


Esto es una limitación, no cabe duda, pero gracias a los ordenadores de hoy en día podemos hacer cuentas con decenas de miles de partículas. ¿Qué ocurre entonces en el caso cuántico?

En un problema de física cuántica la cosa es bastante más complicada. Como ya expliqué en el post sobre la coherencia las monedas cuánticas pueden estar en sus dos estados $\left|cara\right>$ y $\left|cruz\right>$ al mismo tiempo. Esto significa que para dar el estado de una "moneda cuántica" tendré que dar que parte está en cara y cual en cruz, lo que son dos números. ¿Es esto un problema? os preguntaréis sin duda, pues para una moneda no, en absoluto, el problema es cuando vamos incrementando la cosa. Si tenemos dos monedas ahora tenemos 4 posibilidades $\left|cara-cara\right>$, $\left|cara-cruz\right>$, $\left|cruz-cara\right>$ y $\left|cruz-cruz\right>$, hala 4 números que hay que guardar. ¿Y si seguimos aumentando? Si seguimos así veremos muy pronto que para $N$ monedas necesitamos $2^N$ números. Esto puede parecer poco, pero es una barbaridad en cuanto N aumenta un poco. Para muestra un botón, si tenemos 20 partículas tendremos que almacenar algo más de un millón de números y para 30 partículas más de un billón.

La conclusión es simple: En sistemas cuánticos necesitas $2^N$ datos, donde N es el número de partículas que tiene el sistema.

Imagino que empatizaréis ahora con los pobres físicos cuánticos. Nuestros compañeros "clásicos" hacen sus simulaciones de sistemas con un millón de partículas y nosotros rara vez pasamos de 20 (en mi actual trabajo estamos con 10). Tened en cuenta, por ejemplo, que un átomo de Calcio ya tiene 20 electrones, y uno de Uranio 92, eso ya se escapa de nuestra capacidad de cálculo.

Los átomos molan mucho, pero estudiarlos de manera exacta no es posible con nuestros ordenadores.

¿Cómo solucionar semejante problema? La idea es sencilla y se suele atribuir a Richard Feynmann. Sabemos que los ordenadores clásicos no sirven para simular sistemas cuánticos (sirven pero son muy poco eficientes), pero los sistemas cuánticos existen en la naturaleza, por lo que la naturaleza en si puede simular sistemas cuánticos. La solución será crear ordenadores que funcionen en base a la física cuántica, y estos sí podrán simular eficientemente un sistema cuántico.


Richard Feynmann

Por último mencionar que aunque este es el problema principal que los ordenadores cuánticos solucionarían, en la última década han aparecido muchas aplicaciones alejadas de la física. De eso hablamos un poco más abajo.


Del bit al qubit

Veamos entonces cual es la diferencia entre un ordenador normal, que a partir de ahora llamaremos "ordenador clásico", y un ordenador cuántico.

Como todos sabemos los ordenadores clásicos trabajan con unidades básicas de información, llamadas bits. Estos bits básicamente representan algo que puede tener dos valores, "cero" o "uno", por ejemplo. Los ordenadores cuánticos son más raros y su unidad fundamental no es el bit, sino el quantum bit o qubit, para abreviar.

La diferencia entre los bits y los qubits es clara, los bits sólo pueden estar en "0" ó "1" mientras que los qubits barren cualquier posibilidad. Eso se representa muy bien median la esfera de Bloch. En esta representación los polos de la esfera representan los bits clásicos "0" y "1" y todos los demás puntos son las distintas posibilidades que puede tomar un qubit. Está muy claro que los qubits tienen infinitas posibilidades mientras que los bits sólo dos.


La esfera de Bloch


Otras aplicaciones de los ordenadores cuánticos

Como ya he mencionado anteriormente el interés por los ordenadores cuánticos no es simplemente por cuestiones de física cuántica. En los últimos años se les anda buscando todo tipo de aplicaciones, pero sin duda las más conocidas son las siguientes.

- Buscar un elemento en una base de datos (algoritmo de Grover):

Este es el famoso algoritmo de Grover [1], publicado en 1996. Este algoritmo sirve para buscar en una lista de números desordenada si un número está o no en la lista. Esto puede parecer una trivialidad, pero si tienes una lista enorme, por ejemplo los clientes de una multinacional, averiguar si un nuevo cliente está ya o no en la lista lleva bastante tiempo.

En un ordenador clásico hay poco donde mejorar, básicamente tienes que revisar todos los elementos uno por uno. Esto hace que el tiempo que uses sea proporcional al número de elementos de la lista, de modo que si duplicas el tamaño de la lista te llevará el doble de tiempo (obvio). Por suerte cuánticamente sí se puede mejorar. El algoritmo de Grover generalmente tarda un tiempo proporcional a la raíz cuadrada del tamaño de la lista, por lo que si doblas el tamaño de la lista sólo aumenta el tiempo en un factor $\sqrt{2}\sim 1.4$, esto por supuesto mejora más cuanto más grande es la lista.

Algoritmo de Grover, vía Wikipedia

- Factorizar números (algoritmo de Shor):

Esta es en mi opinión la aplicación estrella de los ordenadores cuánticos, ya que tiene unas aplicaciones muy relevantes. Básicamente el problema es el siguiente, imaginad que os doy dos números primos, por ejemplo 3 y 11, si os digo que lo multipliquéis no os llevará mucho tiempo. Ahora imaginad que en vez de eso os doy un número, por ejemplo 65, y os digo que es el producto de dos números primos, ¿me podéis decir cuáles son? Esto ya no es tan fácil. Este es el problema a resolver dado un número que es el producto de dos primos, averiguar cuales son.

Antes que nada muchos pensaréis que esto es un problema matemático sin mucha utilidad, pues os equivocáis y mucho. Este tipo de problemas es la base de la encriptación RSA, que basa su seguridad precisamente en que esta operación requiere mucho tiempo. Esto quiere decir que si alguien averigua como factorizar estos números rápidamente podrá acceder a datos de bancos, tarjetas de créditos y secretos gubernamentales por doquier. Ciertamente es muy importante.

Ahora la cuestión cuántica. Para resolver este problema en un ordenador cuántico está el famoso algoritmo de Shor. No mencionaré detalles, porque es bastante complicado, pero creedme si os digo que es mucho más rápido para números grandes. Podéis consultarlo en el enlace de la Wikipedia o en la referencia [3].

- Algoritmo de Deutsch-Jozsa:

El algoritmo de Deutsch-Jozsa tiene el honor de ser el algoritmo cuántico más antiguo. No resuelve un problema muy útil, pero es muy ilustrativo. Vamos a ello.

Problema: Tenemos una caja que al recibir un bit (0 ó 1) devuelve un bit (0 ó 1), pero no sabemos cual es la correspondencia entrada-salida. Sin embargo es fácil deducir que la caja

1. da la misma salida a las dos posibles entradas (caja constante) o
2. da diferentes salidas (caja balanceada).

El problema en cuestión es averiguar si la caja es constante o balanceada usándola el menor número de veces.

Clásicamente la cosa está clara, hay que usar la caja dos veces, introducir primero un 0, luego un 1 y ver si la salida es o no es la misma. Cuánticamente hay un método donde podemos averiguarlo con una sola llamada a la caja .

Conclusión

Hasta aquí este post introductorio sobre como son y para que sirven los ordenadores cuánticos. Creo que está bastante claro su potencial, tanto en facilitar la investigación de los físicos cuánticos, lo que dará mejoras en temas de física atómica, de materiales y un sinfín de aplicaciones más, como en cuestiones matemáticas. En el próximo post hablaré sobre los distintos intentos que hay para construirlos. Espero que os guste.


Referencias

[1] Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Revisión pedagógica del algoritmo de Grover.

[2] Shor, Peter W. (1997), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput. 26 (5): 1484–1509, arXiv:quant-ph/9508027v2

[3] Nielsen, Michael A. & Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press.

[4] David Deutsch and Richard Jozsa (1992). Rapid solutions of problems by quantum computation. Proceedings of the Royal Society of London A 439: 553. 

No hay comentarios:

Publicar un comentario en la entrada

Agradecemos mucho tu opinión, pero comentarios difamatorios, insultantes o con ánimo de ofender, trollear o spamear serán eliminados. Tampoco se aceptan comentarios anónimos.