Medición y confluencia en lambda cálculos cuánticos con qubits explícitos

Ayer llegué de Francia. Estuve 2 semanas en Grenoble y 2 semanas en Orsay.

En Grenoble estuvimos trabajando con Pablo Arrighi y Jonathan Grattage en extender mi tesis de grado de agregado de medición al Lambda Cálculo cuántico de van Tonder[1]. La idea fue extenderlo para probar confluencia y dejar el método lo suficientemente general para que pueda ser fácilmente usado para extender otros lambda cálculos (en particular, ahora estamos trabajando en extender el lambda cálculo de Pablo[3,4], que es quien me invitó a Grenoble, y el QML de Jon[5,6], también investigador en Grenoble).

Hoy enviamos el extended abstract al QPL08 que se realizará en Reykjavík, Islandia los próximos 12 y 13 de Julio.

El 21 de Abril nos avisarán si el paper ha sido aceptado.

Esas dos semanas y el tiempo que le siguió, he aprendido muchísimo! Ahora Pablo está tramitando una beca para ver si puedo empezar mi doctorado allí en Setiembre.

En Orsay también fueron muy amables, y también aprendí mucho. Ellos están trabajando en algoritmos y complejidad (cuánticos), un tema que no conocía en profundidad.

Tanto en Grenoble como en Orsay, dí una charla sobre mi tesis de grado, los slides los pueden obtener de aquí. (Igualmente si les interesa el tema, les recomiendo leer el extended abstract, ya que tiene algunos cambios bastante importantes).

Referencias.

[1] A. van Tonder. A lambda calculus for quantum computation. SIAM Journal on Computing, 33(5):1109-1135, 2004. (también en arXiv:quant-ph/0307150).

[2] P. Arrighi y G. Dowek. A computational definition of the notion of vectorial space. Electronic Notes in Theoretical Computer Science, 117:249-261, 2005. (también disponible en la página de Gilles Dowek).

[3] P. Arrighi y G. Dowek. Linear-algebraic lambda-calculus: higher-order, encodings and confluence. Enviado a RTA'08 (también en arXiv:quant-ph/0612199).

[4] T. Altenkirch y J. J. Grattage. A functional quantum programming language. En Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 2005. (también en arXiv:quant-ph/0409065).

[5] T. Altenkirch, J. J. Grattage, J. K. Vizzotto, y A. Sabry. An algebra of pure quantum programming. Electronic Notes in Theoretical Computer Science, 170:23-47, 2007. (también en arXiv:quant-ph/0506012).

Foco en el Procesamiento de Información Cuántica basada en Medición

La primeras contribuciones a una publicación sobre "Measurement-Based Quantum Information Processing", editada por Jian-Wei Pan y Terry Rudolph, ha sido publicada en el New Journal of Physics (NJP).

Todos los artículos están disponibles para su descarga gratuita en http://herald.iop.org/njp/m52/nad/249739/link/846

QRBGS

El Instituto Ruđer Bošković de Croacia a lanzado un servicio online de generación de números aleatorios "reales" logrado por mecanismos cuánticos. El servicio se llama "Quantum Random Bit Generator Service" (QRBGS).

Los detalles técnicos se pueden ver en dos papers que han publicado[1][2] sobre el tema.

Ref.
[1] Radomir Stevanović, Goran Topić y Karolj Skala, Quantum Random Bit Generator Service for Monte Carlo and Other Stochastic Simulations, Lecture Notes in Computer Science, Springer, 2007 (Online aquí).
[2] Mario Stipčcević y Branka Medved Rogina, Quantum random number generator, arXiv:quant-ph/0609043.

Lenguajes de Programación Cuánticos

A todo aquel que le interesen los lenguajes de programación que se están desarrollando para la computación cuántica, les recomiendo el -bastante exhaustivo- review de Simon J. Gay: Quantum Programming Languages: Survey and Bibliography[1]
Además, en su página pueden encontrar un buscador de papers sobre el tema.

Ref:
[1] Mathematical Structures in Computer Science 16(4), 2006

Rankeando papers

Dave Bacon tuvo la genial idea de darle una vuelta de tuerca más al arXiv (por ahora sólo al quant-ph que es el que más nos interesa) al crear la página SciRate.com.

La idea es simple, todos los días se copiará (y enlazará) a la sección new del archivo quant-ph del arXiv desde SciRate, y los usuarios registrados podrán "puntuar" cada uno de los papers, así, se tendrá un orden de mejor puntuado a peor puntuado (por los propios lectores) para poner alguna especie de "filtro".

¿Porqué surge ésta iniciativa?: Diariamente hay más de 20 papers nuevos sólo en la sección de Cuántica en el arXiv, eso hace que haya más ruido que ciencia. La idea es lograr un pequeño filtro (al menos para lograr ordenar de "causó más impresión" a "causó menos impresión").

Además, Dave habilitó un blog para poner sugerencias y comentarios sobre ésta iniciativa.

Si quieren ver la explicación de Dave sobre cómo funciona y el porqué de este sitio, click aquí.

Lenguajes Cuánticos de "Alto nivel"

Recientemente, Nacho publicó un comentario en mi blog en el que me mostraba un lenguaje de Computación Cuántica de alto nivel. Después, Mauro (desde su "nueva" ubicación), me pasó el dato de alguien de allí (Nottingham) que está trabajando con lenguajes de Alto Nivel para computación cuántica: Thorsten Altenkirch.

En su página pueden encontrarse varios artículos sobre sus trabajos. La verdad que me ha parecido un tema más que interesante, sobre todo por lo que planteé hace unos meses en el post Niveles de abstracción, pensando ingenuamente que aún no se estaba trabajando en ello. ¡¡Y hasta me encontré con un congreso sobre Lenguajes de Computación Cuánticos!!!

Debo decirlo: esto avanza muy rápido...

Circuito para distinguir estados de Bell desconocidos.

Recorriendo la Base de Datos de Los Alamos me he topado con un paper[1] más que interesante. Se trata de un circuito que logra distinguir entre los 4 estados de Bell, sin medirlos y sin destruirlos. El circuito planteado es el que muestro a continuación:

Es un circuito ingenioso que logra dejar en los dos qubits ancillares los valores de los qubits que generan el susodicho estado de Bell.
Me pareció un circuito muy "atractivo" hasta que noté que el mismo resultado puede conseguirse sin mucho esfuerzo "desentangleando" el estado de Bell y volviendo a entanglearlo, de esta manera:

por lo que el circuito anterior pierde todo sentido. En otro paper[2] hablan de cómo utilizar este algoritmo para clonar estados de Bell y el autor termina comparando su método con la Universal Cloning Machine[3] (UCM) diciendo que el suyo es extremadamente mejor ya que puede clonar con fidelidad 1, mientras que la UCM sólo lo hace con una fidelidad de 5/6. En realidad la cuestión es que la UCM clona cualquier estado desconocido, en comparación con éste algoritmo que copia sólo estados de Bell, los cuales pueden ser copiados por más de un método, ya que el Teorema de No-Clonning lo que dice es que no se pueden clonar estados no-ortogonales, y los estados de Bell son ortogonales entre si.

Referencias

[1] M. Gupta, P. K. Panigrahi, "Deterministic Bell State Discrimination", arXiv:quant-ph/0504183 (2005).
[2] J. O. Grabbe, "Deterministic cloning of an unknown Bell state", arXiv:quant-ph/0507016 (2005).
[3] D. Bruss, D. P. DiVincenzo, A. Ekert, C. A. Fuchs, C. Macchiavello, J. A. Smolin, "Optimal Universal and State-Dependent Quantum Cloning", Phys. Rev. A 57 2368 (e-print arXiv:quant-ph/9705038) (1998)

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.

Mi primer Paper

Aún no está publicado, pero ya lo he enviado a la International Journal of Quantum Information (IJQI), 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)