Workshop on Foundations of Quantum Computation @ Quilmes

FoQCoSS Kickoff Workshop

Foundations of Quantum Computation: Syntax and Semantics

5 y 6 de Diciembre

Universidad Nacional de Quilmes

Roque Sáenz Peña 352, Bernal, Buenos Aires, Argentina

http://diaz-caro.web.unq.edu.ar/foqcoss.html

En el marco del proyecto STIC-AmSud FoQCoSS, el lunes 5 y martes 6 de diciembre próximos se realizará un workshop con exposiciones de los integrantes del proyecto. El mismo se desarrollará en el campus de la Universidad Nacional de Quilmes (Roque Sáenz Peña 352, Bernal), aula a confirmar.

Rogamos confirmar asistencia enviando un mail a alejandro ARROBA diaz-caro PUNTO info, con su nombre, apellido e institución de pertenencia.

Por razones de organización, se ruega confirmar asistencia enviando un email a alejandro@diaz-caro.info

Cronograma:

(Los abstracts de las charlas, y más información sobre el evento, los pueden ver en la página del mismo).

Lunes 5/12 - Aula 22
10.30 ► Gilles Dowek: Quantitative informational aspects in discrete physics
11.15 ► Pablo Arrighi: Discrete Lorentz covariance for quantum walks and quantum cellular automata
12.00 - Almuerzo
14.00 ► Christian de Ronde: On the physical foundation of quantum superpositions (beyond measurement outcomes and mathematical structures)
14.45 ► Simon Martiel: Quantum causal graph dynamics
15.30 - Coffee break
16.00 ► Stefano Facchini: Quantum walking in curved spacetime: (3+1) dimensions, and beyond

Martes 6/12 - Aula 44
10.30 ► Benoît Valiron: A Geometry of interaction for quantum computation
11.15 ► Alejandro Díaz-Caro: Typing quantum superpositions and projective measurements
12.00 - Almuerzo
14.00 ► Gabriel Senno: Robust Bell inequalities from communication complexity
14.45 ► Ariel Bendersky: Non-signaling deterministic models for non-local correlations have to be uncomputable
15.30 - Coffee break
16.00 ► Renaud Vilmart: Completeness and Incompleteness of the ZX-Calculus, a diagrammatic language for quantum reasoning and computing
16.45 ► José Carlos Puiati (video-conferenced): Implementation of an interpreter and typechecker for the double effect quantum lambda calculus

Materia optativa en Rosario

Este semestre, además del curso de una semana (25 hs) que voy a dar en el CACIC, voy a dictar una materia optativa en la Licenciatura en Ciencias de la Computación (también da créditos para el doctorado) en la Universidad Nacional de Rosario. El nombre de la materia es

Introducción a la computación cuántica

y fundamentos de lenguajes de programación.

Aquí les dejo la página de la misma, donde iré subiendo el material.

http://computacion-cuantica.web.unq.edu.ar

Workshop INFINIS en Temas de Tesis de Licenciatura y Doctorado

INFINIS es un Laboratorio Internacional Asociado del CNRS-Université Paris Diderot y del CONICET-Universidad de Buenos Aires especializado en métodos formales en ciencias de la computación. Fue creado en 2011.

El miércoles 3 de agosto haremos un workshop en el que cada grupo de INFINIS presentará posibles temas de Licenciatura y de Doctorado. Son seis grupos y cada presentación tiene una duración de 30 minutos. Las presentaciones están destinadas a alumnos. No hace falta inscribirse, están todos bienvenidos.

En particular, yo estaré presentando los temas del grupo Logics and Dynamics of Programming Languages (o como lo rebautizamos en español, Lógica y Reescritura para Lenguajes de Programación).

Para más información pueden ver la página del workshop

http://winfinis.dc.uba.ar/w2016.html

Algoritmos Cuánticos para Optimización Multiobjetivo

Una de las aplicaciones más populares en computación cuántica es en el diseño de algoritmos de optimización. Esto es gracias a la popularidad del modelo de computación cuántica adiabática y anuncios realizados por compañías privadas que dicen poseer un computador cuántico de más de 1000 qubits basados en este modelo.

No voy a realizar un debate sobre si lo que dicen estas compañías es cierto o no. El objetivo de esta entrada es simplemente dar a conocer mi más reciente artículo que puede descargarse de este enlace arXiv:1605.03152. Este es el primer trabajo en donde se muestra como resolver un problema de optimización "multiobjetivo" en un computar cuántico (por lo menos eso creo después de hacer una revisión de la bibliografía). En principio, un problema multiobjetivo es un problema de optimización con dos o más funciones objetivo (que pueden ser contradictorios o presentan trade-offs) que deben optimizarse de forma simultánea. Entonces, pueden existir soluciones "óptimas" que son incomparables entre sí. Por ejemplo, si quiero llegar de un punto A a otro punto B en un mapa, quiero elegir el camino con menos tránsito y que sea más corto. Sin embargo, tal vez el camino más corto tenga la mayor cantidad de tránsito o el camino más transitado sea el más largo; entre esas dos soluciones pueden existir muchas otras soluciones con trade-offs entre cantidad de tránsito y longitud. Si quisiéramos considerar el tiempo de viaje, es suficiente con agregar eso como una función objetivo más. A las personas interesadas les invito a leer el artículo enlazado arriba para los detalles. 

Este es un artículo muy interesante porque al principio el problema era muy difícil, y no teníamos la menor idea de como proceder. El objetivo era conseguir un algoritmo cuántico en donde pudiéramos demostrar la convergencia a una solución óptima en tiempo finito. Ahí fue en donde el teorema adiabático resultó de mucha ayuda. Sin embargo, como en muchos otros trabajos de investigación, nuestra demostración nos ayudó a identificar propiedades que hacen difícil la implementación de algoritmos cuánticos adiabáticos para optimización multiobjetivo. Estas propiedades en particular aparentemente no son estudiadas por la comunidad de optimización multiobjetivo, y sin embargo, introducen también líneas de investigación interesantes en optimización clásica.

Agenda de viajes... Y CURSO DE CUANTICA

En este post les cuento un poco los viajes programados que tengo para este año. En particular, si son estudiantes de computación en Argentina y quieren ir a un curso de computación cuántica y lenguajes para la misma, voy a estar dando un curso en el CACIC.

• Hasta mediados de Julio (y desde Enero) estoy en la Università degli Studi di Torino, en Turín (Italia), a donde vine como investigador visitante a trabajar con Simona Ronchi della Rocca y Mariangiola Dezani-Ciancaglini.
• En Mayo voy una semana a trabajar con Gilles Dowek a París (Francia).
• En Junio voy al CSR a presentar el paper que escribimos con Abuzer Yakaryılmaz, en San Petersburgo (Rusia).
• También en Junio voy al FSCD, en Porto (Portugal), aunque allí no voy a presentar nada (pero no me podía perder el primer RTA-TLCA fusionado en FSCD).
• En Julio voy a la sesión de Lógica y Computabilidad del Congreso Latinoamericano de Matemáticos en Barranquilla (Colombia). Allí voy a presentar lo que he estado trabajando con Simona, que básicamente es una continuación del trabajo con Gilles (es la interpretación en lógica lineal de ese trabajo).
• Y finalmente, en Octubre, voy a San Luis (Argentina) a dar un curso de 5 días a la Escuela del CACIC. El curso va tener básicamente el mismo formato que el que dí en la Río, pero con un poco más de profundidad (porque tengo el doble de horas). Les dejo acá los datos oficiales del curso:
  
  TITULO: Fundamentos de lenguajes de programación para computación cuántica
  
  OBJETIVOS: Introducir la computación cuántica y los fundamentos de lenguajes de programación para dicho paradigma. Se pretende que los estudiantes tengan una primera visión no sólo de la computación cuántica sino también de problemas científicos actuales a la hora de estudiar sus fundamentos lógicos. El estudiante debería terminar con un conocimiento introductorio de computación cuántica y de cálculo lambda.
  
  CONTENIDOS: Introducción a la computación cuántica. Conceptos de física. Formalismo matemático. Algoritmos cuánticos: Deutsch, Deutsch-Jotza, Grover, Teleportación, Codificación Superdensa, Protocolo de distribución de claves BB84 Introducción al cálculo lambda tipado. Relación entre tipos y lógica intuicionista. Introducción a las extensiones cuánticas al cálculo lambda: paradigma de control clásico y datos cuánticos, y paradigma de control y datos cuánticos tipado.
  

Espero cruzarlos en algún evento.

Continuando con autómatas afines

En una entrada anterior Alejandro había anunciado un nuevo paper sobre una idea de un modelo de computación con transformaciones afines. A modo de continuación de ese artículo, este servidor en coautoría con Abuzer Yakaryilmaz, acabamos de hacer público una continuación a la idea de lo autómatas afines. Se puede descargar el manuscrito directamente desde arXiv. En este caso nos concentramos en la complejidad descripcional de dichos computadores con varios resultados interesantes.

También aprovecho esta ocasión para resaltar otra continuación más de este mismo paper, titulado "Can one quantum bit separate any pair of words with zero-error?," escrito por Belovs, Montoya y Yakaryilmaz; también puede descargarse desde arXiv. En este artículo en particular se mira un problema muy sencillo de explicar pero bastante complejo de resolver, el de separar palabras. Por ejemplo, si te doy x e y, ¿cuál él es el autómata de tamaño mínimo que acepta x y rechaza y?

Entonces, por lo que va de año ya son 3 los artículos sobre autómatas afines. ¿Será el inicio de una línea de invetigación? Solo el tiempo lo dirá. Por ahora, el modelo es muy interesante y prometedor ya que simplifica muchos argumentos en la teoría de autómatas cuánticos.

Computación afín y autómatas afines, en Rusia

El paper que escribimos con Abuzer Yakaryılmaz (el cual comenté aquí), fue aceptado en el CSR 2016 (The 11th International Computer Science Symposium in Russia).

Pueden bajar un preprint de arXiv. La versión publicada es un poco más corta por límites de espacio, y está aquí: LNCS 9691:146-160.

Lo que hacemos en este trabajo es definir los autómatas afines. La idea surgió de un comentario que hice en una charla que dio Abuzer en mi grupo acerca de los autómatas cuánticos. La ganancia computacional que tenían estos autómatas parecía venir exclusivamente de las amplitudes negativas, entonces surgió la pregunta de si podríamos tener el mismo poder computacional simplemente usando un autómata probabilista con "probabilidades" negativas. Y así llegamos a las transformaciones afines: la idea es que un estado está representado por un vector cuyas componentes suman uno, sólo que no pedimos que sean positivas (como en un autómata probabilista). Luego usamos transformaciones afines (que mantienen la suma a uno) como matriz de transición. El resultado fue sorprendente ya que en el caso determinista, resultó ser más poderoso que los autómatas finitos cuánticos (y en el caso no determinista, igual).

Dejaré los slides una vez lo prepare para el simposio (que es en San Petersburgo del 9 al 13 de junio). Update: Aquí están.

Cabe aclarar que Abuzer es el especialista en autómatas (igual que Marcos Villagra, co-autor de este blog), mi campo principal es el cálculo lambda y la teoría de tipos... pero estuvo buena esta colaboración y espero ir aprendiendo más del tema.

Comenzando actividades

Hace casi un año que me mudé de vuelta a Asunción para iniciar mis actividades académicas. Me dijeron que el primer año resultaría duro y lo fue. Especialmente después de haber vivido casi ocho años en Japón y volver a acostumbrarme a mi propia cultura fue lo más difícil. Hasta este momento nunca me había dado cuenta de lo aculturado que estaba a Japón.

Actualmente estoy realizando un cambio en mis estudios y estoy aprovechando estos nuevos aires para incursionar en complejidad algebraica. Es un área de estudio que me siempre me provocó curiosidad y siempre disfruté estudiar. Ahora es una buena oportunidad para comenzar en esto. No significa que voy a dejar la computación cuántica, sino más bien, sería como un refuerzo que actuaría en sinergía con la computación cuántica. Los mismos conceptos aparecen en ambos como los tensores, los polinomios, y por supuesto, el álgebra abstracta.

Este año voy a estar muy concentrado en crear un grupo de investigación en teoría de la computación, el cual es un área (según mi entendimiento) inexistente en el Paraguay. Solo estamos dos personas que hacemos investigación en teoría de la computación. Espero poder cambiar eso en un futuro.

Por lo tanto estoy buscando estudiantes de grado y postgrado interesados en hacer teoría de la computación, en particular, las áreas de complejidad algebraica, computación cuántica y complejidad computacional clásica. Hay oportunidades de beca para estudiantes a tiempo completo, y nuestro consejo de ciencia y tecnología local ofrece todos los años becas de postgrado. Además, nuestro programa de postgraduación en Ciencias de la Computación es muy bueno, con expertos en diferentes áreas como bioinformática, optimización, ingeniería, computación científica y otros.

Voy a ir reportando avances de como vamos organizando el grupo. No quiero prometer publicaciones en el blog cada cierto tiempo estecífico, pero si voy a intentar cada tanto hacer una actualización. Es increíble como antes teníamos como una entrada en el blog cada semana, pero luego de graduarme y empezar a trabajar se hizo muy difícil escribir.

Este es un buen momento para volver a escribir.

Rūsiņš Mārtiņš Freivalds 1942-2016

Hoy me llegó la triste noticia de que Rūsiņš Freivalds falleció. El fue un pionero de la teoría de autómatas y la complejidad computacional. Entre sus muchas contribuciones quisiera resaltar  el primer algoritmo que demuestra la superioridad de la computación probabilística sobre la determinística; el demostró que el lenguaje {0ⁿ1ⁿ | n≥0} puede ser reconocido por un autómata probabilístico. También, fue el descubridor de un algoritmo asintóticamente óptimo para verificar la multiplicación de matrices, conocido como el Algoritmo de Freivalds. 

Tuve el placer de conocerlo y escuchar en varias ocasiones sus historias sobre como hacían investigación en la antigua unión soviética, del cual Latvia (o Letonia en español) fue parte. Siempre que él iba a alguna conferencia estaba acompañado de sus muchos estudiantes. En los últimos años sus trabajos se centraron en un modelo de computación basado en números p-ádicos. Aunque aparenta ser un modelo muy extraño, es una generalización muy natural y muy interesante.