100 años de la Teoría de la Relatividad Especial

Hoy se cumplen 100 años desde que Albert Einstein publicó su artículo titulado "Sobre la Electrodinámica de los Cuerpos Móviles"[1] en cual define la Teoría de la Relatividad Especial. Feliz cumple, teoría ;)

Links interesantes:
* Explicación de la Relatividad Especial en la Wikipedia
* Traducción al inglés del paper original

Referencias:
[1] A. Einstein, "Zur Elektrodynamik bewegter Körper", Annalen der Physik. 17:891-921. (30 de Junio de 1905).

Algoritmo de Shor y Algoritmo de "de Vries"

En un nuevo paper de Andreas de Vries[1], parece ser que el algoritmo que plantea es capaz de realizar una búsqueda en una base de datos desordenada en un órden O(log n). Esto implica que NP está dentro de BQP, o sea: los problemas NP completos son resolubles en tiempo polinomial en una computadora cuántica.

Si esto es correcto, este nuevo algoritmo hace obsoleto el algoritmo de Grover y es, junto al algoritmo de Shor, uno de los más importantes algoritmos cuánticos.

Aún debo leerlo más "sesudamente", luego comentaré mis impresiones.

Update: Estaba leyendo el paper y encontré hasta ahora un error en la ecuación (9) donde dice que C²=C-I, esto no es cierto, pero igualmente, antes de terminar de leerlo encontré este post en el Weblog de Dave Bacon que ya lo estudió a fondo y encontró otros errores más. El paper fue enviado a la Physical Review D, así que será cuestión de tiempo de esperar a que lo refereen y de Vries corrija los errores, asimismo creo que la afirmación de que NP C BQP no se podrá demostrar a partir de este algoritmo.

Update++: En palabras del mismo Andreas, el problema más severo en su paper está en el Ejemplo 5, en el cual dice que su algoritmo es más rápido que el de Grover, y esto no es cierto, ya que para el caso especial de N=4 (el que él analiza) el algoritmo de Grover requiere una sóla consulta al oráculo, no 2 como dice él, y en ese caso su algoritmo se comporta exactamente igual, por lo tanto el algoritmo de Grover sigue siendo "óptimo".

[1] A. de Vries, Fast quantum search algorithms by qubit comparisons exploiting global phase interference, arXiv:quant-ph/0506137.

Niveles de abstracción

Veamos, el desarrollo lógico de la computación cuántica, al igual que la computación clásica, debería ir llevando a crear nuevos niveles de abstracción. Hasta ahora existen:
nivel 0 de abstracción: Física cuántica
nivel 1 de asbtracción: Computación cuántica en base a compuertas lógico-cuánticas
nivel 2 de abstracción: Aritmética computacional cuántica
nivel 3 de abstracción (¿o 1.5?): Lambda Cálculo para computación cuántica

Ya sería hora de crear un nuevo nivel, "lenguajes de programación cuánticos" ¿qué permitiría esto? si bien no se van a poder implementar "compiladores" cuánticos todavía (ya que no existen aún máquinas cuánticas que manejen un número de qubits interesantes), se puede llegar a simplificar bastante el escribir algoritmos cuánticos si disponemos de un lenguaje para esto. El único problema es que todos los "niveles" mencionados siguen desarrollándose constantemente, por lo tanto se necesitaría un lenguaje lo suficientemente potente como para poder ir cambiándolo facilmente de acuerdo a los nuevos descubrimientos en niveles inferiores.

Se invita a todos a dejar sus comentarios ;)

PD: si quieren saber un poco más de qué es la computación cuántica, lean el post anterior "Charlas Introductorias a la Computación Cuántica"

Charlas Introductorias a la Computación Cuántica

Terminaron las charlas, quería agradecer a Federico Bergero, Mariano Salvetti y Rafael Namías por la ayuda en la organización (y por haber sido los que propusieron el curso), a Guido Macchi, Claudio Gazza y Ariel Dobry por todo el apoyo y a Lucas Minuto por ser el conejito de indias escuchando cada charla antes de que la dicte.

Se puede bajar los apuntes completos de las charlas desde eXactas.org haciendo click acá.
Nuevo link (eXactas no existe más).

Mi primer Paper

Aún no está publicado, pero ya lo he enviado para su publicación, se puede ver el preprint desde la base de datos de Los Alamos[1].

En este paper, titulado "On the Teleportation of N-qubit States", lo que hago es una generalización del algoritmo cuántico de teleportación creado por Brassard[2] (basado en la teleportación descripta por Bennett et al.[3]) y además hago una generalización de los dos protocolos de teleportación que planteó Kak[4] (los cuales con tan sólo n bits de información clásica completan la teleportación, en contraste de los 2n bits necesitados en el protocolo de Bennett).
El único problema con los protocolos de Kak es que se necesita preparar el estado que se llevará "Bob" junto con el estado que se va a teleportar (por lo tanto no tiene mucho sentido, ya que en ese caso, sería más lógico que Bob se llevase directamente el estado que quiere obtener), igualmente a nivel teórico los protocolos de Kak, son interesantes.

Referencias
[1] A. Díaz-Caro, arXiv:quant-ph/0505009 (2005)
[2] G. Brassard, Physica D 120, 43 (1998)
[3] C. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres y W. Wootters, Phys. Rev. Lett. 70, 1895 (1993).
[4] S. Kak, arXiv:quant-ph/0305085 (2003)