11 de noviembre de 2014

Escuela de Geometría Algebraica en Río

El próximo año del 1 al 5 de Junio en Rio de Janeiro comienza una escuela en geometría algebraica que tiene muy linda pinta. El enlace dejo aquí. El poster de la escuela lo pongo más abajo. Está organizado por el IMPA.

La Geometría Algebraica desde hace un tiempo atrás viene haciendo algunas conexiones muy interesantes con la complejidad computacional. A este nuevo enfoque se lo conoce como Geometric Complexity Theory (GCT) y fue iniciado por Ketan Mulmuley de la Universidad de Chicago. 

El GCT es más bien un programa, que apunta a resolver los grandes problemas como P vs NP. Actualmente, los matemáticos están más interesados en un objetivo menos ambicioso, pero igualmente difícil. Este problema es el de separar las clases #P y FP a través de dos problemas bien representativos de ambas clases: el cómputo de la permanente y el determinante de una matriz. El determinante se puede computar en tiempo polinomial usando eliminación guassiana, y la permanente es completo para #P.



29 de octubre de 2014

QOptics: Días 1 y 2

Les cuento acerca de las dos charlas que más me interesaron en los primeros 2 días de la conferencia. La primera fue del área de quantum information, por Antonio Acín, y la segunda de fundamentos, por Andrew White.

Tony habló sobre implementaciones de protocolos para Device Independent Quantum Key Distribution (DIQKD).

La idea de QKD es generar claves compartidas (para luego usarlas en, por ejemplo, algoritmos de encriptación) que sean seguras contra la presencia de espías en la comunicación y que tal seguridad se base en principios de la cuántica (cómo, por ejemplo, la no-clonabilidad de estados) en lugar de la aparente intractabilidad de problemas matemáticos.
El primer protocolo para distribución cuántica de claves fue BB84. Este protocolo se prueba seguro (i.e., la probabilidad de que un espía obtenga información significativa sobre la clave generada se va exponencialmente a cero con el tamaño de la clave). Sin embargo, la prueba depende fuertemente de la posibilidad de controlar perfectamente los estados de los sistemas intervinientes así como de los aparatos de medición.
DIQKD viene a eliminar esas limitaciones, dando protocolos cuya seguridad no dependa del comportamiento interno de los dispositivos usados para generar las claves. Y, como probablemente se imaginarán, detrás de estos protocolos está el teorema de Bell. La idea es que, si la generación de la clave se realizó usando una correcta violación de una desigualdad de Bell, entonces ningún espía pudo haber adquirido información significativa sobre las correlación intervinientes, pues eso daría lugar a un modelo local. Entonces, en DIQKD, el desafío tecnológico pasa a ser lograr generar violaciones validas (i,e. loophole-free) de desigualdades de Bell.

La charla de Andrew White tuvo dos partes. La primera trató acerca de las consecuencias (principalmente computacionales) de tener una teoría física compatible con la cuántica cuyo espacio-tiempo permita la existencia de Closed Timelike Curves (piensen en agujeros de gusano).

La segunda, fue acerca del estado de realidad que se le puede adscribir a la función de onda.
Aun si sos un realista científico (creés que hay una realidad, independiente de la observación, y que la ciencia es el camino para descubrirla), tenés dos opciones para cómo tratar a la función de onda: 1) como describiendo nuestro estado de conocimiento acerca del sistema (psi-epistemic) o 2) cómo un objeto de la realidad (psi-ontic). En el primer campo entraría la interpretación de Copenhague (aunque ellos no son generalmente realistas científicos) y en el segundo la interpretación de Muchos Mundos de Everett o la mecánica de Bohm. Andrew contó el resultado de Pusey, Barrett y Rudolph quienes probaron que la función de onda no puede ser un concepto epistémico si se restringe a las explicaciones ónticas complementarias a tener la forma de modelos de variables ocultas à la Bell.

Para una explicación de este último tema les recomiendo http://mattleifer.info/2011/11/20/can-the-quantum-state-be-interpreted-statistically

También habló sobre "Information Causality"[1], pero ese tema lo voy a dejar para un post aparte.

¡Saludos!

M. Pawlowski, T. Paterek, D. Kaszlikowski, V. Scarani,
A. Winter, and M. Zukowski, Nature 461, 1101 (2009).

28 de octubre de 2014

Curso en la Escuela de Verano de Río Cuarto

Como anuncié previamente, este verano estaré dando un curso de posgrado en la Escuela de Verano de Ciencias Informáticas de Río Cuarto.

Fundamentos de lenguajes de programación cuántica

En este curso de 5 días, tomaré los primeros dos para hacer una introducción a la computación cuántica. El tercer día daré una introducción al lambda-cálculo. El cuatro día explicaré los lenguajes de programación à la Selinger-Valiron, donde el control del programa se lleva de manera clásica y el cómputo en una máquina cuántica, la cual recibe las instrucciones a ejecutar desde la máquina clásica. Finalmente el último día explicaré los lenguajes de programación puramente cuánticos, donde el control también se lleva a cabo en una máquina cuántica, lo que permite superponer programas. Daré como ejemplo el cálculo vectorial que fue uno de los resultados de mi tesis.

Más detalles del curso, en la página de la escuela.

¡Los espero!

24 de octubre de 2014

Quantum Optics @ MDQ

La semana que viene se va a estar realizando el VII Quantum Optics en la ciudad balnearia de Mar del Plata, organizado por el Latin American Committee for Quantum Optics. Contará con charlas plenarias de reconocidos miembros de la comunidad de fundamentos e información cuántica, entre otros temas.

Acá pueden ver el programa y la lista de abstracts.

Voy a estar reportando en vivo para Computación Cuántica, tratando de comentar sobre las charlas más afines a los temas del blog.

¡Saludos!







20 de octubre de 2014

Bienal Latinoamericana de Óptica Cuántica

Amigos, este es un post cortito para contarles que el Miércoles voy a estar presentando un resultado en la Bienal Latinoamericana de Óptica Cuántica (BLOC-O) que se desarrolla en la UNLP del 22 al 24 de Octubre.

El resultado es un nuevo loophole para experimentos tipo Bell. En poca palabras, el teorema de Bell permite, a partir de la estadística colectada sobre las mediciones en un conjunto de sistemas físicos, determinar si el comportamiento de estos puede o no ser simulado por computadoras que no se comunican entre sí. 
Con mis coautores probamos que el teorema no aplica a situaciones en las cuales las elecciones de las mediciones que se realizan sobre los sistemas se hace siguiendo algún algoritmo (por ejemplo, algún PRNG), lo cual es habitual en la mayoría de las realizaciones experimentales hasta la fecha.

Para los que quieran saber más sobre los detalles del trabajo, tenemos un preprint en el arXiv http://arxiv.org/abs/1407.0604 con éste y otro resultado acerca de la preparación de estados mixtos.

¡Saludos!

13 de octubre de 2014

En Argentina, próximos movimientos

Hola,

Ya estoy instalado en Argentina, y empezando a moverme por aquí y allá. Les comento dónde estaré y haciendo qué próximamente:
  • Esta semana estaré participando de las Jornadas de Ciencias de la Computación, que se llevan a cabo en Rosario desde hace mucho tiempo (estas son las 12vas!). Son del 15 al 17 de octubre. Yo voy a dar una charla  el viernes 17 a las 17hs. Voy a presentar un trabajo que ya he comentado en este blog, sobre los isomorfismos de tipos y sus consecuencias en los lenguajes de programación (clásicos, nada de cuántica acá). (Update: post con video).
  • A fines de Noviembre, estaré en París participando del segundo encuentro del proyecto Franco-Chino LOCALI (el primero se hizo en China) que se lleva a cabo del 24 al 26. Allí voy a hablar sobre un trabajo que empecé hace muy poquito, continuación de mi tabajo en isomorfismos de tipos. Ya contaré más sobre ese trabajo que recién estoy empezando, cuando tenga algo más armado. (Update: página del encuentro con abstracts de las charlas).
  • Finalmente, del 9 al 14 de Febrero, estaré dando un curso en la Escuela de Verano de Río Cuarto. Otro evento con larga trayectoria en Argentina (ya van por las 22vas!). En ese curso de 5 días (2.5hs por día) voy a hablar en general de mis temas de investigación: extensiones cuánticas al cálculo lambda, con aplicaciones en teoría de tipos probabilistas y no-deterministas. La idea es explicar qué es lambda-cálculo, qué es computación cuántica, y cómo se relacionan. (Update: post).
Bueno, espero que haya muchos interesados, y desde ya les cuento que si están terminando su carrera y pensando en la posibilidad de un doctorado en estas áreas (teoría de tipos, computación cuántica, reescritura, o teoría de tipos y reescritura para computación cuántica), pues me encantaría dirigir alguna tesis en esta dirección. La Universidad Nacional de Quilmes es un ámbito muy ameno para llevar a cabo un doctorado, y el CONICET otorga becas de doctorado (para no tener que trabajar mientras se hace el doctorado, ya que el doctorado en sí es un trabajo). No duden en consultarme con respecto a esto!

3 de julio de 2014

Repatriación

Les cuento que, a partir de agosto, volveré a la Argentina, repatriado por medio del programa Raíces del Ministerio de Ciencia, Tecnología e Innovación Productiva de la Argentina, con un cargo de Profesor Adjunto de Dedicación Exclusiva en el Departamento de Ciencia y Tecnología de la Universidad Nacional de Quilmes.

Ha sido un largo trayecto desde que hace casi 6 años partimos con mi mujer a Grenoble, Francia, donde hice mi doctorado, y luego a París, donde estamos ahora. En estos años he conocido mucha gente de todos los rincones del planeta y he aprendido mucho de gente invaluable. Creo que esta experiencia me será muy útil en el futuro, y ahora espero poder contribuir a la ciencia desde mi país, Argentina, que en los últimos años ha demostrado una gran voluntad política por hacer crecer la investigación científica, con una inversión constante. Espero que siga así, y poder contribuir activamente a ese crecimiento.

En Quilmes voy a trabajar con Eduardo Bonelli y el equipo LoReL. Desde el punto de vista docente voy a integrar el equipo pedagógico de la recientemente creada Licenciatura en Desarrollo de Software, dirigida por Pablo E. "Fidel" Martínez-López y coordinada por Eduardo, donde estaré a cargo de la cátedra "Características de Lenguajes de Programación".

Eso es todo por ahora, mi próximo post probablemente lo haga desde Argentina.

28 de mayo de 2014

Arena de juego

Un grupo ingenieros de Google desarrollaron un "playground" cuántico: un simulador con un lenguaje llamado QScript bastante intuitivo. Tiene loops, sentencias condicionales, etc, y las principales compuertas cuánticas necesarias para jugar un rato. Sobre todo la sección de ejemplos es muy buena para entender intuitivamente qué hacen las compuertas cuánticas y ver implementados algunos algoritmos importantes como Grover y Shor. Todo esto se completa con una linda visualización gráfica del algoritmo que se está ejecutando.

Les dejo el link (recomiendan verlo con Chrome):


(Gracias a Julián por el link)

27 de abril de 2014

Teoría de tipos homotópica y el axioma de univalencia

Antes que nada, me disculpo por la larga ausencia en el blog. Voy a tratar de comentarles, en este post, sobre un área reciente en teoría de tipos, en la cual me estoy empezando a interesar. No soy experto en el área, así que si hay alguien trabajando en esto, está más que invitado a postear en el blog. En este post sólo comento algunas ideas básicas, y porqué de mi repentino interés en esta teoría.

La teoría de tipos homotópica (o "HoTT" por sus siglas en inglés), es una nueva manera de interpretar la teoría de tipos. Empecemos con algunos conceptos básicos. De la wikipedia:
"En topología, y más precisamente en topología algebraica, dos aplicaciones continuas de un espacio topológico en otro se dicen homotópicas (del griego homos = mismo y topos = lugar) si una de ellas puede "deformarse continuamente" en la otra." -- Wikipedia: Homotopía
En teoría de tipos, se dice que dos tipos son isomorfos si hay una biyección entre ellos: o sea, A≡B si existen f:A→B y g:B→A tal que f∘g=id_B y g∘f = id_A. La idea de la teoría de tipos homotópica es considerar a los tipos A como espacio topológicos, los términos a como puntos en ese espacio, entonces a:A se traduce como a∈A. Una prueba de igualdad de dos términos de tipo A, es simplemente un camino de un punto a otro en ese espacio. Y finalmente una prueba de igualdad entre dos pruebas de igualdad, se interpreta como una homotopía. 

HoTT está planteado con tipos dependientes, donde existe el tipo Id_A(a,b), y una prueba con ese tipo es una prueba de que a=b en A. Pero como Id_A(a,b) en sí es un tipo, podemos probar que p=q en el tipo Id_A(a,b), o sea, podemos probar Id_(Id_A(a,b))(p,q), lo cual significa probar que dos pruebas de igualdad de a y b en el tipo A, son iguales. A eso es a lo que se considerará una homotopía en la interpretación HoTT.

Resumiendo:
Teoría de tiposTeoría de homotopías
tipo Aespacio A
término apunto a
a:Aa∈A
p:Id_A(a,b)camino p:a↦b
g:Id_(Id_A(a,b))(p,q)homotopía g:p⇒q

En particular, en tipos dependientes, los tipos son elementos de un tipo universal U (en realidad, existen diversos U para eliminar paradojas al estilo la de Russell, pero mantengamos la descripción simple). Por lo tanto, se puede probar también que dos tipos son iguales: Id_U(A,B).

Lo interesante del tema: el axioma de univalencia. El axioma es muy simple de escribir, pero tiene grandes implicaciones:  A~B ↔ A=B. O sea, si A y B son equivalentes/homotópicos, entonces A es igual a B (el sentido inverso de la flecha es trivial). O de otra manera, si dos tipos son equivalentes, entonces son iguales.

De dónde nació mi interés en el tema? Yo he estado trabajando en una teoría de tipos simple, módulo isomorfismos: es decir, si dos tipos son isomorfos, en esta teoría se consideran iguales (la versión más actualizada de este paper se encuentra en mi página web). Nuestro trabajo es una interpretación computacional: definimos el cálculo sintácticamente, y mostramos sus propiedades. Claro que no es tan sencillo en HoTT: nosotros usamos tipos simples, HoTT usa tipos dependientes. Nosotros sólo usamos dos conectivos: implicación y conjunción. En ese caso con sólo esos conectivos, sólo existen 4 isomorfismos a considerar. En HoTT, con tipos dependientes, hay que considerar todas las pruebas que se pueden realizar de igualdad. O sea: nuestro trabajo está muy lejos del tema HoTT... pero nos interesa ir hacia allí! Quizá algunas técnicas en nuestro trabajo puedan servir para la teoría de tipos homotópica, y es una dirección que estamos dispuestos a seguir.

A quienes les interese aprender sobre la teoría de tipos homotópica, existe un libro, el cual puede ser descargado gratuitamente de aquí, que es el libro que inició todo. La historia es así: Vladimir Voevodsky es el padre de ésta área, y muy pronto, gente muy reconocida empezó a involucrarse. En 2012-2013, el Institut for Advanced Studies de Princeton organizó un año de trabajo intensivo en ésta nueva área, y de allí salió el libro, que hoy se sigue modificando colaborativamente.

Para quienes se pregunten que tiene que ver todo esto con computación cuántica: pues nada. Yo comenzé con cuántica, me interesé por los tipos vectoriales, como una generalización de cuántica, y el no-determinismo en particular, los cuales me llevaron a los isomorfismos de tipos, a los cuales llegué desde cuántica y ahora me estoy interesando por esta nueva teoría a la cual llegué desde los tipos isomorfos. Sin embargo, hay un hilo conductor, por lo que algunas ideas de cuántica terminan colándose en los otros trabajos, y viceversa.