System F à la Curry y Grupo de trabajo

Buenas!

Les cuento que ya estoy instaladísimo en Grenoble. Lo que he hecho en estos días es adaptar un sistema de tipos polomórficos (System F à la Curry, ver [1], [3] o [4] para más detalles) al Linear-Algebraic Lambda-Calculus de Arrighi y Dowek [2], además hice una prueba de strong normalization (ver [1] o [3]) para este «Linear-Algebraic System F» y algunos comentarios respecto a que este sistema se corresponde de acuerdo al Isomorfismo de Curry-Howard (ver [4]) con la misma lógica (Lógica Proposicional de Segundo Orden) que el System F original. La idea ahora es empezar a jugar con reglas de tipos más complejas, hacer alguna clase de álgebra de tipos, para obtener alguna lógica un poco más loca. Ya les comentaré cuando tenga algo más armado :)

Este próximo jueves nos juntamos con el grupo de trabajo que estamos más o menos en los mismos temas, en lo que le hemos dado a llamar WHOCAS: «(informal) Workshop on Higer-Order Calculi and Algebraic Structures», seremos sólo 5 personas, ya que es un grupo de trabajo más que un workshop: Lionel Vaux, Benoît Valiron, Gilles Dowek, Pablo Arrighi y yo. La idea es que cada uno dará una pequeña charla de 40 minutos contando en qué está trabajando, así vemos qué colaboraciones pueden salir de allí. Luego del WHOCAS publicaré aquí las transparencias que use.

Referencias
[1] Jean-Yves Girard, Yves Lafont, Paul Taylor. Proofs and types. Cambridge University Press, 1989.
[2] Pablo Arrighi, Gilles Dowek. Linear-algebraic lambda-calculus: higher-order, encodings, and confluence. Lecture Notes in Computer Science: (RTA'08), 5117:17-31, 2008. (preprint en arXiv:quant-ph/0612199)
[3] Henk Barendregt. Lambda calculi with types, volume 2 of Handbook of Logic in Computer Science. Clarendon Press, Oxford, 1992.
[4] Morten Sørensen, Pawel Urzyczyn. Lectures on the Curry-Howard Isomorphism, volume 149 of Studies in Logic and the Foundations of Mathematics. Elsevier, 2006. (disponible para bajar en CiteSeer)

Categories, Logic and Foundations of Physics: Los videos

Copio (y traduzco) un post de Bob Coecke en el blog The n-Category Café:

Los videos del 2do workshop Categories, Logic and the Foundations of Physics que se realizó en Londres están disponibles aquí. También hay allí algunas charlas del workshop Logic, Physics and Quantum Information Theory organizado por Prakash Panagaden en Barbados. Desafortunadamente algunas de las charlas no salieron muy bien, por ejemplo la de Peter Selinger "completeness result for dagger compact categories". Esperamos poder compensar esto en el workshop Quantum Physics and Logic que se hará en julio en Islandia. Todos los créditos para Ben Jackson y Jamie Vicary por realizar esta filmación y ponerla online.

La fecha para el próximo workshop "Categories, Logic and the Foundations of Physics", el cual será en Oxford, es el 23 y 24 de agosto - dos días esta vez.

Ese congreso en Islandia es donde presentamos y nos fue aceptado el paper sobre medición y confluencia en lambdas cálculos cuánticos. Lamentablemente por razones económicas no podré ir, así que al menos espero poder ver los videos.

Publicada la lista de papers aceptados para el QPL

El paper que enviamos al QPL fue aceptado para una exposición completa de 30 minutos (en contraposición con una exposición corta de 15 minutos). La lista completa de los papers aceptados está publicada en la página del evento.

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. Update: (16/6/08) En un post reciente pueden encontrar la versión extendida, la cual tiene varios cambios sustanciales

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).

Video de la presentación de Tesis

Lo prometido: el video de la presentación "Agregando Medición al Cálculo de van Tonder". Los créditos para mi hermana y mi novia por la excelente filmación :).

Los slides los pueden bajar de aquí (versión para imprimir), y en unos días subiré el informe de tesis completo (le estoy arreglando algunos detalles que no me gustaron). Dejo un draft.

Obteniendo mi título

Después de una larga ausencia por este blog, paso a contar la causa: Estuve estudiando a full para llegar a recibirme antes de terminar el año.

Y llegó el momento de presentar mi Tesis de Licenciatura en Ciencias de la Computación:

Día y Hora:

Viernes 21 de Diciembre de 2007, 10:45hs

Lugar:

Aula 23, Pellegrini 250, Rosario.
Facultad de Ciencias Exactas, Ingeniería y Agrimensura
Universidad Nacional de Rosario

Título de la tesis:

Agregando medición al Cálculo de van Tonder

Tesista:

Alejandro Díaz-Caro

Director:

Dr. Manuel Gadella

Co-Director:

Dr. Pablo Martínez López

Resumen:

El área de los lenguajes de programación cuánticos se está desarrollando a una gran velocidad. En particular, se han definido varias extensiones al Lambda Cálculo que proveen la sintaxis y semántica necesarias para modelar algoritmos cuánticos.
Uno de los trabajos más influyentes en este sentido es el \lambda_q de André van Tonder[1]. Este es un Lambda Cálculo, definido mediante su semántica operacional, para cómputos puramente cuánticos: la medición no es parte del cálculo.
La intención de este trabajo es agregar medición al \lambda_q, para lo cual nos valemos de algunas herramientas del Lambda Cálculo probabilístico definido por Di Pierro, Hanking y Wiklicky en [2]. Además, siguiendo la línea de trabajo de van Tonder, también hacemos uso de la la sintaxis para la lógica lineal de Philip Wadler[3].

Ref:
[1] A. van Tonder, "A Lambda Calculus for Quantum Computation", SIAM J. Comput. 33(5), Society for Industrial and Applied Mathematics, 1109–1135, 2004
[2] A. Di Pierro, C. Hankin y H. Wiklicky, "Probabilistic Lambda-calculus and Quantitative Program Analysis", Journal of Logic and Computation 15(2), 159–179, 2005
[3] P. Wadler, "A Syntax for Linear Logic", Proceedings of the 9th International Conference on Mathematical Foundations of Programming Semantics, Springer-Verlag, 513–529, 1994


En algunos días subiré el PDF completo de la tesis y el PDF de la presentación (En otro post).

---

Update: Ya soy licenciado! Dejo algunas fotos (hay más en mi album picasa) y en unos días subiré el video de la presentación en otro post está el video de la presentación.

Antes de empezar, esperando a que llegue el director de escuela.

Abrazos y felicitaciones luego de la presentación.

Una vieja tradición argentina: Los compañeros y amigos ensucian a los egresados con huevos, harina, yerba mate, gaseosa y todo lo que se encuentre a la mano.

La foto de grupo, luego de los huevos. Por algún motivo nadie me quiso abrazar :P

QCMC 2008: Primer anuncio

Transcribo (y traduzco) el mail que me llegó del Primer Anuncio del QCMC 2008

Queridos Colegas,

Este es el primer anuncio de la Novena Conferencia Internacional en Comunicación, Medición y Computación Cuántica (QCMC), la cual se desarrollará en la Universidad de Calgary, Canadá, del 19 al 24 de Agosto de 2008.

El alcance de la conferencia será similar al de la serie de encuentros anteriores e incluirá los siguientes temas:

- Comunicación Cuántica y Criptografía Cuántica
- Medición Cuántica y Meteorología Cuántica
- Computación Cuántica y Teoría de la Información Cuántica
- Implementaciones del Procesado Cuántico de Información
- Control Cuántico

La fecha límite para la presentación de resúmenes de papers es el 15 de Abril de 2008, y la fecha límite para la registración es el 30 de Junio de 2008. Puede encontrar más detalles sobre el evento en el sitio web http://www.qcmc2008.org/

Calgary es una ciudad de un millón de habitantes en las colinas de las magníficas Montañas Rocosas Canadienses. Se encuentra cercana al Parque Nacional de Banff y ofrece a muchas actividades recreativas de verano incluyendo excursiones, rafting y kayak, escaladas, exploración de cuevas, buceo en lagos de montaña, ciclismo de montaña, visita a glaciares, ala delta, y equitación. Agosto es un mes excelente para la recreación debido a su clima clemente y tiempo seco.

Esperamos darle la bienvenida en Calgary en agosto de 2008.

En nombre de los comités de organización y de programación,

Alex Lvovsky, organizador principal.

Versión original:

Dear Colleagues,

This is the first announcement of the Ninth International Conference on Quantum Communication, Measurement and Computing (QCMC), which will be held at the University of Calgary, Canada, on August 19 to 24, 2008.

The scope of the conference will be similar to that of previous meetings in the series and include the following topics:

- Quantum Cryptography and Quantum Communications
- Quantum Measurement and Quantum Metrology
- Quantum Computing and Quantum Information Theory
- Implementations of Quantum Information Processing
- Quantum Control

The abstract submission deadline for contributed papers is April 15, 2008, and the early registration deadline is June 30, 2008. Further details about the meeting can be found on the website http://www.qcmc2008.org/.

Calgary is a city of one million inhabitants in the foothills of the magnificent Canadian Rocky Mountains. Calgary is close to Banff National Park and offers many summertime recreational activities including hiking, whitewater rafting and kayaking, climbing, caving, mountain-lake scuba diving, mountain biking, glacier trips, hang gliding, and horseback riding. August is an excellent month for recreation due to its clement warm and usually dry weather.

We look forward to welcoming you in Calgary in August 2008.

On behalf of the organizing and program committees,

Alex Lvovsky, principal organizer

WECIQ 2007

Del 29 al 31 de Octubre se desarrollará en la ciudad de Campina Grande, Brasil, el 2do Workshop-Escuela de Computación e Información Cuántica. El primero se hizo el año pasado en la ciudad de Pelotas, y estuvo realmente muy bueno!
Aún se pueden enviar resúmenes de trabajos hasta el 31 de Mayo. Le recomiendo a todo el que tenga la posibilidad de ir, que no se lo pierda.

Video de David DiVincenzo

Acá dejo un video de una charla de David DiVincenzo en el "International Workshop on Measurement-Based Quantum Computing" que se realizó en Oxford entre el 18 y 21 de Marzo pasados. La Charla se titula "The Pioneers of Quantum Computing" (Los Pioneros de la Computación Cuántica) y acá dejo el abstract.

Que lo disfruten.

D-Wave presenta sus primeros prototipos

D-Wave Systems presenta este 13 de Febrero en Mountain View (California, EE.UU.) y repite la presentación el 15 de Febrero en Vancouver (Columbia Británica, Canadá) los primeros prototipos de Computadoras Cuánticas de 16 qubits.

Si bien éstos productos comerciales ya están casi para salir al mercado, cabe aclarar que son dispositivos para fines muy particulares, no "Computadoras Cuánticas de Propósito General".

Bueno, hay mucha expectativa puesta en la presentación, veremos cómo va.

Quienes quieran asistir, deben registrarse a dichas presentaciones en la página de D-Wave.

JAI v.2.0

El día 5 de diciembre próximo, en el Hotel Ariston (Córdoba 2554, Rosario), se realizará la JAI v 2.0 (Segunda Jornada Abierta de Informática) organizada por Sadio Rosario.

«La JAI, en su segunda versión, busca generar un ámbito de exposición académica, y al mismo tiempo, un espacio que reuna inquietudes que incentiven la actualización de los profesionales del sector.»

Junto con Julián Samborski Forlese daremos una charla titulada "Brevísima Introducción a la Computación Cuántica" a las 14:30hs en la Sala Orión. (es la misma charla que dimos hace unos días en las JCC).

Están todos invitados, la entrada es libre y gratuita pero requiere registración previa ya que tienen cupos limitados: http://rosario.sadio.org.ar/jai2.

Edit: Las transparencias de la charla se pueden bajar de aquí.

Brasil: Punteros sudamericanos

Ayer volví del WECIQ, un Workshop y Escuela Brasileña sobre computación cuántica. Realmente me impresionó la cantidad de grupos y los temas variados que trabajan en nuestra hermana Brasil. El evento tuvo un nivel muy bueno y, por supuesto, un nivel de cordialidad y cooperación muy agradables.
Para todos aquellos a quienes les interese ver los trabajos y mini-cursos presentados, en la página del evento se pueden encontrar los anales digitalizados.

QIP 2007

Del 30 de Enero al 3 de Febrero de 2007 se desarrollará en Brisbane, Australia el 10º QIP (Quantum Information Processing). Este workshop es el más importante en Información Cuántica teórica y este año está a cargo de nada menos que Michael Nielsen.
El deadline para enviar abstract de charlas es el 4 de Noviembre de 2006.
El deadline para registrarse es el 24 de Noviembre de 2006.
La página del evento se puede ver aquí: http://qipworkshop.org.
Bueno, veamos si consigo alguna beca para ir allí (cualquier propuesta sobre a quién pedir una beca es bienvenida) ;)

WECIQ 2006

Del 9 al 11 de Octubre se desarrollará en la ciudad de Pelotas, Brasil, un evento que pinta ser interesante, el 1er Workshop-Escuela de Computación e Información Cuántica.
El evento contará con importantes investigadores de la región, y, además de los trabajos (que aún se pueden presentar hasta el 20 de Julio), tendrá la sección "Escuela" con charlas de 2hs en los siguientes temas:

• Conceptos e interpretaciones de la Mecánica Cuántica
• Circuitos cuánticos
• Información cuántica
• Algoritmos cuánticos
• Lenguajes de programación cuánticos
• Tecnologías para las computadoras cuánticas.

La inscripción estará abierta a partir del 20 de Agosto.

Volviendo...

Buenas! Ya se me están terminando los días por Europa, he estado en Paris, en los cursos del Institut Henri Poincaré, estuvieron allí gente como Bennett, Brassard, Winter, Aharonov, Cerf, Cleve, Gottesman, Zoller.... bueno, toda esa gente que son la cabeza de la computación cuántica hoy en día, estuvo increíble.
Para quienes quieran disfrutar de las charlas, la mayor parte de ellas fueron grabadas en video y están aquí, realmente valen la pena.
Para quienes quieran ver las fotos que tomé de París están aquí ;)
Luego de Paris (que estuve sólo el mes de Febrero), me he dado una vuelta por Valladolid, España, donde seguimos trabajando con Manolo, Juanjo y todo el grupo de allí, y de paso di un pequeño seminario sobre la Teleportación de N-qubits.
Bueno, ya postearé algo más en cuanto llegue a Argentina!

Cursos en el Instituto Henri Poincaré

Información, Computación y Complejidad Cuántica
4 de Enero al 7 de Abril de 2006

TOPICS

• Algoritmos cuánticos
• Comunicaciones
• Teleportación y criptografía
• Corrección de errores
• Información cuántica con variables contínuas
• Decoherencia y caos cuántico inducido por imperfecciones
• Implementación de qubits en estado sólido
• etc, etc...

Además, los siguientes eventos se llevarán a cabo:

• 16 al 20 de Enero: 9th International Workshop "Quantum Information Processing"
• 13 al 16 de Febrero: "QIPC Cluster Review and Conference 2006"
• 22 al 26 de Marzo: Workshop "Quantum computation and coherence"

Para más información dejo el Website del evento, y si algún alma caritativa me consigue una beca, nos veremos allá ;)