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.