17 de junio de 2016

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.

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.