10 de enero de 2012

Back Online!

Bueno, ya era hora de escribir algo de vuelta. Mucho pasó desde la última entrada. En particular, el fantástico anuncio de CERN sobre sus últimos experimentos en búsqueda del bosson de Higgs. Alguno siempre me pregunta por qué es tan importante descubrir esa partícula. Yo trato de explicar en los términos que yo entiendo, porque no soy físico. Este vídeo es fabuloso. Mejor que esto ya no se puede explicar. Es un poco largo.



Después también la conferencia QIP 2012 que se llevó a cabo en Montreal en diciembre. Lástima que este año no colgaron los videos en la página web como en años anteriores. Aún así, hay un excelente resumen en The Quantum Pontiff.

También, los últimos avances después de más de 20 años en multiplicación de matrices bien reportado en Shtetl Optimized.

Lo que me mantuvo ocupado, en especial los últimos 2 meses, es el nuevo paper en el que estaba trabajando. De hecho, ya había dado un pista en este post anterior. Es sobre una nueva técnica para encontrar cotas inferiores para protocolos de comunicación cuántica. En este post había explicado el modelo de comunicación. Bueno, después de mucho, mucho (y mucho) trabajo, por fin pude hacer lo que me propuse.

Uno de los problemas principales en esta área era demostrar un gap en la complejidad para modelos de comunicación con 3 o más jugadores. Un gap quiere decir, encontrar alguna función que clásicamente requiera ≥ X recursos computacionales (tiempo, espacio, etc), y quánticamente requiera a lo más estrictamente menor que X recursos computacionales. Por ejemplo, en búsqueda no-estructurada sabemos que clásicamente requerimos Ω(n) accesos a un oráculo, pero O(√n) accesos a un oráculo cuántico. Entonces acá hay un gap cuadrático.

En el caso de comunicación entre 2 jugadores, ya tenemos varios gaps exponenciales y cuadráticos. Para 3 o más jugadores no teníamos nada. Y de hecho este es un problema bastante difícil, principalmente porque las ténicas para cotas inferiores en modelos clásicos de multiparty communication son generalmente muy débiles, i.e., las cotas inferiores no son óptimas, y muchas veces están lejos de ser óptimas. Entonces ¿cómo hacer para demostrar un gap en comunicación multiparty? El truco está primero en relajar el modelo, por ejemplo, en lugar de considerar modelos de comunicación con bounded-error, considerar un modelo no-determinístico. Segundo, tener una nueva técnica.

Eso fue lo que hice en este trabajo. Primero consideramos un modelo de comunicación no-determinístico, y acotamos por arriba y por abajo utilizando el concepto de tensor rank. Esto luego lo aplicamos al problema de multiplicación de matrices y pudimos sacar un gap super-polinomial, el primero en multiparty communication.

Generalmente estos modelos no-determinísticos no son realistas, pero muchas veces se usan para hacer predicciones en modelos reales. Por ejemplo, P vs NP, i.e., tiempo determinístico vs tiempo no-determinístico. En este trabajo también hicimos algunas aplicaciones a comunicaciones cuánticas exactas, i.e., donde la respuesta se obtiene con probabilidad 1.

Al final lo mandé a una conferencia, y ahora estoy preparando la versión full para subir a arXiv y a ECCC y preparar la versión journal. Apenas lo tengo lo pondré aquí.

Actualización(14/Ene/2012): Aquí está la versión en ECCC.


8 comentarios:

  1. Hola primeramente felicitaros por vuestro fantastico blog. Soy estudiante de matematicas y todo este tema me parece apasionante. Mi pregunta es la siguiente, ¿tiene cabida un matematico en este mundillo de la computacion cuantica?y si la tiene ¿que tipo de trabajo haria?

    ResponderBorrar
    Respuestas
    1. Hola!

      Antes que nada, gracias por los elogios. Y ya que estamos aprovecho para agradecerle a Marcos quien es quien últimamente mantiene el blog (ya trataré de actualizar algo próximamente).

      Respecto a tu pregunta: claro que si! Hay muchos matemáticos trabajando en cuántica! En este momento se me ocurre como ejemplo los modelos categóricos de computación cuántica, aunque quizá eso sea más ciencias de la computación (justo en el delgado límite que la separa de la matemática). Si buscás grupos de investigación de computación cuántica en departamentos de matemática, verás que temas específicos trabajan.

      Por otro lado, yo me dedico a la lógica y el cálculo lambda, y aquí en Europa en algunos lugares eso lo hacen matemáticos y no cientistas de la computación.

      De todas maneras, he escuchado de grupos más 'puramente matemáticos', aunque no sabría decirte en que temas.

      Saludos,
      Alejandro

      Borrar
  2. Los matematicos pueden hacer de todo, en serio! Desde mecánica cuántica hasta economía y filosofía. Hay muchos matemáticos muy exitosos trabajando en computación cuántica. El primero que se me viene a la mente es Michele Mosca. Y no solo computación cuántica, todo en ciencias de la computación puede ser abarcado por un matemático. Solo tienes que encontrar lo que te gusta.

    ¿Cuál es la diferencia entre un matemático y un "theoretical computer scientist"? Yo no encuentro ninguna. Aunque los cientistas de la computación se centran más en combinatorica, lógica y algebra. Pero también conozco gente que trabaja en geometría y topología computacional, y aquí por ejemplo entran los números reales.

    ResponderBorrar
  3. ahora estoy de vacaciones en un hotel en buenos aires pero yo estudio matematicas en chile, mis felicitaciones por este blog!

    ResponderBorrar
  4. Hola, me encantó el blog! Felicitaciones :D. Soy estudiante de último año de Ingeniería en Sistemas de Información en la UTN (Argentina). Me gustaría saber en qué temas me tengo que especializar para poder dedicarme a investigar en computación cuántica, y si tengo posibilidades de hacer un postgrado en este tema (ya que lo veo más para los matemáticos y físicos). Gracias!

    ResponderBorrar
    Respuestas
    1. Hola,

      La verdad que no conozco mucho el perfil del ingeniero en sistemas (IS). En mi desconocimiento tengo la idea que están preparados para desarrollo de software a gran escala y el diseño de sistemas en general. Desde ahí es donde hablo (y si un IS no tiene nada que ver con la descripción anterior, no tomes en cuenta el resto).

      Aún así, la formación matemática imagino que es bastante fuerte, con lo cual podrías aprender lo que te falte. Quizá lo que podruas hacer en tus tiempos libres hasta que te recibas, es conseguirte el libro "Quantum Computation and Quantum Information" de Michael Nielsen e Isaac Chuang. Es una buena introducción al tema, y te da las herramientas básicas que quizá necesites.

      Luego de esa base, podrías buscar grupos de investigación que trabajen en diversos problemas cuánticos: desde teoría de juegos, pasando por los Quantum walks que hace Danny, hasta las cuestiones de modelos. Lamentablemente no conozco ningún grupo en argentina sobre esos temas, sólo conozco un par de físicos (trabajando en problemas netamente físicos), sin embargo hay alguna gente en Montevideo trabajando en teoría de lenguajes para cuántica y también en Brazil. Es importante que identifiques más o menos el área que te interesa. Después verás como acceder a un doctorado.

      Otra opción es venir a hacer un Máster a Europa sobre computación cuántica. Hay varios. El Master europeo es equivalente aL último año de la carrera de ingeniería (o a los 2 últimos si haces un Máster de 2 años). O sea, acá estudian 3 años de Licence, y luego 2 de Máster. Existen muchos programas de financiación para esta clase de estudios. Por ejemplo en Francia, tenés el sitio de CampusFrance que te da info de como conseguir esa financiación.

      Pero bueno, primero lo primero: tratá de conseguir el libro que te recomendé antes y fíjate cómo te va.

      Saludos!

      Borrar
  5. Estos son alguno investigadores en Latinoamérica.

    - Alejandro Romanelli (Universidad de la República, Quantum Walks) http://www.fing.edu.uy/if/nuclear/alejo.html

    - Salvador Vengas-Andraca (Tecnológico de Monterrey,Algoritmo Cuánticos) http://mindsofmexico.org/sva/

    - Fernando Brandao (Universidad de Minas Gerais, Quantum Infomartion y algoritmos cuánticos) http://www13.fisica.ufmg.br/~fgslb/index/aboutme.html

    ResponderBorrar
    Respuestas
    1. Excelente. Agrego un par más:

      - Juliana Vizzotto (Universidade Federal de Santa Maria, Lenguajes) http://www.inf.ufsm.br/~juvizzotto

      - Octavio Malherbe (Universidad de la República, Modelos)

      En Brazil en particular hay mucha gente.

      Borrar