14 de abril de 2016

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

27 de febrero de 2016

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.

16 de febrero de 2016

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


Pueden bajar un preprint de arXiv. La versión publicada será un poco más corta por límites de espacio.

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

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.