Computación Cuántica

Banear Elsevier

2012-01-26T10:09:00.000-03:00

Les recomiendo este artículo en el blog de Tim Gowers (un medalla Fields y blogger), donde expresa su preocupación sobre las revistas de Elsevier y el apoyo de esta editorial a los proyectos de ley estadounidenses SOPA, PIPA y Research Works Act (esta última es un proyecto para prohibir las publicaciones científicas estadounidenses en revistas de libre acceso).

Hay una declaración de intención donde, hasta ahora, 460 científicos han (hemos!) dado su apoyo diciendo que o bien no van a publicar, o no van a hacer reviews, o no van a participar en la edición de revistas de esa editorial (o ninguna de las 3), hasta que cambie sus políticas. Se pueden ver algunas personalidades muy reconocidas entre los firmantes, como por ejemplo Jean-Louis Krivine, entre muchos otros.

Update: Agrego más cosas al post.

En el post de Tim Gowers menciona otros 3 puntos en contra de Elsevier, que resumidamente son:

1. Precios extremadamente elevados

2. La justificación de esos precios con que te tenés que suscribir a todas sus revistas en algún tema, o a ninguna (no podés elegir a qué revistas suscribirte)

3. Cuando una biblioteca trata de negociar el precio, Elsevier directamente les corta el acceso a todas sus publicaciones.

Y lo más importante: los papers los escriben científicos (no pagados por Elsevier), los referean los mismos científicos (tampoco se recibe retribución por eso) y en la mayoría de los casos, los editan los mismos científicos, también gratuitamente. Porqué Elsevier luego les vende las publicaciones a las mismas instituciones que pagan a esos científicos? Pues no tiene sentido alguno. Hace mucho tiempo, el trabajo de Elsevier era distribuir las publicaciones, así llegaba a las distintas universidades y centros de investigación. Hoy en día, con Internet, no sólo es innecesario su trabajo, es contraproducente, ya que quien no haya pagado el acceso, no puede acceder a la publicación (y Elsevier en particular tiene reglas muy duras en cuanto a no permitir a los autores poner una copia gratuitamente en la web).

Por eso están proliferando cada vez más las publicaciones de libre acceso, como por ejemplo Logical Methods in Computer Science (hay muchas más, sólo menciono el ejemplo más relevante a mi trabajo), que cuenta con un cuerpo editorial del más alto nivel en el área, tiene un proceso de review muy riguroso, y la publicación se hace online, de libre acceso y con licencia Creative Commons. Hay muchísimas revistas, en casi cualquier área de la ciencia, de acceso gratuito. Aquí dejo un sitio que se encarga de listarlas.

Y la pregunta obligada es: Realmente necesitamos a Elsevier?

Logic and interactions 2012

2012-01-19T09:55:00.000-03:00

Desde el 30 de Enero al 2 de Marzo, se llevará a cabo en la ciudad de Marsella (Francia) el evento Lógica e interacciones. Se trata de un evento de 5 semanas que reunirá investigadores en muchas áreas de lógica computacional.

En particular la cuarta semana, del 20 al 24 de Febrero, estará dedicada a "Enfoques Cuantitativos". Los organizadores de dicha semana son Michele Pagani, Simon Perdrix, Peter Selinger y Christine Tasson. Habrá cursos dictados por Thomas Ehrhard, Elham Kashefi, Prakash Panangaden y Christine Tasson. Además se contará con numerosos oradores invitados de renombre, y algunas contribuciones. Yo envié una contribución, la cual fue aceptada y la presentaré el ~~martes 21 a las 15:30~~ jueves 23 a las 11:20. Aquí dejo los datos de mi presentación (la versión en inglés la pueden consultar en la página):

Título:
Tipage vectorial

Resumen (traducción):

Los cálculos lambda algebraicos son extensiones al cálculo lambda donde las combinaciones lineales de términos, son también términos. Estos cálculos pueden verse como un marco para expresar programas probabilísticos, baricéntricos, cuánticos y no-determinísticos. Más generalmente, operadores lineales y vectores pueden expresarse naturalmente en este entorno. El sistema de tipos Vectorial, en su variante à la Church, es un sistema que se ubica sobre el cálculo lambda algebraico lineal, poniendo en relieve esos operadores lineales y mostrando la estructura de los vectores formados por la forma normal de los términos. En este sistema se pueden expresar programas cuánticos. Aunque ya hemos encontrado la conexión de Curry-Howard de un fragmento del sistema con la lógica proposicional de segundo orden, aún queda un trabajo por hacer para encontrar la lógica detrás del sistema completo. En esta charla presentaré el sistema de tipos Vectorial (un trabajo en conjunto con B. Valiron y P. Arrighi), el isomorphismo de Curry-Howard de la parte aditiva (trabajos conjuntos, uno con B. Petit y otro con G. Dowek) y daré algunas pistas de direcciones futuras para encontrar la "lógica vectorial", una lógica que tendrá programas cuánticos, probabilísticos y no-determinísticos como pruebas.

Preparación para SODA 2012

2012-01-15T23:04:00.000-03:00

El martes 17 de enero comienza SODA'12 en Kyoto. El hotel tiene muy linda pinta. Queda más o menos a 1 hora de camino desde donde vivo, asi que pienso ir y venir durante los 3 días que dure. Voy a intentar hacer un mini-reporte sobre los 3 días más adelante. Además voy a llevar mi super cámara Nikkon.

Voy a estar principalmente enfocado en las presentaciones sobre comunicación. Hay algunas muy interesantes también relacionadas a streaming. Sobre computación cuántica solo va a haber una presentación de Francois Le Gall sobre multiplicación de matrices.

Para el viaje en tren de 1 hora (2 horas ída y vuelta), me estoy llevando el libro Algebraic Complexity Theory.

Back Online!

2012-01-10T05:27:00.000-03:00

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.

Dick y Ken entrevistan a Kurt Gödel

2011-10-31T23:31:00.000-03:00

Muy buen entrada en el blog Gödel's Lost Letter and P=NP. Vale la pena leerlo.

QIP 2012

2011-10-30T23:01:00.000-03:00

Los papers de QIP 2012 y el programa ya están listos! Pueden ver en este link. Siempre QIP tiene papers de muy alta calidad. Por algo es la mejor conferencia en nuestra área. Quiero destacar algunos papers:

Merkle Puzzles in a Quantum World. Gilles Brassard, Peter Hoyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, Louis Salvail.

Está como featured talk, y es un paper escrito por mi gran amigo Kassem. Un excelente trabajo con una gran aplicación en un problem natural del método del adversario negativo. Este trabajo también lo presentaron en CRYPTO'11.
Local quantum circuits are appoximate polynomial-designs. Fernando Brandao, Aram Harrow, Michal Horodecki.

Fernando es de Brasil, y es profesor asistente en la Universidad de Minas Gerais. Aún no tuve el placer de conocerlo, espero poder hacerlo y charlar un poco sobre el interés que hay en Brasil y latino-américa en computación cuántica.
Improved Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication. Francois Le Gall.

Francois es un colega de la Universidad de Tokyo. Su paper es fabuloso, mejorando el paper de Harry Buhrman y Robert Spalek basado en quantum walks. Francois utiliza una reducción a triangle finding, que al mismo tiempo está basado nuevamente en quantum walks. Este paper también lo va a estar presentando en SODA'12 que será en Kyoto.

Quantum Information and Foundations StackExchange Proposal

2011-10-29T20:01:00.001-03:00

[Este post es en inglés, ya que se trata de crear un sitio en inglés]

I just copy and paste an email from the quantum-foundations mailing list.

Dear fellow researchers:

We hope you can all join us in building a new web-based research community for quantum computing, information and foundations on StackExchange, and possibly earn some social media reputation points while they're at it (good for bragging rights, at least).

StackExchange is a collection of web sites where users can ask questions of a technical nature and receive high-quality answers from their communities. We hope to use StackExchange to coordinate expertise and facilitate research in the quantum information and quantum foundations communities, and so we have created a proposal for a new site dedicated to doing just that. StackExchange has already been found to be highly useful in pure mathematics [1], theoretical computer science [2], and applied [3] and theoretical physics [4], but our proposal addresses that quantum information and foundations lie frustratingly between these fields, and thus each of these existing sites excludes many excellent contributors.

If you're new to the idea of a StackExchange site, here's some examples of StackExchange sites being used in practice to help make it more clear what we're trying to build up:

- http://mathoverflow.net/questions/77985
- http://cstheory.stackexchange.com/questions/6085/shors-factoring-algorithm-help
(Peter Shor himself answered this one!)
- http://cstheory.stackexchange.com/questions/990/can-we-quantify-the-degree-of-quantumness-in-a-quantum-algorithm
- http://physics.stackexchange.com/questions/3777/informational-capacity-of-qubits-and-photons
(Shor answered this one, too.)
- http://physics.stackexchange.com/questions/15482/how-do-i-calculate-the-position-on-the-bloch-sphere-of-a-quantum-gate-with-a-giv
(even fairly basic questions are OK)
- http://physics.stackexchange.com/questions/11702/how-could-a-particle-be-isolated-to-avoid-decoherence
(Yep, Shor.)
- http://theoreticalphysics.stackexchange.com/questions/370/rigorous-security-proof-for-wiesners-quantum-money
(Asked by Scott Aaronson and answered by Daniel Gottesman.)
- http://theoreticalphysics.stackexchange.com/questions/93/models-of-neutrinos-consistent-with-operas-results

If you are interested in helping make this proposal happen, you can help by submitting example questions to the proposal site [5], and later joining in the private beta once it goes live. Remember, the more people that join in, the more useful the site will become! Currently, we need 15 new users for the proposal to go live, so your help is definitely appreciated. Thanks for reading! We hope to see you on StackExchange soon!

Sincerely,

Chris Ferrie
Chris Granade

Links:
[1] http://mathoverflow.net/ (Not actually an SE site, but very similar!)
[2] http://cstheory.stackexchange.com/
[3] http://physics.stackexchange.com/
[4] http://theoreticalphysics.stackexchange.com/
[5] http://area51.stackexchange.com/proposals/36039/quantum-information-and-foundations

Otro pionero de la computación nos deja

2011-10-25T21:19:00.000-03:00

Primero Steve Jobs, depués Dennis Ritchie, y ahora John McCarthy. El fue uno de los iniciadores de la inteligencia artificial. De hecho, él fue la persona quien acuñó ese término. Además fue el creador del primer lenguaje funcional LISP. También fué ganador del premio Turing 1971.

Recuerdo que una vez cuando estaba comenzando en la universidad, le había enviado un email a John McCarthy con algunas preguntas. Ya ni recuerdo sobre que le escribí, pero no recibí ninguna respuesta.

Poster: Foro Digiteo

2011-10-18T16:45:00.001-03:00

En octubre comencé un postdoc financiado por el consorcio Digiteo.
Hoy se realizó el Foro Anual de Digiteo, donde se muestran los proyectos en los cuales han invertido. Por lo tanto, tuve que presentar un poster allí explicando mi proyecto. Aquí les dejo el poster en PDF para descargar.

Mayoritariamente, los proyectos financiados por Digiteo son de aplicación inmediata (mucho de robótica, visión, ciudades inteligentes, etc), pero todos los años financian algún que otro proyecto teórico, como el mío. Grata fue la sorpresa de encontrarme con un trabajo de "Practical" Quantum Coin Flipping!

Video de la defensa de mi tesis

2011-09-28T06:19:00.002-03:00

Como mencioné en un post anterior, el viernes 23/09/11 defendí mi tesis. La universidad puso el video de la defensa (sólo la parte de presentación, sin las preguntas del jurado). Así que aquí les dejo el video y otra vez los slides y el manuscrito:

Du typage vectoriel

Slides - Manuscript - Video

Terminando una etapa

2011-09-26T17:09:00.001-03:00

El viernes pasado defendí mi tesis titulada "Du typage vectoriel" (sobre el tipage vectorial). El abstract ya lo puse en otro post. Aquí les dejo los slides que usé para defender la tesis y la tesis en sí.

Hoy fui a la oficina a sacar todas mis cosas, ya que en este momento estoy en plena mudanza a París, porque el martes que viene empiezo un contrato de investigación de un año en la Université de Paris-Nord, de lo cual cuento más en este post.

Y bueno, como toda etapa que termina, viene la nostalgia... y quería recordar en este blog cuando vine a Grenoble por primera vez, cuando me dieron la beca, y cuando comencé esta aventura... simplemente: Gracias a tantos lectores que mantienen vivo este blog! Espero poder seguir comentando sobre mis investigaciones en lambda cálculo, teoría de tipos y un poquito de cuántica... y para los amantes de la cuántica por suerte tenemos ahora un verdadero "cuántico" que espero los mantendrá actualizando :)

Hasta la próxima!

Update: El video de la defensa está disponible aquí.

Alán Aspuru-Guzik en "La oveja eléctrica"

2011-09-17T13:05:00.001-03:00

Les dejo un programa mexicano de divulgación científica llamado "La oveja eléctrica", con un reportaje a Alán Aspuru-Guzik,

Soutenance / Defence / Defensa + QuAND

2011-09-13T11:10:00.001-03:00

(English) (Español)

J'ai le plaisir de annoncer ma soutenance de thèse, accompagné d'un rencontre QuAND, qui aura lieu le 23 septembre à Grenoble. Voici le programme, les infos pratiques et les détails de la thèse.

PROGRAMME :

10h - 11h :
Réunion stratégique du projet QuAND (privé)
11h15 - 12h :
Exposé de Michele Pagani « Working for a theory of algebraic abstract reduction systems »
12h - 14h :
Pause repas
14h30 - 16h :
Soutenance de thèse d'Alejandro Díaz-Caro : « Du typage vectoriel »
16h :
Pot de thèse

INFOS PRATIQUES :

Voilà un petit carte http://g.co/maps/rc8dc et quelques renseignements :
Depuis la gare vous pouvez prendre le Tram B direction « Plaine des sports » et descendre à l'arrêt « Bibliothèques universitaires ».
Le rencontre QuAND aura lieu à la Salle Aquarium, et la soutenance dans l'Amphi du MJK ( Maison Jean Kuntzmann ) même que le pot de thèse.

DÉTAILS DE LA THÈSE :

Titre :

Du typage vectoriel
Par :

Alejandro DÍAZ-CARO
Directeur :

Pablo ARRIGHI
Co-directeur :

Frédéric PROST

Cette soutenance aura lieu Vendredi 23 Septembre 2011 à 14h30 devant le jury composé de :

Rapporteurs :
Gilles DOWEK
Directeur de recherche - INRIA Centre Paris-Rocquencourt
Thomas EHRHARD
Directeur de recherche CNRS - Laboratoire Preuves, Programmes et Systèmes
Eduardo BONELLI
Profesor Asociado et Investigador Adjunto - Universidad Nacional de Quilmes et CONICET

Examinateurs :
Philippe JORRAND
Directeur de Recherche Émérite - CNRS
Laurent REGNIER
Professeur - Université de la Méditerranée
Lionel VAUX
Maitre de Conférences - Université de la Méditerranée
Michele PAGANI
Maitre de Conférences - Université de Paris Nord

Directeur de thèse :
Pablo ARRIGHI
Maitre de Conférences - Université de Grenoble

Résumé de la thèse :
L'objectif de cette thèse est de développer une théorie de types pour le λ-calcul linéaire-algébrique, une extension du λ-calcul motivé par l'informatique quantique. Cette extension algébrique comprend tous les termes du λ-calcul plus leurs combinaisons linéaires, donc si t et r sont des termes, α.t+β.r est aussi un terme, avec α et β des scalaires pris dans un anneau. L'idée principale et le défi de cette thèse était d'introduire un système de types où les types, de la même façon que les termes, constituent un espace vectoriel, permettant la mise en évidence de la structure de la forme normale d'un terme. Cette thèse présente le système Lineal , ainsi que trois systèmes intermédiaires, également intéressants en eux-même : Scalar, Additive et λCA, chacun avec leurs preuves de préservation de type et de normalisation forte.

I am happy to announce that my thesis defence, accompanied of a QuAND meeting, will be held on September 23 at Grenoble. Here you are the programme, the venue and the thesis details.

PROGRAMME:
10h - 11h:
Business meeting of the QuAND project (private)
11h15 - 12h:
Seminar by Michele Pagani "Working for a theory of algebraic abstract reduction systems"
12h - 14h:
Lunch
14h30 - 16h:
Alejandro Díaz-Caro's thesis defence: "On vectorial typing"
16h:
Drinks

VENUE:

Here is a map http://g.co/maps/rc8dc and some details:
From the train station, you can take the Tram B in direction "Plaine des sports", and take off at the stop "Bibliothèques universitaires".
The QuAND meeting will be held at the Aquarium room, and the defence at the lecture hall of the MJK building (Maison Jean Kuntzmann), same as the drinks afterwards.

DETAILS OF THE THESIS:

Title :

On vectorial typing
By:

Alejandro DÍAZ-CARO
Adviser:

Pablo ARRIGHI
Co-adviser:

Frédéric PROST

The defence will take place on Friday, September 23, 2011 at 2:30 pm in front of the following jury:

Rapporteurs:
Gilles DOWEK
Directeur de recherche - INRIA Centre Paris-Rocquencourt
Thomas EHRHARD
Directeur de recherche CNRS - Laboratoire Preuves, Programmes et Systèmes
Eduardo BONELLI
Profesor Asociado and Investigador Adjunto - Universidad Nacional de Quilmes et CONICET

Examinateurs:
Philippe JORRAND
Directeur de Recherche Émérite - CNRS
Laurent REGNIER
Professeur - Université de la Méditerranée
Lionel VAUX
Maitre de Conférences - Université de la Méditerranée
Michele PAGANI
Maitre de Conférences - Université de Paris Nord

Thesis adviser:
Pablo ARRIGHI
Maitre de Conférences - Université de Grenoble

Thesis abstract:
The objective of this thesis is to develop a type theory for the linear-algebraic λ-calculus, an extension of λ-calculus motivated by quantum computing. This algebraic extension encompass all the terms of λ-calculus together with their linear combinations, so if t and r are two terms, so is α.t + β.r, with α and β being scalars from a given ring. The key idea and challenge of this thesis was to introduce a type system where the types, in the same way as the terms, form a vectorial space, providing the information about the structure of the normal form of the terms. This thesis presents the system Lineal, and also three intermediate systems, however interesting by themselves: Scalar, Additive and λCA, all of them with their subject reduction and strong normalisation proofs.

Me es un placer anunciarles que mi defensa de tesis, acompañada de un encuentro QuAND, será el 23 de Setiembre en Grenoble. Aquí tienen el programa, las informaciones prácticas y los detalles de la tesis.

PROGRAMA:

10h - 11h:
Encuentro de trabajo del proyecto QuAND (privado)
11h15 - 12h:
Charla de Michele Pagani "Working for a theory of algebraic abstract reduction systems"
12h - 14h:
Almuerzo
14h30 - 16h:
Defensa de tesis de Alejandro Díaz-Caro: "Sobre el tipage vectorial"
16h:
Brindis

INFORMACIÓN PRÁCTICA:

Aquí hay un mapa http://g.co/maps/rc8dc y algunos detalles:
Desde la estación de trenes, pueden tomar el Tram B en dirección "Plaine des sports", y bajarse en la parada "Bibliothèques universitaires".
El encuentro QuAND será en la sala Aquarium, y la defensa en el anfiteatro del edificio MJK (Maison Jean Kuntzmann), al igual que el brindis.

DETALLES DE LA TESIS:

Título:

Sobre el tipage vectorial
Por:

Alejandro DÍAZ-CARO
Director:

Pablo ARRIGHI
Co-director:

Frédéric PROST

La defensa se llevará a cabo el viernes 23 de Setiembre de 2011 a las 14:30hs delante del jurado compuesto por:

Rapporteurs:
Gilles DOWEK
Directeur de recherche - INRIA Centre Paris-Rocquencourt
Thomas EHRHARD
Directeur de recherche CNRS - Laboratoire Preuves, Programmes et Systèmes
Eduardo BONELLI
Profesor Asociado e Investigador Adjunto - Universidad Nacional de Quilmes et CONICET

Examinateurs:
Philippe JORRAND
Directeur de Recherche Émérite - CNRS
Laurent REGNIER
Professeur - Université de la Méditerranée
Lionel VAUX
Maitre de Conférences - Université de la Méditerranée
Michele PAGANI
Maitre de Conférences - Université de Paris Nord

Director de tesis:
Pablo ARRIGHI
Maitre de Conférences - Université de Grenoble

Resumen de la tesis:
El objetivo de esta tesis es desarrollar una teoría de tipos para el λ-cálculo algebraico-lineal, una extensión de λ-cálculo motivada por la computación cuántica. Esta extensión algebraica comprende todos los términos del λ-cálculo y sus combinaciones lineales, de manera que si t y r son dos términos, α.t + β.r, con α y β escalares de un anillo dado, también lo es. La idea principal y el desafío de esta tesis ha sido introducir un sistema de tipos donde los tipos, de la misma manera que los términos, formen un espacio vectorial, proveyendo información acerca de la estructura de la forma normal de los términos. Esta tesis presenta el sistema Lineal, y también tres sistemas intermedios, aunque interesantes por ellos mismos: Scalar, Additive y λCA, todos ellos con sus pruebas de preservación de tipo y normalización fuerte.

Los nuevos pontífices

2011-08-18T22:53:00.001-03:00

El pontífice cuántico Dave Bacon se ha retirado para dar lugar a un grupo nuevo de pontífices: Steve Flammia, Charles Bennett, y Aram Harrow. Les deseo mucha suerte a sus santidades.

Comparto una imagen muy interesante de uno de sus recientes posts.

Video de Introducción a la Computación Cuántica

2011-08-09T21:53:00.003-03:00

Este es simplemente una de las mejores explicaciones de como funciona la computación cuántica. Video de Charlie Marcus.

Escuelas, conferencias, y otras cosas

2011-08-02T02:49:00.000-03:00

Hace mucho que debería haber escrito esta entrada, pero simplemente luego de mi viaje a Canadá se me acumuló un montón de trabajo.

Primero, la escuela canadiense en computación cuántica: 11th Summer School on Quantum Information. En general, estuvo genial! Los profesores eran todos investigadores reconocidos en su especialidad. En el área de ciencias de la computación cuántica tengo que destacar a Michele Mosca, Andrew Childs, Gilles Brassard, Renato Renner, y Daniel Gottesman. Todas sus clases estuvieron fabulosas. Las otras clases eran en teoría de la información, las cuales entendí regularmente bien, y en física, esto último más o menos. Fueron 2 semanas muy buenas en donde pude conocer gente de todo el mundo, y con quien pude hablar sobre computación cuántica con libertad, sin tener que explicar los porques ni dar razones de su estudio. Simplemente directo al asunto. En este enlace se pueden encontrar las notas de curso de todas las clases. El próximo año va a ser en IQC, uno de los mejores lugares del mundo para estudiar la materia.

Segundo, en agosto 23-27 se realiza AQIS 2011 en Busan, Korea. Voy a estar dando una presentación allí sobre el mismo tema que presenté en la escuela. El título del trabajo es: Quantum Query Complexity of Hamming Distance Estimation. Ya estaré subiendo una versión del paper en mi página web personal y arXiv.

Por último, estuve colaborando con Stasys Jukna en la correción (proofread) de su último libro que estará publicándose muy pronto. Solo leí 4 capítulos, pero está increíble! Sin duda será un éxito. Stasys tiene otro libro que es una joya en combinatorica: Extremal Combinatorics with Applications in Computer Science. Lo tengo aquí mismo, y siempre lo estoy consultando para cualquier problema que tenga. Recomiendo ese libro a cualquiera que esté interesado en cotas inferiores para algoritmos.

Mi interés está principalmente en técnicas de cotas inferiores para dos modelos de computación cuántica: árboles de decisión y protocolos de comunicación. Mis últimos trabajos estuvieron básicamente en la aplicación de técnicas conocidas a problemas específicos. Pero ahora quisiera realmente intentar desarrollar una técnica nueva en communication complexity. Para ello, estoy estudiando tensor rank. Quiesiera hacer mención de un muy lindo paper sobre esto que aparareció en el último CCC 2011: Tensor Rank Some Lower and Upper Bounds (arXiv:1102.0072). Además tiene un apéndice que explica muy bien varias propiedades de los tensores.

Postdoc: Proyecto ALAL

2011-07-21T12:13:00.006-03:00

Como anuncié en un post anterior, se aproxima mi defensa de tesis: el 23 de Setiembre. A partir de Octubre comenzaré un postdoc en la Université de Paris-Nord (Paris XIII), un proyecto financiado por DIGITEO y la región Île-de-France. El responsable del proyecto de Michele Pagani, del Laboratoire d'Informatique de Paris Nord y el socio Gilles Dowek, director de uno de los 5 dominios de investigación del INRIA.

Título del proyecto:

ALAL: Algebraic approaches to lambda calculi

(Métodos algebraicos para cálculos lambda)

No voy a poner el proyecto entero acá, pero dejo el resumen corto (abajo la traducción al español)

The project focuses on formal foundations for language-based (especially static) techniques guaranteeing resource-related runtime properties of programs. The project belongs to the research area whose aim is to associate to a program a certiﬁcation assuring some speciﬁc properties. We will derive the tools and techniques for our investigation from the ﬁeld of logical proof-theory and semantics, with special interest in linear logic and λ-calculus. In particular, we will explore the new interactions between linear algebra and the formal methods approach to computation, recently arisen from the differential extension of linear logic and the algebraic λ-calculi. The expected result is a robust theoretical framework in which to develop static analysis and veriﬁcation tools for non-deterministic paradigms, such as stochastic systems, concurrent computation, quantum programming, etc.

Y aquí una traducción:

El proyecto se centra en los fundamentos formales de las técnicas basadas en lenguage (sobre todo estáticas) que garantizan propiedades de ejecución de los programas relacionadas con recursos. Este proyecto pertenece al área de investigación cuyo objetivo es asociar a un programa una certificación que garantice ciertas propiedades. Vamos a derivar las herramientas y técnicas de nuestra investigación del campo de la teoría de la demostración lógica y de la semántica, con especial interés en lógica lineal y cálculo lambda. En particular, vamos a explorar las nuevas interacciones entre álgebra lineal y enfoques de métodos formales recientemente surgidos a partir de la extensión diferencial de lógica lineal y de los cálculos lambda algebraicos. El resultado esperado es un framework sólido en el cual desarrollar herramientas de análisis estático y verificación para paradigmas no-determinísticos como sistemas estocásticos, computación concurrente, computación cuántica, etc.

LSFA (y QuAND!)

2011-07-21T10:01:00.002-03:00

Con Pablo Buiras, a quien estoy dirigiendo en su tesis de licenciatura (el equivalente a la tesis de master en el sistema de la Unión Europea) y Mauro Jaskelioff, su codirector, hemos escrito un paper basado en la tesis de Pablo, que fue aceptado en LSFA 2011. Será Pablo quien lo presente allí.

El paper aborda el problema de la confluencia del lambda cálculo algebraico lineal por medio de un sistema de tipos (el cual permite sólo términos fuertemente normalizables, lo que en conjunto con la confluencia local, nos da la confluencia del lenguaje). Este sistema de tipos puede verse como una extensión de Additive al cálculo completo o como una simplificación de Vectorial. Tiene la ventaja de que, al igual que Additive, sólo introduce sumas en los tipos, y no escalares como lo hace Vectorial, lo cual lo haría mucho más complejo y difícil de interpretar en otros sistemas conocidos. Además, da información aproximada de qué es lo que está pasando en el término: por ejemplo, si tenemos un término 2.1 M + 1.5 N donde M tiene tipo T y N tipo R, el tipo de esta combinación lineal de términos será T+T+R, dicho de otro modo, el tipo "aproxima las cantidades" de términos de cada tipo que están presentes en la combinación, tomando su parte entera.

El paper completo (el borrador, claro, aún tenemos tiempo para enviar la versión definitiva) lo pueden bajar de acá. Y el lunes pasado presenté el trabajo (con un cambio, ya que en mi presentación la normalización fuerte la derivo a partir de la normalización fuerte de Vectorial) en el encuentro del proyecto QuAND. Los slides de esa presentación están acá.

La versión definitiva del paper será publicada en el Electronic Proceedings in Theoretical Computer Science, una revista científica electrónica que suele publicar los anales de workshops y conferencias, y que tiene la particularidad de ser abierta: cualquiera puede descargarse sus artículos, no hace falta pagar por ello.

Habemus date definito : XXIII Septembris

2011-07-08T07:34:00.002-03:00

(English below)

Mi tesis titulada "Du typage vectoriel" (Del tipage vectorial) ha sido aceptada para ser defendida. Hemos fijado la fecha de la defensa para el 23 de septiembre. Aquí la traducción del resumen oficial.

El objetivo de esta tesis es desarrollar una teoría de tipos para el λ-cálculo algebraico-lineal, una extensión de λ-cálculo motivada por la computación cuántica. Esta extensión algebraica comprende todos los términos del λ-cálculo y sus combinaciones lineales, de manera que si t y r son dos términos, α.t + β.r, con α y β escalares de un anillo dado, también lo es. La idea principal y el desafío de esta tesis ha sido introducir un sistema de tipos donde los tipos, de la misma manera que los términos, formen un espacio vectorial, proveyendo información acerca de la estructura de la forma normal de los términos. Esta tesis presenta el sistema Lineal, y también tres sistemas intermedios, aunque interesantes por ellos mismos: Scalar, Additive y λCA, todos ellos con sus pruebas de preservación de tipo y normalización fuerte.

Aquí les dejo el anuncio oficial. El manuscrito no lo voy a hacer público hasta que no corrija la enorme cantidad de errores de tipeo que tiene.

My thesis entitled "Du typage vectoriel" (On vectorial typing) has been accepted to be defended. The Viva has been fixed for the 23th September. Here you are the official abstract:

The objective of this thesis is to develop a type theory for the linear-algebraic λ-calculus, an extension of λ-calculus motivated by quantum computing. This algebraic extension encompass all the terms of λ-calculus together with their linear combinations, so if t and r are two terms, so is α.t + β.r, with α and β being scalars from a given ring. The key idea and challenge of this thesis was to introduce a type system where the types, in the same way as the terms, form a vectorial space, providing the information about the structure of the normal form of the terms. This thesis presents the system Lineal, and also three intermediate systems, however interesting by themselves: Scalar, Additive and λCA, all of them with their subject reduction and strong normalisation proofs.

Here it is the official announcement. I won't make the manuscript public until I do not correct the huge amount of typos it has.

DCM 2011

2011-07-05T05:29:00.002-03:00

Luego de un período de larga ausencia del blog (me excuso con que estaba terminando de redactar mi tesis (la cual se encuentra en revisión por el jurado ahora)) vuelvo para comentarles que este domingo estaré presentando un paper en el 7th International Workshop on Developments of Computational Models (el 3 de Julio, en Zúrich). El paper es un trabajo en conjunto con Pablo Arrighi y Benoît Valiron, el cual presenté antes en algunos encuentros informales y ahora fue aceptado para ser publicado en los proceedings de este workshop.

Les dejo los detalles originales en inglés y debajo la traducción.

A type system for the vectorial aspects of the linear-algebraic lambda-calculus

(joint work with Pablo Arrighi and Benoît Valiron)

We describe a type system for the linear-algebraic lambda-calculus. The type system accounts for the part of the language emulating linear operators and vectors, i.e. it is able to statically describe the linear combinations of terms resulting from the reduction of programs. This gives rise to an original type theory where types, in the same way as terms, can be superposed into linear combinations. We show that the resulting typed lambda-calculus is strongly normalizing and features a weak subject-reduction.

Un sistema de tipos para los aspectos vectoriales del lambda cálculo algebraico lineal

(trabajo en conjunto con Pablo Arrighi y Benoît Valiron)

Describimos un sistema de tipos para el lambda cálculo algebraico lineal. El sistema de tipos tiene en cuenta la parte del lenguaje que emula operadores lineales y vectores, o sea, es capaz de describir estáticamente las combinaciones lineales de términos resultantes de la reducción de los programas. Esto conduce a una teoría de tipos original donde los tipos, de la misma manera que los términos, pueden ser superpuestos en combinaciones lineales. Mostramos que el cálculo tipado resultante tiene normalización fuerte y una versión débil de la propiedad de conservación de tipo.

Hasta que esté publicado (en EPTCS, de libre acceso), les dejo aquí los links:

~~Luego del workshop subiré aquí los slides de la presentación también~~.
Update (05/07/11): Aquí están los slides que presenté durante el workshop.

Poster para la escuela

2011-06-03T04:00:00.001-03:00

Este domingo me pongo en camino al 11th Summer School on Quantum Information & 8th Canadian Student Conference on Quantum Information, como lo mencioné en el post anterior.

Por lo tanto, aquí está el poster que voy a presentar allí (enlace). No es perfecto, siempre mi punto débil fue el diseño de posters y presentaciones. Pero, es lo suficientemente bueno para transmitir la idea, lo cual es lo más importante.

No creo que vaya a escribir durante mi estadía allá, pero si seguramente estaré dando algunos avisos por el twitter. Al regresar voy a escribir sobre mis impresiones. Después de más de 3 años por Asia, voy a volver a un uso horario Americano.

Ahh, si a alguien le interesa el tema de investigación del poster, dejen un comentario, y puedo explicar sobre que es. Básicamente, son dos cotas superiores en una generalización de la distancia de Hamming. Como aún es un trabajo en progreso, sigo buscando las cotas inferiores para el problema. A ver si puedo conseguir un poco de feedback en la escuela.

Ultimos eventos

2011-05-15T08:11:00.002-03:00

Hace mucho tiempo que ya no escribía nada en el blog. No tengo excusas, aunque si he estado muy ocupado (reductio ad absurdum). Escribir papers, tesis y otras cosas endiabladas hizo que me olvide un poco del blog. Pero voy a volver a tomar el ritmo de antes, más o menos 2 posteos al mes.

La última entrada que escribí es el CFP de AQIS 2011. Muy linda conferencia, yo fuí el año pasado y me encantó. Este año me gustaría ir, pero creo que no. Tengo otros planes. Uno de ellos es que voy a Canadá por 2 semanas al 11th Summer School on Quantum Information & 8th Canadian Student Conference on Quantum Information. Echenle un vistazo al programa y verán que muchos expertos en el área estarán dictando clases. Estoy muy ansioso por participar de esta escuela desde hace mucho tiempo. Alejandro ya fué y le gusto mucho. También voy a estar presentando un poster, y apenas lo tenga listo lo pondré aquí en el blog. Es sobre un problema que me tiene enganchado desde hace mucho tiempo, sobre estimación de edit distance pero utilizando quantum queries. Ya más adelante daré más detalles.

Otra cosa, ya están los papers de ICALP 2011. Muy buen nivel este año aparentemente y promete mucho. También no se olviden de ISAAC 2011. Todavía hay tiempo para enviar, va a ser en Yokohama. Y por último SODA 2012 aquí en Kyoto. Con o sin paper, definitivamente voy a ir!!

AQIS 2011 CFP

2011-05-11T22:46:00.000-03:00

You are cordially invited to submit your precious research papers to AQIS11,
which will be held in Busan, Korea.

http://newton.kias.re.kr/aqis11

is a tentative homepage for AQIS11 still under construction.
Busan is the second largest city of Korea and was the capital city of Korea during the Korean war. It is now one of the most favorite Korean places for the tourists with beautiful beach and movie business.

Important dates of AQIS11 are
Submission dead line: June 13, 2011
Acceptance notification: July 10, 2011
Final draft: July 31, 2011
Tutorials: August 23, 2011
Main conference: August 24-27, 2011
Workshops: August 29-30, 2011

λvec en QAPL 2011: los slides

2011-04-02T12:49:00.004-03:00

Hace un par de horas dí la charla sobre el sistema de tipos vectorial que había anunciado aquí, aquí (explicación del paper) y aquí (updated (λvec)) en el QAPL 2011.

Dejo los slides aquí ~~(más adelante los subiré a mi página web y cambiaré el link)~~.

@compucuantica

2011-03-23T08:52:00.003-03:00

Acabo de crear una cuenta twitter exclusiva para el blog: @compucuantica

Por ahora allí aparecerán actualizaciones de los posts cada vez que haya nuevos contenidos en el blog. Más adelante se verá si puede servir para algo más.

Para entretenerse

2011-03-10T20:30:00.001-03:00

Dejo dos videos muy interesentes. El primero es sobre el gran resultado del año pasado en complejidad computacional cuántica QIP=PSPACE, explicado por uno de los mejores, John Watrous.

El segundo es para mirar con una coca cola y papas fritas. Es sobre la mecánica cuántica de los viajes en el tiempo, explicado por uno de los grandes también en computacion cuántica, Seth Lloyd.

Talk @ École Polytechnique

2011-03-08T14:08:00.003-03:00

Mañana daré una charla en la École Polytechnique de Paris, invitado por el grupo COMÈTE del laboratorio LIX.

Aquí les dejo los detalles: http://www.lix.polytechnique.fr/comete/seminar/abs2011.php#DiazCaro11

Curso introductorio a topología: 1ra clase

2011-03-02T07:53:00.004-03:00

En el marco del grupo de estudio SELEN (SEmántica de LENguages), el cual es coordinado por Mauro Jaskelioff, de la Universidad Nacional de Rosario (UNR), Raúl Kantor ha comenzado a dictar un curso introductorio a topología, y lo han grabado y subido. Aquí les dejo el video, el cual no tiene desperdicio.

Curso Topología 1 from Mauro Jaskelioff on Vimeo.

Dr. Raúl Kantor

para SELEN 2011

24/2/2011

Raúl Kantor, doctor en matemática y más tarde abogado, fue el director de la carrera de Ciencias de la Computación en la UNR cuando yo la cursé, de hecho, él es uno de los fundadores de la carrera.

TEDxCaltech: Quantum Computing

2011-02-28T17:33:00.008-03:00

An interesting intervention of Scott Aaronson at the TED^x organized at Caltech

via La Consigna

Cotas inferiores para funciones booleanas simétricas

2011-02-27T10:32:00.000-03:00

Últimamente he estado estudiando una técnica para encontrar cotas inferiores para árboles de decisión basadas en polinomios. Básicamente, la función booleana se escribe como si fuera un polinomio, e.g. x1∧x2 se puede escribir como un polinomio en dos variables p(x1,x2)=x1⋅x2. Entonces el número de consultas al oráculo es exactamente el grado del polinomio. Para el ejemplo del and tenemos que este número es 2.

Bueno, hay un resultado en computación cuántica que dice que el número de consultas que hace un algoritmo a un oráculo cuántico está acotado por abajo por el grado de un polinomio de bajo grado que aproxima la función booleana. Este es el link al paper original que desarrolló la técnica.

Ahora consideremos la función threshold, donde Thrt(x)=1 si y solo si el número de 1s en x es mayor o igual a t, i.e. |x|≥t. La cota inferior reportada en muchos papers es de . Existe un teorema (Paturi 1992) basado en el método de los polinomios. Este teorema nos permite calcular la cota inferior para cualquier función booleana simétrica. Una función booleana f es simétrica, si dado cualquier entrada x, permutar el orden de los bits no cambia el valor de f(x). Claramente Thrt es simétrica.

Tengo una pregunta en Theoretical Computer Science Stack Exchange que está sin respuesta ya por unos días. Básicamente el problema es que la cota inferior para threshold indicada arriba no sigue en forma directa desde el teorema de Paturi.

Creo que voy a esperar unos días más, y si sigue sin respuesta voy a poner una recompensa. Pero si algún lector de este blog conoce la respuesta, le voy a estar muy agradecido :-)

QPL 08 y 09 en Electronic Notes in Theoretical Computer Science

2011-02-04T22:04:00.006-03:00

El primer paper internacional que publiqué, en el QPL 2008, finalmente apareció en Electronic Notes in Theoretical Computer Science. Los editores se demoraron un poco (bastante), pero finalmente publicaron los proceedings de este workshop.

Este paper fue la culminación de mi tesis de licenciatura, y lo escribimos con Pablo Arrighi (mi director de doctorado), Manuel Gadella (uno de mis directores de tesis de licenciatura) y Jonathan Grattage.

Y acá les dejo la cronología en el blog de este paper :)

Acá está el post de cuando lo enviamos.
Acá cuando nos avisaron que fue aceptado
Acá cuando mandamos la versión final.
Y finalmente, este post para la versión publicada :)

Y la cosa no queda allí, también los mismos editores enviaron los papers del QPL 2009! Allí encontrarán la primera versión de Scalar, en el siguiente número de ENTCS (esta es una versión de sólo 10 páginas, la versión de arXiv está mucho más completa). Este fue el primer paper durante mi doctorado, y como no podía ser de otra manera, la cronología también está reflejada en nuestro blog:

Aquí cuando fue aceptado,
y luego los slides de mi presentación y la versión arXiv.

2 nuevos: λFA y λvec

2011-02-03T19:29:00.008-03:00

El miércoles envié dos nuevos papers:

El primero está basado en la tesis de licenciatura, en progreso, de Pablo Buiras. El paper lo escribimos entre Pablo, Mauro Jaskelioff, y yo (sus directores). Pueden bajar el paper libremente del arXiv: arXiv:1102.0749.

El título del paper es

Lower bounds for scalars in a typed algebraic λ-calculus

(Cotas inferiores para escalares en un λ-cálculo algebraico tipado)

Acá copio el abstract y explico un poquito de qué se trata "en criollo".

The linear-algebraic λ-calculus is an untyped λ-calculus extended with arbitrary linear combinations of terms. As shown by previous works, building a type system on top of it is a delicate matter. A straightforward extension of a classic type system, like System F, would impose an undesirable restriction: it would only allow superpositions of terms of the same type. Adding sums of types lifts this restriction but raises the question of how to deal with the interaction between scalars and additions. We propose a type system with sums of types for the linear-algebraic λ-calculus which provides an answer to this question by allowing types to have some degree of imprecision. The proposed type system has a subject reduction property and is strongly normalising. Furthermore, we show that the additive fragment of the calculus can be seen as an abstract interpretation of the full calculus.

En lugar de traducir el abstract, explico un poquito la idea: En [DCP10] Barbara Petit y yo creamos un sistema de tipos, λadd, para el fragmento aditivo del linear-algebraic lambda-calculus [AD08] (λlin para abreviar). Luego mostramos que ese cálculo podía traducirse a System F con pares.

En el nuevo trabajo, extendemos ese resultado para el cálculo λlin completo: Primero creamos un sistema de tipos muy similar a λadd, pero para todo el cálculo: o sea, no sólo para lambda términos que se pueden sumar, como t+r, con t y r lambda términos, sino que también se pueden escalar: α.t+β.r, con α, β reales positivos. El sistema se llama λFA (por Full-Additive). La sintaxis de los tipos sigue siendo la misma que la de λadd : básicamente es Sistem F donde además se pueden sumar tipos. Y los escalares? Bueno, lo que hacemos es aproximarlos tomando su parte entera: si un término t tiene tipo T, el término α.t:⌊α⌋.T (nótese que ⌊α⌋ es un número natural y por tanto ⌊α⌋.T no es más que T+T+····+T, ⌊α⌋-veces). Como alguno ya inferirá, mezclar escalares y sumas no es nada sencillo, por ejemplo: 1/2.t+1/2.t tendría tipo ⌊1/2⌋.T+⌊1/2⌋.T = 0.T+0.T = 0, sin embargo si tomamos números mayores (por ejemplo, multipliquemos todo por 100), pues la precisión será muy buena... bueno, depende de lo que queramos decir por "muy buena", pero si no nos parece buena, pues agregamos más 0s al 100 :)

Probamos una especie de subject reduction para este sistema: básicamente lo que dice que se pierde precisión en los escalares al reducir el término, pero no en los tipos. O sea, si un término tiene tipo T+R+S+S, pues sabemos que al reducirlo (al "ejecutar el programa"), obtendremos un término con al menos los tipos T, R y dos veces S.

Además hicimos una prueba de strong normalisation: algo no sencillo ya que la prueba de Scalar [ADC09] no nos sirve porque en Scalar sólo se puede tipar t+r si t y r tienen el mismo tipo (módulo un escalar), por lo tanto el conjunto de términos no es el mismo. Tampoco se puede re-usar la de λadd, porque allí los escalares en los términos no existen (por lo tanto también tenemos otro conjunto de términos), así que hubo que hacer una prueba desde cero.

Por último, mostramos que λadd se comporta como una interpretación abstracta de λFA, y luego conjeturamos (con muchas pistas de que la conjetura es cierta), que System F con pares por extensión también es una interpretación abstracta de λFA.

-

El segundo paper es un trabajo con Pablo Arrighi y Benoît Valiron y es una extensión (o digamos, la continuación) de este. El título es:

A type system for the vectorial aspects of the linear-algebraic lambda-calculus

(Un sistema de tipos para los aspectos vectoriales del linear-algebraic lambda-calculus)

Abstract:

In this paper we describe a type system for the linear-algebraic lambda-calculus. The type system accounts for the part of the language emulating linear operators and vectors. The type system is able to statically describe the linear combinations of terms resulting from the reduction of programs. This gives rise to an original type theory where types, in the same way as terms, can be superposed into linear combinations. We show that the resulting typed lambda-calculus is strongly normalizing and features a weak subject-reduction.

Básicamente los cambios con respecto al viejo son: volvimos a agregar una regla de reescritura que habíamos quitado previamente (usando un truco para que ahora sí funcione), haciendo que el sistema sirva para todo el cálculo λlin, y lo más importante: λlin originalmente (el cálculo no tipado) podía encodear programas cuánticos. Ninguno de los sistemas de tipos en los que trabajé hasta ahora podía hacerlo, Scalar puede tipar programas con distribuciones baricéntricas, λadd podría pensarse como no determinista y λFA podrían ser usado para tipar programas probabilísticos, pero este es el primero que permite tipar los programas cuánticos propuestos en el paper original.

El cálculo se llama λvec (bueno, el nombre correcto sería ).

Aún no lo subimos al arXiv, pero lo que vamos a hacer es actualizar el anterior, ya que es su versión final (ah, por cierto, el anterior, que sería la versión "work-in-progress" de este, fue aceptado y lo vamos a presentar en QAPL 2011 (sólo como presentación, sin aparecer en los proceedings ya que es un work-in-progress)). ~~Cuando aparezca la versión nueva en arXiv pondré el link aquí~~. Lo pueden bajar de aquí: arXiv:1012.4032.

Novedad en el blog: Barra wibiya

2011-01-25T05:45:00.024-03:00

Buenas, este post es para comentarles que hemos agregado la barra wibiya al blog (la barrita que ven abajo). Aquí les describo las funcionalidades que tiene (por ahora, ya que se le pueden agregar cosas a gusto):

Aquí se muestra cuánta gente está viendo el sitio en este momento. Haciendo click muestra algunas estadísticas del sitio (de dónde vienen los últimos visitantes del sitio, por ejemplo).

Este botón sirve para lo que imaginan: traducir los posts a diferentes idiomas. Creo que puede ser útil sobre todo para post escritos sólo en inglés.

Pues eso: acceso directo y cómodo a los últimos posts.

Esta es mi funcionalidad favorita: Haciendo click aquí los lleva a un post cualquiera.

También tienen los botones típicos de las distintas redes sociales y un "+ compartir" para incluso más redes.

Acceso al RSS del blog. Para seguir el blog con algún lector de RSS (como por ejemplo el online Google Reader).

Para ver las últimas actividades en la "Fan Page" del sitio en Facebook. Lo interesante es que pueden verla sin necesidad de irse del blog.

Esta utilidad (obviamente: un chat) aún no estoy seguro de qué tan útil será, ya que 1) por lo general no hay mucha gente online al mismo momento en el blog y 2) hay que autorizar la aplicación en alguna red social para poder acceder al chat. Veremos si gusta o no.

Por último: un link a wibiya, por si a alguien le interesa para su propio blog, y una flechita para ocultar la barra por si a alguien le molesta.

Bueno, espero les guste la nueva funcionalidad.
Happy reading!

Videos from QIP 2011

2011-01-17T21:29:00.000-03:00

QIP2011 videos are online!! You can find them on this link.

I only watched one: Bo'az Klartag and Oded Regev, Quantum one-way communication can be exponentially stronger than classical communication. It presents a classical lower bound for a promise problem from linear algebra which the authors call Vector in Subspace Problem. Their lower bound is based on a very interesting geometric argument on the n-dimensional sphere. This result implies an exponential gap between one-way quantum and classical communication complexity.

Others that I would like to watch (which are related to my own interests) are:

Tsuyoshi Ito, Hirotada Kobayashi and John Watrous, Quantum interactive proofs with weak error bounds.
Loïck Magnin, Martin Roetteler and Jérémie Roland, On the additive and multiplicative adversary methods.
Jianxin Chen, Xie Chen, Runyao Duan, Zhengfeng Ji, Zhaohui Wei and Bei Zeng, On the solution space of quantum 2-SAT problems.
Andrew Childs and Robin Kothari, Quantum query complexity of minor-closed graph properties.

Enjoy the videos!!

Debate: Sobre-calificación?

2011-01-12T06:21:00.003-03:00

Este post no es técnico, sino más bien referido a la preparación que tenemos en Argentina (y a quien le quepa, hablo de Argentina porque es lo que conozco) y algunas ideas discutibles sobre qué tan necesarias son algunas cosas.

Lo primero que me sorprendió al llegar a Francia, no fue tanto la preparación de los investigadores de acá (la cual a modo general es muy buena), sino la edad de la gente: Mi director tiene prácticamente mi edad. Los estudiantes de doctorado comienzan a los 23 y a los 25 ya son doctores. Luego hacen un par de años de post-doc y pum, un cargo permanente... a los 28, 29 años.

En Argentina tendemos a querer hacer muchísimas cosas antes de recibirnos, lo cual está perfecto, pero lo hacemos en perjuicio de demorarnos varios años más para obtener el título (hablo del primer título, la licenciatura de 5 años en nuestro caso). Conozco casos de chicos que se han ido a hacer hasta 3 pasantías al extranjero, de al menos 6 meses cada una. Otros casos de tesis de licenciatura que llevan años. Otros que se ponen a dar clases y terminan dando tantas clases que no se reciben nunca.

Creo que lo ideal sería tratar de recibirse jóvenes, con la mayor experiencia posible... o sea: balancear la cosa. Por ejemplo: una pasantía de 6 meses puede ser muy valorada a la hora de buscar una beca doctoral. 3 pasantías es aceptar ser explotado con trabajo precarizado que nos demora el título. Una buena tesis de licenciatura nos ayudará también con el CV. Si incluye una publicación, pues tanto mejor (y puede ser una publicación post-tesis, no hay ningún problema con ello). 3 publicaciones antes de recibirse sería una exageración (y tomaría demasiado tiempo). Dar clases como ayudante de cátedra colabora con el CV. Dar 200 horas de clases al año es una exageración que nos demorará el título.

El modelo europeo es totalmente distinto al nuestro, acá se supone que uno comienza su carrera a los 18 años y para los 23 se recibió y comenzó el doctorado. Las carreras tienen mucho menos contenidos en general, ya que son mucho más especializadas, lo cual se puede hacer porque cuentan con muchísimos más cargos docentes. Por ejemplo, si queremos hacer una carrera orientada a la teoría de lenguajes, metemos muchas materias sobre el tema, quitamos otras no relacionadas al tema y dividimos la carrera en "Cs. de la Computación" y "Cs. de la Computación con orientación a la teoría de lenguajes". Eso implica que cada una tendrá menos alumnos y se necesitarán más cargos docentes. Algo difícilmente permisible en Argentina. Por lo tanto, es normal que nuestras carreras tengan tantos temas juntos, lo cual nos da una preparación mayor (más amplia) pero también nos lleva más tiempo terminarla. La cuestión está en no agregarle a eso, cosas innecesarias. Y que no se mal entienda, tampoco digo meterle pata a rendir todas las materias y exclusivamente eso y terminar sin haber hecho nada extra. Eso nunca es bueno tampoco. Lo que digo es tener un sano balance.

Bueno, este post pretende arrancar una discusión, no cerrar el tema, así que sientanse libres de comentar! Mi opinión no está cerrada sobre el tema, es algo que estoy reflexionando y quise compartir para reflexionar en grupo (de ser posible, comenten en el post y no en facebook, ya que en facebook la discusión se termina perdiendo).

Talk @ Paris 13

2011-01-06T15:14:00.011-03:00

(English version below)

El próximo 17 de enero daré una charla sobre los sistemas de tipos algebraicos en Paris 13 (Lab LIPN) en las series "Sémiraires LCR". Aquí está la información y aquí reproduzco el resumen:

En esta charla voy a presentar varias extensiones a System F, para tipar el lambda-cálculo lineal-algebraico, un lambda-cálculo enriquecido con una estructura vectorial. El primer sistema de tipos es una extensión directa de System F, el cual sólo tipa el cálculo sin más adorno. El segundo es un sistema de tipos que tiene en cuenta escalares, el cual puede servir como una garantía de que la forma normal de un término tiene forma con . El siguiente sistema incluye "suma de tipos" reflejando los de los términos -- mostrando que las sumas en el cálculo algebraico se comportan como una clase particular de pares. Finalmente el último sistema de tipos combina los dos anteriores. Damos contraejemplos de porqué este tipo de sistema de tipos vectorial no se puede hacer en estilo Curry y mostramos algunas pistas de un futuro sistema de tipos vectorial en estilo Church, adecuado para especializarlo en un cálculo cuántico.

Edit: Aquí dejo los slides.

Next January 17th I will give a talk about the algebraic type systems at Paris 13 (LIPN Lab) in the series "Sémiraires LCR". Here it is the information and I reproduce here the abstract:

In this talk I will present several extensions to the System F, for the sake of type the linear-algebraic lambda-calculus, a lambda-calculus enriched with a vectorial structure. The first type system is a straightforward extension of System F, which just types the calculus without any further adornment. The second one is a type system accounting for scalars, which can serve as a guarantee that the normal form of a term is of the form with . The following system includes "sums of types" reflecting that of the terms--showing that sums in the algebraic calculus behaves as a special kind of pairs. Eventually the last type system combines the previous two. We give counterexamples of why this kind of vectorial type system cannot be made in Curry style and show the clues of a future vectorial type system in Church style suitable to specialize the calculus into a quantum calculus.

Edit: Here are the slides.

Explicación del paper, legible por humanos.

2010-12-21T06:09:00.002-03:00

Ya apareció en arXiv el último paper que enviamos, y aprovecho para hacer una introducción más sencilla a él.

Para entender un poco más el contexto, les recomiendo este post donde doy una explicación no-técnica sobre el área. El presente post va a ser (obligatoriamente) un poquito más técnica, pero trataré de que lo sea lo menos posible. Voy a continuar con los ejemplos de ese post anterior, así que aún si ya lo leyeron, les recomiendo mirarlo de nuevo por arriba para refrescarlo.

Habíamos dicho que la idea era encontrar tipos para un lenguaje en particular para obtener de allí una lógica cuántica. El lenguaje con el que estoy trabajando es el "Linear-Algebraic Lambda-Calculus" (lambda-cálculo algebraico-lineal).

¿Porqué este lenguaje y no otro? Lambda-cálculo es el lenguaje más pequeño y universal que existe (pequeño == simple). Este cálculo algebraico-lineal lo que hace es permitir combinaciones lineales de términos, esto es, si M y N son dos términos de mi lenguaje, a.M+b.N con a y b escalares cualquiera, también es un término. Si lo pensamos desde lo más básico de la computación cuántica tenemos que 0 y 1 son bits y a.|0>+b.|1> es un qubit (aunque en este caso se pide cierta propiedad que a y b deben cumplir, a saber a y b son números complejos y |a|²+|b|²=1).

Así que este lenguaje se puede pensar como "cuántico" en el sentido de que se puede codificar programas cuánticos en él y que se puede "superponer" programas. Sin embargo, si consideramos a.M+b.N como superposición, entonces también podemos hacer superposiciones que no corresponden a programas cuánticos (cuando a y b no cumplan con las propiedades necesarias).

Ahora vamos a los tipos. Como decía en el post anterior, a cada programa (lambda-término en este caso, un término de nuestro lenguaje) le podemos hacer corresponder un tipo. Podemos considerar que si el término tiene un tipo que le corresponde, es un término válido, y sino, no lo es. Así que los tipos nos sirven en este caso para limitar el lenguaje como nosotros queramos.

¿Porqué querríamos limitar el lenguaje? Como dije anteriormente, el lambda-cálculo algebraico lineal es demasiado general y admite términos que no tienen interpretación cuántica, así que la idea es darle tipos para limitarlo y que sólo admita términos con una interpretación cuántica.

Entre todas las lógicas que mencioné en el post anterior, me interesan en particular las que tienen polimorfismo. Un ejemplo para entender qué es polimorfismo es la función identidad: Supongamos que tenemos un término lógico A, es fácil deducir que A implica A, en símbolos A=>A. Si tenemos otro término B, también podemos deducir B=>B. En general, si tenemos un término X podemos deducir que X=>X. Usando polimorfismo esto se escribe como ∀X.X=>X y se lee "para todo X, X implica X".

Desde el punto de vista del lenguaje estamos diciendo que si tenemos un término, digamos I, que se comporta como una función identidad, esto es: si recibe el término M devuelve el término M, entonces le vamos a dar el tipo ∀X.X=>X, o usando la notación del post anterior, I:∀X.X=>X. O sea: I es una función tal que si le damos un término de cualquier tipo, nos devuelve un término del mismo tipo. Entonces decimos que I es una prueba de que la fórmula lógica ∀X.X=>X (esto es "para todo X, X implica X") es correcta.

Entonces lo que queremos es un sistema de tipos tal que las únicas pruebas válidas, sean programas cuánticos.

Por lo tanto, tenemos que limitar, como dije anteriormente, los escalares que se usan para las combinaciones lineales de términos. Y eso lo queremos hacer con los tipos... ¡Entonces tenemos que incluir los escalares en los tipos! Pero con escalares sólos no nos basta, necesitamos también poder sumarlos, así que lo que necesitamos es básicamente que si un término M tiene tipo T y otro término N tiene tipo R, que el término a.M+b.N tenga tipo a.T+b.R. Y eso es lo que llamamos un sistema de tipos vectorial: un sistema en el cual dados tipos básicos, la combinación lineal de ellos es un nuevo tipo.

Para poder considerar un sistema lógico y programas como sus pruebas, necesitamos tener una propiedad llamada Subject Reduction (si alguien conoce el término que se usa en español, lo agradeceré). Esta propiedad es simple, dice que si un programa M tiene tipo T, el término N que se obtiene de ejecutar el programa, también tendrá tipo T. En este formalismo, ejecutar el programa M y obtener N se anota como "M→*N" y se lee "M reduce a N". Entonces Subject Reduction dice

Si M→*N y M:T, entonces N:T

Hay otras maneras de escribir los términos y los tipos. Hasta ahora estábamos escribiendo los términos en lo que se conoce como estilo Curry, en contraposición con el estilo Church. Un ejemplo: En el estilo Curry simplemente decimos que la función f aplicada a x tiene tipo A=>B de la siguiente manera, f(x):A=>B. En estilo Church el tipo es parte del término y diríamos algo como f^B(x:A):A=>B. Viendo el término ya tenemos el tipo, el tipo es parte del término.

Y ahora si, después de toda esta introducción puedo decir en forma relativamente corta qué es lo que probamos en este paper: El paper muestra que un sistema de tipos vectorial que incluya polimorfismo y esté expresado en estilo Curry, no tiene Subject Reduction. Y además, mostramos qué es lo más cercano a Subject Reduction que podemos tener, que es esto:

Si M→*N y M:T, entonces N:T' donde T' tiene una relación con T y si la forma de ejecutar el programa M para arribar a N no incluye una reducción en particular, entonces T' es simplemente T.

El preprint del paper está disponible aquí: arXiv:1012.4032.

New paper: Subject reduction in a Curry-style polymorphic type system with a vectorial structure

2010-12-17T21:07:00.005-03:00

(Versión en español más abajo)

New paper submitted, with Pablo Arrighi and Benoît Valiron.

Title: Subject reduction in a Curry-style polymorphic type system with a vectorial structure.
Abstract: The algebraic lambda-calculus [Vau09] and the linear-algebraic lambda-calculus [AD08] extend the lambda-calculus with the possibility of making arbitrary linear combinations of lambda-terms. The two foundational works of [ADC09] and [DCP10] describe type systems for this calculus respectively accounting for scalars and sums. Building on these approaches, we devise a typed algebraic lambda-calculus merging the two approaches while keeping a language featuring local confluence and a weak subject reduction. This gives rise to an original and general type theory where types, in the same way as terms, have a vector space-like structure. The main contribution of this paper is a subject reduction result, a problem renowned to be a delicate matter under the presence of union-like type constructs.

Basically the idea of the paper is to present the several-times an n o u n c ed "vectorial type system": we present here a type system with a non-standard subject reduction. We conclude that, in general, to have subject reduction in a vectorial type system we would need to move to Church-style.

I uploaded the paper to arXiv today, so it will appear next Tuesday. ~~I will put the link here~~. arXiv:1012.4032.

Nuevo paper enviado, con Pablo Arrighi y Benoît Valiron.

Título: Subject reduction (ni idea cómo se dice eso en español) en un sistema de tipos polimórfico à la Curry con una estructura vectorial.
Resumen: El lambda-cálculo algebraico [Vau09] y el lambda-cálculo algebraico-lineal [AD08] extienden el lambda-cálculo con la posibilidad de hacer combinaciones lineales arbitrarias de lambda-términos. Los dos trabajos fundacionales de [ADC09] y [DCP10] describen sistemas de tipos para este cálculo respectivamente teniendo en cuenta escalares y sumas. Construido sobre estos enfoques, elaboramos un lambda-cálculo algebraico fusionando ambos, logrando un lenguaje con confluencia local y una subject reducción débil. Esto da lugar a una teoría de tipos original y general donde los tipos, de la misma manera que los términos, tienen una estructura al estilo de un espacio vectorial. La principal contribución de este paper es el resultado de subject reduction, un problema reconocido como complicado en presencia de construcciones de tipo unión.

Básicamente la idea del paper es presentar el muchas veces an u n c i a do "sistema de tipos vectorial": lo que presentamos aquí es un sistema de tipos con un subject reduction no estándar. Concluímos que, en general, para tener subject reduction in sistemas de tipos vectoriales deberíamos pasarnos a Church-style.

Hoy subí el paper a arXiv, así que aparecerá el próximo martes. ~~Pondré el link aquí~~. arXiv:1012.4032. Y aquí una explicación más amena del paper.

Quantum Foundations Mailing List | Lista de correo "fundamentos cuánticos"

2010-12-09T15:06:00.003-03:00

(Versión en español más abajo)

Bob Coecke and Jamie Vicary have started a mailing list on "quantum foundations".

The announcement is the following:

It was agreed by many that the existence of a quantum foundations mailing list, with a wide scope and involving the broad international community, was long overdue. This moderated list (to avoid spam or abuse) will mainly distribute announcements of conferences and other international events in the area, as well as other relevant adverts such as jobs in the area. It is set up at Oxford University, which should provide a guarantee of stability and sustainability. The scope ranges from the mathematical end of quantum foundations research to the purely philosophical issues.

To subscribe to the list, send a blank email to:
quantum-foundations-subscribe@maillist.ox.ac.uk

To unsubscribe, a blank email to:
quantum-foundations-unsubscribe@maillist.ox.ac.uk

Bob Coecke y Jamie Vicary comenzaron una lista de correo en "fundamentos cuánticos".

El anuncio es el siguiente:

Se ha llegado al acuerdo entre muchos que la existencia de una lista de correo en fundamentos cuánticos, con un amplio alcance y gran participación de la comunidad internacional, es una deuda desde hace mucho. Esta lista moderada (para evitar el spam o abuso), principalmente distribuirá anuncios de conferencias y otros eventos internacionales en el área, así como otros anuncios pertinentes tales como puestos de trabajo en el área. Se instaló en la Universidad de Oxford, lo que debería ofrecer una garantía de estabilidad y sostenibilidad. El ámbito de la lista abarca desde el fin matemático de la investigación en fundamentos cuánticos hasta las cuestiones puramente filosóficas.

Para suscribirse a la lista, envíe un mail en blanco a:
quantum-foundations-subscribe@maillist.ox.ac.uk

Para desuscribirse, un mail en blanco a:
quantum-foundations-unsubscribe@maillist.ox.ac.uk

Communication complexity lower bounds

2010-11-30T10:57:00.086-03:00

I just discovered a spectacular survey article on communication complexity lower bounds. The paper is below.

Troy Lee and Adi Shraibman (2007) “Lower Bounds in Communication Complexity”,

Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263–399.

You can find a draft in Troy Lee's homepage.

Finished reading it, not with full details, but enough for understanding the bigger picture in the proof technique they use. Now I'm ready to read it for a second time, but this time going deeper into the details. First let's review the communication model. There are two players, Alice (A) and Bob (B), and they want to solve a problem together call it f which will be a boolean function. The input to f is divided between A and B, so in order to solve the problem they will need to communicate. The complexity is the minimum number of bits that need to be interchanged to solve the problem. The running time of A and B is not taken into account. All communication is defined by the communication matrix M, which is defined as M[x,y]=f(x,y), i.e. the rows and columns are indexed by the inputs to A and B, and each entry is the value of f. Changing the acceptance condition for the model we get a deterministic, randomized (two, one and zero-sided) or a nondeterministic model. If we allow the player to send qubits we get quantum. It can also be generalized to multiparty communication with all different flavors like the topology of communication, the way the parties access the input, etc.

Since communication complexity is more about lower bounds, all research is devoted to this. Upper bounds in this models are implied by upper bounds in the decision tree model. The general idea of proving lower bound is the following three steps procedure:

Embed the communication matrix onto the reals. This is done by a mapping from some operator norm to an euclidean norm.
Formulate the problem using the embedding as a maximization problem.
Give a witness for the objective function of the resulting program.

I would say that step 1 is the easiest because there is a lot of work done there, so you just need to choose the most fit for your problem. Although, there is still many open problems here to solve like the famous log-rank conjecture. The second step depends in the duality between the studied norms. The objective here is to avoid dealing with forall quantifiers (minimization), and solve the problem for existential quantufiers (maximization). This is because it's easier to just give a witness for the program, rather that showing that for all inputs the solution is optimal. The final step requires a witness for the resulting program. This could also be very difficult, because choosing a bad witness (one that is too far from the global optimum) could give a very weak or trivial lower bound. In the paper, the authors show how to choose a good witness for a particular case. Only for very few cases we know how to choose a good witness, and more research is needed in this part.

The paper ommits models like SMP (simultaneous message passing), unbounded-error protocols, and quantum communication with entanglement. The authors concentrate in lower bounds that can be stated in terms of a mathematical program by using norms. Still, they give a nice explanation on the corruption bound. This is an important technique because as noted by the authors it is the only lower bound technique that can separate quantum from randomized communication for total functions.

Back to blogging in spanglish

2010-11-23T21:49:00.000-03:00

Following the momentum given by Alejandro, I will also start writing in english. Well, actually I will do it either in english or spanish. I don't think I'll do it at the same time, mostly due to my increasing lazyness in the last couple of months.

The last two months I was simply overloaded with work at school, from TA work, reports, msc thesis, etc etc. Now, I'm finishing the thesis (but surely my advisors are going to give something else to add), passed the qualifying exam, finished sending two grant proposals (and writing a third one), I feel that I can start writing some posts.

It pains me to say that although my native language is spanish, I feel more comfortable writing in english. In the last 5 years, I only wrote one technical paper in spanish, so I think it's only a matter of practice though.

Well, what happened the last 2 months? For me, what I already mentioned above, but in the academic/internet world some very interesting stuff happened. For example, the recent breakthrough in computational complexity by Ryan Williams, i.e. NEXP not included in ACC0 (paper here). NEXP is known as the exponential NP and ACC0 is the class of languages with polynomial size circuits with bounded fan-in and constant depth with mod gates. Although ACC0 is a very low class, and NEXP is waay above, this "was" a open problem for more than 20 years! This paper presented a real progress in circuit lower bounds after all this time.

Also, the CSTheory stackexchange site is blooming! I was very disconnected from here also, but seeing the questions and answers today I can see that a lot more of people joined.

Finally, the QIP2011 programme is out!. Many interesting talks, but one caught my eye. "Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication" by Oded Regev (paper here). This has been an open problem for around 10 years, and is very much related to what I'm doing.

Empezando a bloggear en English

2010-11-22T06:27:00.000-03:00

(Versión en español más abajo)
From now on, I will start posting both in English and in Spanish. Why? Well, the reason to continue blogging in Spanish is that I feel that all this years blogging (from 2005) allowed me to meet lot of people, mostly in Latin America, to interact with; people doing research in quantum computing or just interested in the topic. Thus I don't want to lose such an opportunity to continue interacting with those people. I am aware that most of them should know English, however, blogging in Spanish was the reason of why this blog became (modestly) popular.
So, why to start blogging in English then? Because I want also to join the large community of academic bloggers in the world, and the common language in academia around the world is English.

Just to start, a bit of history:
This blog, "Computación Cuántica" (Spanish for quantum computing) was started by me in 2005, when I started being interested by the topic, back in Argentina during my undergraduate studies. Last year Daniel Villagra, a Paraguayan researcher based in Japan, joined to the blog and started updating the blog as well. Most posts are about our research. I am working on lambda calculus, type theory and logics, for quantum computing, and Danny is working in complexity, algorithms and automata.
From now on, I will blog both in English and Spanish, however I don't know what Danny will do (is up to him, I didn't ask him yet (sorry for that)).
So, finally: WELCOME. I hope you enjoy our blog.

Desde ahora, voy a empezar a postear tanto en inglés como en español. Porqué? Bueno, la razón para continuar blogueando en español es que siento que todos estos años blogueando (desde 2005) me permitieron conocer mucha gente, principalmente en América Latina, con quienes interactuar; gente investigando en computación cuántica o simplemente interesada en el tema. Por lo tanto no quiero perder la oportunidad de continuar interactuando con esa gente. Ya sé que la mayoría debe saber inglés, sin embargo, bloguear en español es lo que hizo que este blog se vuelva (modestamente) popular.
Ahora, porqué comenzar a bloguear en inglés entonces? Porque quiero unirme a la gran comunidad de blogs académicos en el mundo, y el lenguaje común en la academia en el mundo es inglés.

Un poco de historia:
Este blog lo comencé en 2005, cuando empecé a interesarme en el tema, aún en Argentina, durante mis estudios de grado. El año pasado Daniel Villagra, un paraguayo en Japón, se unió al blog y comenzó a postear también. La mayoría de los posts son sobre nuestras investigaciones. Yo estoy trabajando en cálculo lambda, teoría de tipos y lógica, para computación cuántica y Danny está trabajando en complejidad, algoritmos y autómatas.
Desde ahora, voy a bloguear en inglés y español, sin embargo no sé lo que hará Danny (depende de él, no le he preguntado aún (perdón por eso)).
Así que, finalmente: BIENVENIDOS, espero que disfruten el blog.

Escalares y sumas, al arXiv // Scalars and sums, to arXiv

2010-11-22T05:47:00.003-03:00

(English version below)
Ya está disponible el paper que escribimos con Barbara Petit sobre el análisis de las sumas en los cálculos algebraicos que presentamos en Types 2010. La semana pasada lo subimos al arXiv: http://arxiv.org/abs/1011.3542.

También la semana pasada con Pablo Arrighi actualizamos en el arXiv el paper sobre los escalares en los cálculos algebraicos. En este caso es un sistema de tipos que nos permite llevar de cierta manera una cuenta de 'la cantidad de un tipo' que participa en cada término. Acá dejo el link: http://arxiv.org/abs/0903.3741v4.

Ambos casos son análisis del lambda cálculo algebraico-lineal de Pablo Arrighi y Gilles Dowek, el cual fue pensado originalmente como un lambda cálculo cuántico, en el sentido de que permite encodear algoritmos cuánticos y está diseñado de tal manera de no permitir cloneo.

It is now available the paper we wrote with Barbara Petit about the analysis of sums in algebraic calculi, presented in Types 2010. Last week we uploaded it to arXiv: http://arxiv.org/abs/1011.3542.

Also last week with Pablo Arrighi we updated in the arXiv our paper about scalars in algebraic calculi. In this case it is a type system which allows us to take care of the 'amount of a type' that participates in each term. Here it is the link: http://arxiv.org/abs/0903.3741v4.

Both papers are analyses of the linear-algebraic lambda-calculus developed by Pablo Arrighi and Gilles Dowek, which was originally thought as a quantum lambda calculus, in the sense that it allows to encode quantum algorithms and it is designed to not allow clonning.

Slides Types 2010

2010-10-18T12:39:00.000-03:00

Como ya había adelantado, la semana pasada estuve en Varsovia participando del workshop Types 2010. Los slides de mis presentaciones están disponibles a través de mi página web: Sums in algebraic lambda-calculi y A vectorial type system (work-in-progress).

Hubo en general muy buenas charlas. En particular, les recomiendo ver los slides de la excelente charla de Henk Barendregt: Lambda calculus with types.

Types 2010

2010-09-30T12:19:00.001-03:00

Ya está publicada la lista de charlas y cronograma de Types 2010. Yo presentaré dos charlas allí:

Sumas en cálculos lambda algebraicos. Un trabajo conjunto con Barbara Petit. En este trabajo definimos el fragmento (confluente) "aditivo" del Linear-Algebraic Lambda-Calculus. Le definimos un sistema de tipos que incluye sumas de tipos como reflejo de las sumas en los términos. Luego de probar subject reduction y strong normalisation, estudiamos el rol de las sumas en el cálculo interpretando nuestro sistema en System F con pares. Mostramos que este cálculo se puede interpretar como System F con un constructor de pares asociativo y conmutativo, el cual es distributivo con respecto a la aplicación.
Un sistema de tipos vectorial. Un trabajo en colaboración con Pablo Arrighi y Benoît Valiron. El objetivo de este trabajo es combinar Scalar con Additive (el de más arriba) para crear un sistema de tipos al estilo System F para el Linear-Algebraic Lambda-Calculus el cual nos de una teoría de tipos general y original donde los tipos, de la misma manera que los términos, tengan una estructura de espacio vectorial. Mencionamos las conexiones con computación cuántica.

~~Luego de las charlas subiré aquí los slides~~. Aquí están.

Más novedades: Caminatas Cuánticas

2010-09-21T22:04:00.000-03:00

Reciéntemente (la semana pasada) he tomado y pasado con éxito lo que se conoce como exámen de cualificaciones (del inglés qualifying exam), aunque aquí en Japón lo llaman simplemente "exámen de ingreso al doctorado". Tuve que hacer una pequeña presentación de lo que hice hasta este momento y lo que planeo hacer en el futuro. Ya más adelante voy a comentar sobre lo que voy a hacer (de hecho ya lo comencé), pero ahora paso a transcribir un resumen que describe lo hecho hasta ahora.

Actualmente hay un gran interés en el diseño de algoritmos cuánticos utilizando el paradigma de las caminatas cuánticas. Generalmente, la construcción de algoritmos cuánticos resulta muy difícil, y la utlización de este paradigma resulta ser un enfoque muy prometedor. Las caminatas cuánticas fueron definidas en analogía a las caminatas aleatorias y las cadenas de Markov, y se espera que tengan el mismo éxito para el diseño y análisis de algoritmos cuánticos. Varios algoritmos utilizando caminatas cuánticas ya fueron descubiertos para verificación de multiplicación de matrices, búsqueda de triángulos en grafos, conmutatividad de grupos, por nombrar algunos. Clásicamente, la principal métrica de complejidad para algoritmos basados en cadenas de Markov es el hitting time. Es comúnmente definido como el número esperado de pasos para encontrar un conjunto de vértices marcados en un grafo, y está directamente relacionado con el tiempo de ejecución de los algoritmos aleatorios. De la misma forma, se puede definir una noción similar para caminatas cuánticas, pero esto resulta muy delicado. Si observamos la posición de la caminata sobre un grafo en cada paso, el sistema cuántico colapsa (de acuerdo a los postulados de la mecánica cuántica y el efecto Zenon cuántico), y no tiene ningún sentido tratar de explotar efectos mecánico-cuánticos para aceleración algorítmica. Por lo tanto, hay que tener mucho cuidado al definir una noción adecuada de hitting time. En este trabajo se estudia tal noción llamada One-Shot Hitting Time, y nos concentramos solamente en caminatas de tiempo discreto. Esta investigación está dividida en dos partes: i) líneas, y ii) grillas de 2 dimensiones. Para la primera parte, se propone una caminata que utiliza un operador con parámetros de fase a cargo de entonar la desviación estándar de la distribución de probabilidades inducida sobre la línea. Fórmulas para la evolución en el tiempo de la caminata fueron deducidas utilizando un método de punto silla para aproximación asintótica. Para este fin, como en trabajo anteriores, fue utilizado el análisis de Fourier para simplificar el estudio. También describimos la asintótica demostrando la convergencia débil de la caminata. Estos resultados dan una descripción precisa de los one-shot hitting times sobre la línea. Para la segunda parte, el análisis mencionado arriba no puede utilizarse debido a la complejidad de la fórmulas resultantes. Por lo tanto nos concentramos en acotar el hitting time y la probabilidad de encontrar un vértice arbitrario sobre la grilla. En una grilla de 2 dimensiones de tamaño n es demostrado, utilizando los modelos de caminatas cuánticas con monedas y basadas en cadenas de Markov, un hitting time de O(√n) con una probabilidad de éxito acotada para el primero, y no acotada para el segundo. Estos resultados pueden ser utlizados para aplicaciones algorítmicas en búsqueda espacial y ruteo de redes cuánticas.

La parte de aplicaciones aún la tengo que trabajar para tener todo bien cerrado. Estoy considerando utilizar para el caso de ruteo el modelo de cadenas de espines para transferencia de estados cuánticos. Esto me fue sugerido por Joe Fitzsimons aquí. Parece muy prometedor, pero aún debo de estudiarlo bien.

Algunas novedades

2010-09-08T23:04:00.000-03:00

Estos 3 últimos meses fueron de los más atareados que he tenido, y aún no me desocupo y tengo varias cosas sobre que escribir. Mientras tanto algunas novedades:

Fui a AQIS'10 para presentar este trabajo. La conferencia estuvo simplemente excelente con muy buenas presentaciones dadas por reconocidos investigadores como Andrew Yao, Harry Buhrman, Richard Jozsa y otros. Conocí a otros investigadores y en especial a Luciano Aparicio de Argentina de la Universidad de Tokyo. El estudia con Rodney Van Meter en "multiplexación de información cuántica para ruteo en redes" quien resultó ser una persona muy agradable y aproveché para pedirle los slides de su presentación de video en youtube sobre el cual había escrito aquí. Al final puso un link en su página personal para acceder a los slides.
Ya está habilitado para su acceso al público en general el sitio web de preguntas y respuestas sobre computación teórica CSTheory. Se requiere que las preguntas y respuestas sean de nivel de investigación. Hay varias personas colaborando en esto de todas las áreas de las ciencias de la computación.
Ya está el CFP de STOC'11.
También la conferencia LAGOS'11 que se llevará a cabo en Bariloche. Esto es para los fanáticos de teoría de grafos.

La importancia de P vs NP

2010-08-16T03:25:00.001-03:00

Figura de Theory Matters Wiki.

Dado los acontecimientos de la semana que acaba de terminar, donde Vinay Deolalikar presentó un intento de prueba para el problema de P vs NP, esta entrada la escribo para poder explicar los alcances del problema mismo para las ciencias de la computación, y para todas las ciencias en general.

Cada mes se publican en ArXiv artículos que dicen resolver el problema. Algunos dicen que P=NP, otros que P≠NP, etc. La diferencia estuvo en que este artículo en particular había pasado todos los exámenes que utilizan los teóricos en complejidad para discriminar los artículos serios. Además, este estaba escrito por una persona conocida, y cuando había enviado una versión preliminar a un grupo selecto de científicos, uno de los principales, el mismo descubridor del problema y ganador del premio Turing, Stephen Cook, había escrito en respuesta "esto parece un esfuerzo serio" (del inglés this looks like a serious effort). Esto había motivado al resto y puso a funcionar una máquina bien aceitada de colaboración científica inigualable en la red. Como lo dijo Dick Lipton, "lo que antes se hacía en meses, ahora por Internet lo hacemos en días". Para saber como terminó toda la historia recomiendo el post anterior de Alejandro donde tienen todos los enlaces. Aquí me voy a concentrar en la definición e importancia de P vs NP.

A continuación un pequeño repaso del problema. Antes que nada este es considerado el problema principal, más importante, de las ciencias de la computación. Básicamente el problema es "para ciertos problemas, lo mejor que podemos hacer es una búsqueda bruta", o como escribe Lipton "para ciertos problemas el algoritmo más obvio es el mejor". NP como sabemos quiere decir "tiempo polinomial no-determinístico", y P "tiempo polinomial determinístico". Entonces los problemas o lenguajes con algoritmos que corren en tiempo polinomial están en P, y los problemas con algoritmo en tiempo polinomial no-determinístico en NP.

Una caracterización más fácil de entender de problemas en NP es la siguiente: Sea A un algoritmo que tiene dos entradas, x que representa una instancia de un problema L (e.g. SAT, TSP, etc), y c que representa una solución al problema. Entonces L están en NP si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A y existe un c tal que A(x,c)=1, i.e. que c sea una respuesta válida al problema. Generalmente a c se le llama solución, certificado, testigo o simplemente prueba, i.e. una prueba de que x tiene solución. La misma caracterización se puede hacer para P, pero esta vez el algoritmo no tiene una prueba c. Entonces decimos que L está en P si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A tal que A(x)=1.

La gran diferencia está en el certificado. Los algoritmos para lenguajes en P determinan una solución, mientras que los algoritmos para lenguajes en NP verifican una solución. Una buena analogía es: si yo resuelvo un problema matemático por mi mismo (está en P), o estoy verificando la solución de otra persona (en NP). Entonces, la diferencia radica en que estamos comparando un proceso de determinar una solución a un problema contra un proceso de verificación de una solución ya dada para un problema.

Imagen de Wikipedia.

P vs NP en términos computacionales se refiere a cotas inferiores de problemas NP-completos. La conjetura es que para estos problemas no existe un mejor algoritmo que el de fuerza bruta, i.e. P≠NP. La mayoría de los científicos creen que esto es cierto, y de ahí surgen un montón de alternativas para resolver problemas NP-completos como Búsqueda Local, Algoritmos Genéticos, etc. Y la eficiencia de estos métodos está en que pueden verificar soluciones en tiempo polinomial.

En mi humilde opinión, una prueba de que P≠NP no cambiaría mucho las cosas porque todo lo que hacemos ahora, lo hacemos en función de que P≠NP. Por ejemplo, asumimos la existencia de 1-way functions en criptografía ¿Entonces de que nos sirve una prueba de eso? Una prueba no solo nos dice si una hipótesis es falsa o verdadera, sino que al mismo tiempo ganamos mucha información acerca del problema mismo. De una prueba de P≠NP podemos descubrir muchas conexiones entre áreas de conocimiento u objetos que creíamos desconectados en nuestra teoría. Eso tiene mucho más valor que una respuesta de falso o verdadero. Esto es lo que está ocurriendo con la prueba de Deolalikar. Algunas personas nunca habían considerado conectar el finite model theory con el clustering en Random-k-SAT. El enfoque de por sí requiere más investigación y despierta mucha curiosidad.

En el aspecto filosófico, P vs NP hace la siguiente pregunta: ¿Puede la creatividad ser automatizada? Si yo escribo un libro en el que trabaje 1 año, y lo mando a un periódico para que un crítico lo lea, y la destruye completamente en 2 semanas, ¿Qué es más dificil, escribir el libro o criticar el libro? Intuitivamente el proceso creativo es más complejo y requiere más tiempo, pero hasta que no tengamos una prueba que indique sin duda alguna nunca sabremos, por la misma razón que expuse en el párrafo de arriba. Simplemente por la curiosidad del hombre, tenemos que saber (esto lo dijo David Hilbert).

También la misma pregunta se extiende a otros ámbitos como la física. La visión de las ciencias de la computación y una parte de la comunida de físicos, es que toda nuestra realidad física es computable. Desde la evolución de los seres vivos, hasta la formación de galaxias. Todo es visto como un proceso que dado una entrada genera un salida. Entonces salen preguntas como ¿Qué tan complejo es el plegado de proteínas? ¿Qué pasa con la información y la energía en un hoyo negro que se disipa en forma de radiación de Hawking? etc, etc. Muchas de esta preguntas están siendo respondidas por técnicas de ciencias de la computación. Por ejemplo, sabemos que si P≠NP entonces no podemos viajar en el tiempo, o no podemos movernos más rápido que la luz, y otras conexiones más extrañas. Aún así, estás conexiones dan evidencia a favor de que P≠NP, o no?

Asi que P vs NP no solo se refiere a problemas que solo interesan a las ciencias de la computación. Se refiere también a problemas fundamentales de otras ciencias. Inclusive podría decirse que es una de las preguntas más fundamentales de las matemáticas. Saber si podemos encontrar pruebas eficientemente nos da conocimiento de como resolver otros problemas muy difíciles como la Hipótesis de Riemann. Es por ello que el Clay Mathematics Institute lo pone en su lista de problemas fundamentales.

Para más información recomiendo el libro Computational Complexity A Modern Approach, o el artículo de Lance Fortnow en Communications of the ACM.

Una prueba de que P ≠ NP?

2010-08-10T06:02:00.007-03:00

Desde hace unos días Vinay Deolalikar ha creado un gran revuelo en la comunidad científica al liberar un borrador de una prueba de que P ≠ NP. La pregunta de si P es igual o distinto a NP es uno de los problemas no resueltos más importante de las ciencias de la computación (y las matemáticas), por lo tanto, el borrador de Vinay ha tenido a la comunidad científica ocupada tratando de verificar sus 102 páginas.

Por mi parte sólo estoy tratando de seguir las discusiones, no creo ser la persona capacitada para analizar la veracidad o falsedad de las afirmaciones de Vinay, así que aquí dejaré algunos links para quienes estén interesados en seguir el debate.

Sin dudas los posts en el blog de Dick Lipton son los más interesantes:

También hay un intento de ordenar la discusión por medio de una Wiki en el sitio de Michael Nielsen.

A pesar de los problemas marcados, aún no hay un "veredicto" definitivo de la comunidad científica, más allá de alguna apuesta, la mayoría coincide en que la prueba puede ser correcta, o al menos llevar a un razonamiento correcto, con los errores esperables en un borrador tan largo en un problema tan complejo y lo que todos coinciden, es en que es un muy buen trabajo y tiene resultados interesantes, aún si la prueba de P ≠ NP resultase errónea.

Update 11/08/10: Un nuevo post en el blog de Dick Lipton trata de tirar más luz al asunto: La idea es pedirle a Vinay que muestre cómo usar sus resultados para resolver problemas más sencillos, de los cuales ya se conoce la solución. Es una buena manera de entender por dónde viene la mano, ya que el paper en sí tiene muchos detalles técnicos y es difícil de seguir incluso por quienes trabajan a diario en complejidad.

Update 11/08/10 (2): Dejo un artículo de divulgación muy bueno que apareció en la revista Nature: Million-dollar problem cracked?

Update 12/08/10: Un nuevo post en el blog de Dick Limpton detalla cuál parece ser el mayor problema en la prueba, y la respuesta de Vinay Deolalikar.

Update 13/08/10: Dick posteó lo que parece ser un error insalvable en la prueba, un error de interpretación por parte de Vinay en el uso de la teoría de modelos finita: Fatal Flaws in Deolalikar’s Proof?

Número de sumas de subconjuntos

2010-07-22T04:39:00.002-03:00

Estuve probando un poco de MathOverflow y realmente me sorprendió lo rápido en que las personas leen y responden a tus preguntas. La pregunta que hice fue sobre el número de soluciones para sumas de subconjuntos (subset sums). Sea F_qun campo finito con característica p tal que p < q (i.e. no es un campo primo). Sea D ⊆ F_q un subconjunto con |D| = n. El problema de la suma de subconjuntos consiste en encontrar un subconjunto no vacío {x₁,…,x_k}⊆ D tal que x₁ + ... x_k = s dado s ∈ F_q. Cuántas soluciones aproximadamente permite el problema para un conjunto dado D? Que pasa si seleccionamos D en forma aleatoria?

La respuesta que obtuve fue la siguiente (la versión escrita aquí está mas desarrollada): Tenemos n elementos de los cuales k tienen que sumar s, entonces tenemos candidatos. Sea D = {a₁,…,a_n} y definamos la variable aleatoria X como la suma de k elementos de D, i.e. X = a_x₁ + ... + a_{x_k}. Las variables x_i son índices. Tenemos asi que Pr(X = 0) = P(X = 1) == P(X = s) = P(X = q - 1) = . Por lo tanto el número aproximado de soluciones que suman s es claramente . Bien sencillito.

Para el caso D aleatorio supongamos que tenemos una solución x₁ + ... + x_k. Para una D aleatoria con |D| = n la probabilidad p de que todas las x_i en la solución esten presentes en D es

.

El numerador es así porque para la solución dada solo combinamos los elementos que son diferentes a cada x_i. Entonces p es igual para cada solución. Considerando que el número total de soluciones para todo el campo es (cf. párrafo de arriba), haciendo cuentas el valor esperado es

.

Claramente ambas respuestas deben de coincidir porque en el fondo para responder la primera pregunta hacemos uso de índice aleatorios.

Obs: Esta entrada la escribí usando TtH y el Online LaTeX Equation Editor en modo de prueba. La conclusión es utilizar TtH, y lo que no pueda convertir a html, hacerlo con el editor de ecuaciones.

Theory Overflow

2010-07-11T05:51:00.001-03:00

Para las personas interesadas en computación teórica existe un sitio web que está comenzando a promoverse para establecer discusiones sobre el tema. Temas que van desde computación cuántica, complejidad computacional, lógica, lenguajes de programación, etc. Todos por supuesto temas teóricos.

El problema está en que antes de volverse totalmente activo y ser aceptado por los administradores, debe de tener el suficiente apoyo de personas que firmen con su nombre y se comprometen a participar.

Si alguien está interesado puede hacer click en el enlace de abajo, inscribirse y darle en "commit".

Theory OverFlow

Muchos investigadores exitosos en el área ya están inscriptos y dispuestos a interactuar en el sitio. Esto puede ser muy beneficioso para que estudiantes puedan hacer preguntas y esperar que expertos les respondan.

Existe un sitio similar, pero es sobre matemáticas en general: MathOverFlow. Si hay personas interesadas también pueden unirse ahí. La diferencia está en que Theory OverFlow es estrictamente computación teórica.

Papers de FOCS 2010

2010-07-02T05:35:00.000-03:00

Ya salió la lista de papers aceptados en FOCS 2010. Shiva Kintali realizó un gran trabajo creando una lista de los papers con enlaces a ArXiv en su blog.

Hay solo uno relacionado con computación cuántica, y luego de leer el resumen parece muy interesante.

An efficient test for product states, with applications to quantum Merlin-Arthur games. Aram W. Harrow and Ashley Montanaro. [ArXiv].

Otro que me llamó la atención es

New Constructive Aspects of the Lovasz Local Lemma. Bernhard Haeupler, Barna Saha and Aravind Srinivasan. [ArXiv].

Panel de expertos en Computación Cuántica

2010-06-25T02:58:00.000-03:00

Encontré este video en internet sobre un panel de discusión sobre los avances en computación cuántica. En el están 6 expertos del área: Avi Widgerson, Peter Shor, Daniel Gottesman, Ignacio Cirac, Dorit Aharonov, y Michele Mosca. Todos ellos hicieron grandes aportes al área pero resalta en especial Peter Shor, el descubridor del algoritmo de factorización. Ignacio Cirac también fue uno de las personas que propuso uno de los modelos más efectivos para computación cuántica, la "trampa de iones".

Me gustó mucho el video, explica claramente para las personas no expertas la importancia de la investigación en esta área. Sobre todo me gustó mucho cuando cada uno de ellos contó sobre su experiencia cuando comenzaron a estudiar computación cuántica.

A continuación el video.

Oxford → Marsella → Turín

2010-06-17T17:02:00.000-03:00

Las últimas semanas he estado viajando un poco:

Del 24 al 30 de Mayo fui a Oxford donde se llevó a cabo la spring school foundational structures in quantum computation and information (escuela de primavera estructuras fundamentales en computación e información cuántica), seguida del workshop quantum physics and logic (Física y Lógica Cuánticas). Los videos de todas las charlas de la escuela están acá y del workshop acá. Allí mismo tienen videos de eventos anteriores ordenados por evento o por speaker.
El 8 de Junio fui a Marsella al primer encuentro del proyecto QuAND a presentar el "additive type system" (próximamente en arXiv), trabajo realizado con Barbara Petit, y la traducción del Linear-Algebraic Lambda-Calculus al Algebraic Lambda-Calculus (y viceversa), trabajo realizado con Simon Perdrix, Christine Tasson y Benoît Valiron que ya fue aceptado para el workshop higher-order rewriting que se realizará en Edimburgo el 14 de Julio próximo.
Finalmente, del 9 al 11 de Junio estuve en Turin en el encuentro CONCERTO-PICS donde presenté el mismo trabajo con Barbara. Proximamente van a poner los slides de todas las charlas en esa página.

Matematicas para Computación Cuántica

2010-06-01T05:19:00.000-03:00

Quisiera comentar un poco sobre lo que cuesta estudiar computación cuántica y computación teórica. Entiéndase "cuesta" en términos de esfuerzo, y no en términos de dinero.

Antes de empezar a estudiar el tema, había estado realizando investigación en búsqueda local para problemas de optimización combinatoria como SAT, TSP, etc. Aquí tienen un lista de mis publicaciones. Estos temas los hacía principalmente con experimentos, y fui descubriendo de a poco que no quería hacer investigación experimental. Empece a estudiar computación cuántica con énfasis en algoritmos y complejidad computacional hace 2 años atrás. Ese fue mi plan para la escuela de post-grado. Actualmente ya me siento cómodo trabajando en esta área, tanto que ya estoy en condiciones de publicar resultados. Ahora mismo conferencias, y luego revistas.

La parte más complicada es construir una intuición. Para trabajar en computación teórica utilizamos generalmente las máquina de Turing como modelo. Acostumbrarse a ello no es fácil, y requiere mucho estudio para que se vuelva algo más natural. La mecánica cuántica es en mi opinión más difícil, porque las personas traemos instintivamente conceptos como velocidad, distancia, aceleración, etc., pero en el mundo cuántico no tenemos forma de percibir lo que ocurre. La intuición y el sentido común no sirven y tenemos que seguir los modelos que están bien probados experimentalmente. Es esa intuición la que requiere horas de estudio todos los días durante varios meses. Y no solamente leer sino también hacer investigación, e intentar resolver problemas. A continuación presento un lista de las cosas que considero necesarias para estudiar complejidad computacional y algoritmos cuánticos.

1- Algebra Lineal. Espacios vectoriales y sus propiedades, con principal énfasis en espacios de complejos.

2- Combinatorica. Contar objetos discretos por medio de permutaciones, combinaciones, etc, y otros conceptos muy importantes como series finitas e infinitas (aunque esto es más cálculo), funciones generadoras, aproximación de Stirling. Aquí también incluiría teoría de grafos combinatorica.

3- Complejidad Computacional. Las clases de complejidad básicas como BPP, P, NP, PSPACE, IP, SZK, P/poly, PH, y otros conceptos como relativización y reducciones. También agregaría otros modelos de computación como "communication complexity", árboles de decisión, PCP, y "derandomization".

4- Fundamentos de Computabilidad / Teoría Recursiva. Las definiciones de autómatas como modelos de computación, problemas decidibles, no-decidibles y semi-decidibles, la jerarquía aritmética, y más reducciones. También modelos descriptivos como cálculo-λ y funciones recursivas.

5- Probabilidades. Los conceptos básicos de espacio de probabilidades, valor esperado, varianza, distribuciones de probabilidades, momentos de una variable aleatoria y como realizar análisis probabilístico de algoritmos y análisis de algoritmos probabilísticos. Es de vital importancia también aquí la teoría de cadenas de markov y el método probabilístico en sus distintas formas.

6- Análisis Funcional. Los conceptos de espacios de Hilbert, espacios con normas, y espacios métricos.

7- Análisis Complejo. Analiticidad, ecuaciones de Cauchy-Riemann, funciones armónicas, algebra de números complejos, integrales de contorno. De aquí tuve que aprender un método para aproximaciones asíntoticas de integrales conocida como el método del punto silla.

8- Algebra Abstracta. Teoría de grupos, anillos y campos de Galois. Aquí pondría teoría de grafos algebraica e incluir "expanders" y grafos de Cayley.

9- Mecánica Cuántica. Postulados de la mecánica cuántica, el operador de densidad, estados cuánticos mezclados y puros, osciladores armonicos, dualidad partícula vs onda, el Hamiltoniano, etc.

10-Teoría de la Información. Cantidad de información y entropía, códigos, compresión.

No creo que sea una lista exhaustiva, pero es eso más o menos lo que tuve que estudiar y aprendí en las clases y fuera de ellas. Algunas ya las había aprendido durante los estudios de pre-grado, y otras en post-grado. Por ejemplo, el método probabilístico utilizando segundos momentos y el "Lovász Local Lemma" lo aprendí por mi cuenta, mientras la clase de complejidad SZK lo aprendí en un clase de post-grado sobre criptografía.

Por supuesto, es imposible acordarse de los detalles de todo, por lo que siempre hay que estar con los libros cerca. Pero por lo menos habría que recordar siempre los resultados principales.

Me imagino que en el área de lógica (donde trabaja Alejandro) debería de haber más cosas. No me imagino cuáles. Las comunidades de complejidad y computabilidad están un poco separadas. Comenzaron unidas pero luego fueron separandose debido a que las técnicas utilizadas eran muy diferentes unas de otras.

Aún habrán más cosas por aprender sin duda.

Criptografía cuántica «comercial», crackeada

2010-05-18T07:09:00.003-03:00

Antes que nada, que quede claro la palabra comercial en el título. La criptografía cuántica sigue siendo imposible de crackear en teoría, el problema es la implementación.

Feihu Xu, Bing Qi y Hoi-Kwong Lo de la Universidad de Toronto dicen haber craqueado uno de los sistemas criptográficos comerciales.

El tema es así: las pruebas que dicen que la criptografía cuántica es imposible de crackear se basan en implementaciones perfectas que en la realidad no es posible realizar... siempre habrá ruido que introducirá errores. Por ello es que los dispositivos de criptografía deben tolerar cierto ruido. Varias pruebas dicen que si el error se mantiene por debajo del 20%, el mensaje sigue siendo seguro. Sin embargo esas pruebas sólo consideran el ruido ambiente, no consideran errores introducidos en la preparación del estado inicial (el que envía el emisor)... y allí es donde Xu, Qi y Lo hicieron su truco. Ellos afirman que debido a ese error extra un tercero puede interceptar algunos bits cuánticos, leerlos y volverlos a enviar de una manera que incrementa el error en sólo 19,7%, lo cual será tolerado ya que está por debajo del 20% permitido.

Este problema es fácil de resolver, es cuestión de considerar también el error introducido por el emisor en el cálculo de tolerancia. Pero el problema fue destapado: de la teoría a la práctica habrá siempre cosas que asumir y en esas asunciones es donde está la debilidad.

Conclusión:
El método criptográfico clásico One Time Pad es 100% seguro, es imposible de crackear, el problema es que para utilizarlo y que sea seguro, debe haber algún modo de distribuir las claves a utilizar, las cuales deben ser del mismo largo que el mensaje (para 100% de seguridad). Para hacer eso existen métodos de distribución de claves cuánticos que son 100% seguros, imposibles de crackear, el problema es que para implementarlo debe haber algún modo de realizar un dispositivo sin errores. Para hacer eso se utilizan técnicas de corrección de errores, y se demuestra que se puede tolerar hasta un 20% de error ambiente y sigue siendo 100% seguro, el problema son los otros errores que no se tienen en cuenta. Ahí es donde entra el crack.

Para leer más:

El paper de Xu, Qi y Lo está disponible online: arXiv:1005.2376.
Hay una nota sobre el tema en el blog «The Physics arXiv»: Commercial Quantum Cryptography System Hacked.
Hay una nota sobre el tema también en Slashdot: Commercial Quantum Cryptography System Hacked.

Equivalencia de λ-cálculos algebraicos

2010-05-18T05:07:00.002-03:00

Como ya adelanté anteriormente, con Simon Perdrix, Christine Tasson y Benoît Valiron tenemos un paper aceptado en el workshop Higer-Order Rewriting que se llevará a cabo en Edimburgo el 14 de Julio.

Ayer enviamos la versión final (extended abstract de 5 páginas + referencias) y subimos la versión completa (con todas las pruebas, 19 páginas) al arXiv.

En este paper lo que hacemos es probar que el Algebraic λ-Calculus de Lionel Vaux (λalg), el cual es un fragmento del differential λ-Calculus, puede simular el Linear-Algebraic λ-Calculus de Pablo Arrighi y Gilles Dowek (λlin), el cual es un candidato a λ-Calculus para computación cuántica, y también probamos la simulación inversa. Ambos cálculos permiten la combinación lineal de términos, sin embargo presentan diferencias a la hora de realizar las reducciones. Por ejemplo en λalg el término

reduce a

en cambio en λlin, ese mismo término reduce a

Las pruebas de simulación se basan en la observación de que esencialmente λlin es call-by-value mientras que λalg es call-by-name. La simulación en un sentido usa la idea de "thunks" y en el otro es una extensión del continuation passing style.

Este paper es un paso hacia probar la dualidad entre ambos cálculos.

Computational Complexity in a Nutshell

2010-05-12T21:49:00.001-03:00

No estoy seguro de la traducción del título. "nutshell" es algo así como cáscara de nuez, y es un término utilizado para referirnos a que un tema esta explicado en forma breve pero completo a la vez. En este caso el tema sería Complejidad Computacional.

Complejidad computacional es un área de las ciencias de la computación teórica que estudia la dificultad de resolver problemas computacionales. La dificultad de un problema computacional se mide en términos de los recursos computacionales necesarios para resolver ese problema, por ejemplo, tiempo, memoria, conectividad en la red, número de procesadores etc. El objetivo principal es crear una clasificación (estricta) de problemas computacionales. Esa clasificación son las clases de complejidad. Por ejemplo, los problemas que no requieren mucho tiempo ni mucha memoria se les llama problemas de tipo P. Problemas que requieren mas tiempo, pero aun con poca memoria son NP, y así.

También existe la complejidad computacional cuántica, que estudia la complejidad de las máquinas cuánticas. Más adelante voy a preparar una entrada sobre el tema.

Me gustaría compartir una serie de cursos impartidos en UC Berkeley dictados por Luca Trevisan sobre complejidad computacional. Los materiales para su curso los fue distribuyendo via su propio blog. Fue capaz de explicar temas relativamente difíciles de una forma breve y a la vez clara. Simplemente me encanta las matemáticas de esta área, sin dudad una de las invenciones más bellas de la mente humana.

Clase 1 - Introducción

Clase 2 - P y NP

Clase 3 - Circuitos Booleanos

Clase 4 - La Jerarquía Polinomial

Clase 5 - La Jerarquía Polinomial

Clase 6 - Teorema de Karp-Lipton

Clase 7 - Teorema de Valiant-Vazirani

Clase 8 - Conteo Aproximado

Para más detalles sobre el área recomiendo el libro Computational Complexity: A Modern Approach. Este libro está muy actualizado, y explica los conceptos de una forma bien clara

Arquitectura de Computadores Cuánticos

2010-04-18T00:54:00.009-03:00

Rodney Van Meter es un profesor asociado en la universidade Keio, en Tokyo. Tiene un grupo de investigación en arquitectura de computadores cuánticos. Hace poco descubrí un video en youtube sobre la presentación de las investigaciones que realizan en Keio. Está muy interesante, y presentan otros temas que pueden ser llevadas a cabo por personas en ciencias de la computación. A continuación el video.

Papers de ICALP 2010

2010-04-12T06:37:00.002-03:00

Ultimamente estoy con mucho trabajo, y espero dentro de poco poder presentar en este blog los avances de mi investigación.

Se acaba de publicar la lista de papers aceptados en ICALP 2010 en este link. Hay solo 3 papers en computación cuántica:

1- Hari Krovi, Frederic Magniez, Maris Ozols, and Jérémie Roland. Finding is as easy as detecting for quantum walks. [arXiv:1002.2419]

2- Bob Coecke and Aleks Kissinger. The compositional structure of multipartite quantum entanglement.

3- Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow.

Solo pude encontrar la versión online del primer paper. Por suerte es un paper que está muy relacionado con lo que hago y ya lo imprimí para darle una leída.

El problema que resuelve es un pequeño problema abierto que había en algoritmos de búsqueda basados en quantum walks sobre un arreglo 2-dimensional. Algoritmos anteriores solo resolvían el caso de 1 y 2 vértices marcados sobre este arreglo 2-dimensional. Si se quería encontrar más de 2 soluciones, el número de consultas al oráculo cuántico empeoraba. En este paper se presenta un algoritmo que encuentra un número arbitrario de vértices marcados sobre la grilla casi empatando con la cota inferior (solo difiere en un término logarítmico). Esto lo hace utilizando como base quantum walks basados en producto de reflexiones [Magniez et al. 2007] que extienden las cadenas de Markov y una técnica muy interesante de interpolación entre estas cadenas de Markov clásicas.

Definitivamente un paper que tengo que leerlo bien.

Trabajos en progreso

2010-03-27T20:09:00.005-03:00

Scalar. Con Pablo Arrighi estamos preparando la versión completa del Scalar Type System para un journal. Ya recibimos algunas críticas y estamos enviando una versión corregida. El 11 de abril es el deadline, así que se supone que la terminemos antes. ~~En cuanto esté lista subiré la actualización al arXiv y avisaré aquí~~. Update: Aquí está arXiv:0903.3741
Vectorial. También con Pablo estamos terminando el Vectorial Type System para enviar a una conferencia (aquí dejo los slides que presenté en las Jornadas GEOCAL-LAC a las que fui la semana pasada). El deadline es el viernes 2 y aún falta bastante por hacer, así que no sé si llegaremos... ya comentaré. Update: No llegamos, aún quedan por retocar algunas cosas, así que apuntaremos a algún otro congreso
Lineal → Alg. Con Simon Perdrix, Benoît Valiron y Christine Tasson estamos trabajando en una traducción del linear-algebraic lambda-calculus de Pablo Arrighi y Giles Dowek al algebraic lambda-calculus de Lionel Vaux. Tenemos un deadline este miércoles, lo cual es complicado ya que es muy poco tiempo y todos estamos ocupados con otras cosas, pero si llegamos con esto les comento. Esto es un work-in-progress para un Workshop. Update: Extended abstract enviado, ahora estamos preparando una versión un poquito mas larga (con más detalles) para subir al arXiv, avisaré cuando aparezca. Update 20/04/10: Paper aceptado en el HOR2010. Ahora tenemos hasta el 17 de mayo para enviar la versión extendida, así que no creo que ponga otra versión online antes de esa fecha. Update 18/05/10: Extended abstract (5 páginas + ref) | arXiv:1005.2897 (con todas las pruebas). Post en el blog.
Additive → IMELL. Con Barbara Petit estamos trabajando en una traducción de Additive (vendría a ser un Vectorial sin escalares, o sea, sólo sumas) en Linear Logic (más precisamente: Intuisionistic Multiplicative Exponential Linear Logic, o sea, La parte de Linear Logic que tiene sólo multiplicaciones y bangs (!) y no "tercero excluído").
FullAdditive. Pablo Buiras, de Rosario, está trabajando en una extensión del Additive, ya que el additive que tenemos ahora sólo sirve para el cálculo sin escalares (o sea, el linear-algebraic lambda-calculus que tiene sumas, pero no escalares ni 0), la idea es hacer un sistema de tipos con sumas y no escalares, para el cálculo completo, lo cual presenta problemas no triviales sobre cómo hacer la interpretación (abtracta?) de los términos en los tipos. Esa es una tesis de Licenciatura (lo que acá en Francia sería una tesis de Master), la cual voy a dirigir junto a Mauro Jaskelioff.
Lineal diferencial. Esta es una inquietud que surgió a partir de una visita de Emmanuel Beffara a nuestro laboratorio, en la que estamos trabajando con Emmanuel, Simon y Benoît: Cómo agregar un operador diferencial al linear-algenbraic lambda-calculus.

A medida que vaya teniendo resultados / papers completos los iré posteando aquí.

Escuela: "Foundational Structures in Quantum Computation and Information" en Oxford

2010-03-27T17:23:00.001-03:00

Como mencioné en un post anterior, justo antes del QPL de este año se realizará una escuela sobre estructuras fundamentales en información y computación cuántica. Habrá cursos en los siguientes temas:

modelo de computación cuántica basado en medición (MBQC: measurement-based quantum computation); propiedades de grafos de estados; MBQC y física de materia condensada; computación cuántica ciega (blind quantum computing); determinismo en MBQC; modelo de computación clásica basado en medición y no-localidad;
categorías monoidales, álgebras de Frobenius y su cálculo gráfico; (co)algebra de observables complementarios y enredo cuántico multipartito, y aplicaciones en MBQC; grupos de fase y no-localidad;
simulación clásica de circuitos cuánticos; topología categórica de computación cuántica; cálculo gráfico para medición y canales de información; teorías probabilísticas generalizadas; modelos operacionales convexos y no-localidad;
autómatas celulares cuánticos (QCA); QCAs y causalidad; typos de alto orden en computación cuántica; lógicas cuánticas y máquinas cuánticas; métodos coalgebraicos.

De la mayoría de los temas, conozco poco y nada; y por eso planeo asistir a la escuela :)

La escuela dura cinco días, del 24 al 28 de Mayo, en Oxford y es organizada por Bob Coecke y Ross Duncan.

Trataré de ir haciendo resúmenes diarios sobre lo que vaya viendo.

Videos de QIP 2010

2010-03-11T07:20:00.000-03:00

Las últimas semanas disfruté (y sigo disfrutando) de los videos de las presentaciones de QIP 2010. Se pueden acceder a todas ellas a traves de este enlace.

Muy buenos todos los videos, en especial me gustó mucho la presentación introductoria de Umesh Vazirani sobre la relación entre la física y las ciencias de la computación y los últimos avances en algoritmos cuánticos.

Recomiendo ver el video de QIP=PSPACE. Este fue uno de los mayores avances en complejidad computacional el año pasado.

Escuela de verano canadiense en Información Cuántica

2010-03-01T22:30:00.000-03:00

En julio de este año se organiza la décima escuela de verano en información cuántica en la Universidad de British Columbia. El link de la escuela es este. Los cursos van a ser dictados por personas conocidas en computación cuántica, por lo que promete mucho. Además van a estar organizando un workshop de 3 días para que los estudiantes puedan presentar su investigación. Serán dos semanas muy interesantes.

AQIS 2010

2010-02-23T23:15:00.000-03:00

En agosto se realizará la conferencia AQIS2010 (Asian Conference on Quantum Information Science) en Tokyo. Todos los años van personas muy reconocidas en computación cuántica, por ejemplo el año pasado estuvieron Peter Shor y Charles Bennett. Este año va a estar presente Andrew Yao, asi que voy a ver si puedo enviar algo para presentar o voy solo de asistente. Pero sin duda es una conferencia que no me la quiero perder.

Amplificación de Amplitud

2010-02-16T03:11:00.002-03:00

En este post voy a explicar la técnica más popular para la construcción de algoritmos cuánticos conocida como Amplificación de Amplitud (Amplitude Amplification). Mi investigación está principalmente basada en encontrar cotas superiores e inferiores utilizando esta técnica y quantum walks (sobre este punto ya hablaré más adelante). Esta técnica es una generalización del algoritmo de Grover.

Antes que nada, se le llama amplificación de amplitud porque se amplifica o incrementa la amplitud en la ecuación de onda de una partícula. Por ejemplo, sea un estado cuántico definido en un espacio de Hilbert , donde cada es un vector de la base de (siempre ). En un problema de búsqueda sin información, para encontrar un índice dado , donde , la técnica de amplificación de amplitud ubica el vector base en con amplitud , y sustituye ese valor por otro tal que . El resto de las amplitudes son sustituidas por otras amplitudes con valor absoluto menor. Esto ocurre automáticamente porque las transformaciones efectuadas a son unitarias, i.e., preservan el valor del producto interno y por lo tanto las normas. De esta forma al realizar una observación, el algoritmo retorna el valor con probabilidad suficientemente alta.

Esa es básicamente la intuición en el algoritmo de amplificación de amplitud. A continuación paso a formalizar esta idea, pero solamente describiendo el caso particular del algoritmo de Grover. Hacia el final de post mencionaré como es el caso general de amplificación sin entrar en detalles.

El algoritmo de Grover funciona aplicando primero al estado un operador que genera el vector

i.e., una superposición con la misma amplitud para todos los elementos de la base. Luego, sobre se aplica un número de veces dos operadores unitarios: el oráculo y el operador de difusión . Entonces el algoritmo luce algo como . Vamos a probar que , y retorna con una probabilidad .

Primero el oráculo es un operador de fase (reflexión), y su acción se basa en cambiarle el signo a la amplitud de la base dejando el resto sin alterar. Se define como , donde es la entrada a la función del oráculo, y es el bit del oráculo el cual se invierte si (el operador representa al OR exclusivo bit a bit si la codificación es binaria, o puede considerarse como adición modulo 2 para números en base mayor a 2). Inicializando a , la acción del oráculo puede resumirse en

i.e., el oráculo "marca" el vector buscado inviertiendo su fase. Como escribir el oráculo en esta forma dada la definición anterior es un ejercicio muy entretenido (ref. Quantum Information and Computation. Nielsen and Chuang).

El operador de difusión de Grover (definido aquí) tiene la siguiente forma

o en notación de Dirac

Este operador se conoce también con el nombre de reflexión alrededor de la media, porque también puede escribirse de la siguiente forma .

Ahora, supongamos que estamos buscando un único elemento en (esta es una notación más corta para referirse al conjunto ). Definamos el estado cuántico

La norma de los vectores debe de ser siempre 1, por lo tanto (tenemos un solo porque solo hay un único vector objetivo, y porque esos vectores no representan una solución al problema). Denotemos por el estado del algoritmo en el tiempo . Vamos a calcular cual es la realción entre y . Primero aplicamos el oráculo

A continuación aplicamos el operador , y obtenemos

.

El último término requiere un poco de trabajo, pero es simple algebra. Por último, factorizamos los vectores y

A partir de esta ecuación podemos escribir el estado como

donde . Esto lo escribo sin demostrar, debido a que la prueba es larga y bastante laboriosa, pero puede obtenerse con simple algebra.

Ahora necesitamos que la amplitud de sea cercana a 1, y el resto sea cercano a 0. Si el coseno se vuelve 0, pero el problema es que ese número no es necesariamente un entero. Entonces elijamos un entero . Tenemos que y implican. Por lo tanto, para un ángulo pequeño , . De esta forma la probabilidad de éxito, i.e., la probabilidad de obtener el vector es .

El algoritmo original de Grover realizaba este procedimiento con 50% de probabilidades de éxito, aquí (utilizando una técnica presentada en este paper) probamos que la probabilidad de éxito está muy cercana a 1 si se elige apropiadamente el número de iteraciones. En este caso . Si hacemos más iteraciones, debido a la oscilación del estado, la probabilidad de éxito disminuye. Por lo tanto debemos hacer exactamente esa cantidad de iteraciones o un número cercano.

De similar manera podemos demostrar que si tenemos objetos marcados, podemos encontrar uno de esos objetos en con probabilidades de éxito.

En el caso general nuestra iteración principal la podemos escribir de la siguiente forma

donde es un operador unitario, cambia el signo de la amplitud si es el vector 0, y es el oráculo que cambia el signo al vector . Para los detalles de las demostraciones para el caso general consultar el paper Quantum Amplitude Amplification and Estimation. Para el caso del algoritmo de Grover tenemos que .

Otro problema es intentar encontrar todos los objetos marcados, para ello se requiere con una probabilidad de éxito de .

Se puede demostrar también que esta cota superior es óptima, i.e., existe una cota inferior del mismo orden. Pero esa demostración queda para otro día.

Séptimo QPL

2010-02-04T08:15:00.000-03:00

Los días 29 y 30 de Mayo se realizará el séptimo workshop QPL en Oxford, organizado como todos los años por Bob Coecke, Parkash Panagaden y Peter Selinger. Este es el 7mo workshop con estas siglas, sin embargo las siglas han cambiado de significado: en los primeros cuatro las siglas significaban "Quantum Programming Languages" (lenguajes de programación cuánticos) y ahora significa "Quantum Physics and Logics" (física cuántica y lógica) queriendo abarcar un área mucho mayor.

Justo antes del workshop hay una escuela, del 24 al 28.

He presentado trabajos en el 5to QPL y el 6to QPL, veremos si llego a enviar algo para éste (espero que si)... aunque de todas maneras supongo que iré incluso si no presento nada.

SODA 2010

2010-01-18T22:25:00.004-03:00

La conferencia SODA organizada conjuntamente por SIAM y ACM junta a los mejores teóricos de las ciencias de la computación cada año. STOC y FOCS están también al mismo nivel, y las 3 conferencias son consideradas las mejores en ciencias de la computación teórica.

En esta semana se desarrolla en Austin, Texas la conferencia SODA con una selección de papers muy interesantes. Por suerte, estos artículos pueden descargarse gratuitamente desde el sitio web de la coferencia: http://www.siam.org/meetings/da10/

Hay un solo artículo en computación cuántica:

- Martin Rötteler. Quantum Algorithms for Highly Non-linear Boolean Functions. [link]

Y estos otros dos también me llamaron la atención:

- Kenichi Kawarabayashi and Yusuke Kobayashi. The Edge-Disjoint Paths Problems in Eulerian Graphs and 4-edge-connected Graphs. [link]

- Alexandr Andoni, T.S. Jayram, and Mihai Pătraşcu. Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. [link]

Estos dos últimos artículos me interesan porque me encuentro estudiando el query complexity de estos mismos problemas.

Latex en Blogger mejorado

2010-01-09T23:33:00.004-03:00

Encontré una forma mucho más rápida y fácil para escribir latex en blogger. Utilizando el programa mathTex helper, es mucho más fácil insertar latex como figuras, siempre utilizando el enlace a

http://www.forkosh.dreamhost.com/.

Espero que de esta forma sea más eficiente la redacción de tópicos técnicos.

Aprovecho también esta entrada para compartir un par de cursos en mecánica clásica y cuántica en YouTube. Estos cursos fueron dictados por uno de los científicos más influyentes en Teoría de Cuerdas, Leonard Susskind de la Universidad de Stanford. De hecho, el fue quien propuso el modelo de cuerdas de energía en oscilación allá por los años 60.

Hay otros cursos en física, dictados por Susskind, que valen la pena ver. Solo hay que seguir los enlaces de YouTube.

Autómatas Cuánticos para Lenguajes Omega

2010-01-04T05:46:00.086-03:00

Los autómatas cuánticos son, como su contraparte clásica, modelos de computación. La investigación en esta área está un poco dividida. Existen investigadores que sostienen que la conexión de estos modelos con la realidad no es clara y no poseen una realización física, no así los autómatas clásicos, que bien todos conocen claramente sus aplicaciones y su importancia teórica. Aclaro que aquí no incluyo a los autómatas celulares cuánticos. La aplicación de este último está bien estudiada y existe una relación clara con la realidad, como se puede observar haciendo una simple búsqueda por Google. Aquí me estoy refieriendo a los típicos autómatas como autómatas de estado finito, los autómatas de pila o pushdown, etc. Por otro lado, existen investigadores que sostienen que el estudio de estos modelos es importante para entender las ventajas y desventajas de la computación cuántica, y la relación que existe entre el mundo clásico y el cuántico. A mi en particular me interesa desde un punto de vista netamente de la teoría de lenguajes. En esta entrada voy a presentar una propuesta de autómata cuántico para lenguajes omega (i.e., lenguajes con cadenas de longitud infinita), y algunos problemas abiertos.

Primero, definamos formalmente un lenguaje omega (-languages).

Definición 1 (lenguaje- [1]). Sea un alfabeto y L un lenguaje sobre . El conjunto de cadenas de longitud infinita sobre es denotado por . es el conjunto de cadenas en que surge de la concatenación de cadenas en . Formalmente,

Existen dos clases de autómatas clásicos. Primero están los 1-way finite automata (1FA), donde la unidad de control lee un símbolo de entrada y se mueve inmediatamente al siguiente símbolo a la derecha. En segundo lugar están los 2-way finite automata (2FA), donde la unidad de control puede mover el cabezal a la izquierda, derecha, o quedarse en su lugar. Clásicamente, los modelos 1FA y 2FA son equivalentes, pero en el caso cuántico, el poder de reconocimiento de lenguajes cambia radicalmente. Para un tratado completo sobre las diferencias entre el 1FA y 2FA cuánticos referirse a [2].

A continuación presento la definición del autómata cuántico de 1 lado (1-way).

Definición 2 (autómata cuántico de 1 lado [2]). Un autómata cuántico de 1 lado (1QFA) es una tupla donde

- Q es en un conjunto finito de estados,

- es el alfabeto de entrada,

- es el estado inicial,

- F es el conjunto de estados de aceptación o finales,

- R es el conjunto de estados de rechazo con ,

- es la función de transición donde y son marcadores de inicio y final de cadena, y para un símbol y estados q,r, se tiene que ,

- o para algún es un operador unitario (i.e., ) tal que ,

- es un observable definido en la base de , donde , , y es el complemento ortogonal de y .

La computación de para una entrada es como sigue [2]. El operador se aplica al estado inicial y luego es aplicado a . El operador proyecta a un vector en uno de los subespacios , , , con probabilidad igual a . Si la entrada es aceptada y para; si la entrada es rechazada y para; si entonces se vuelve a aplicar el operador a para el siguiente símbolo de entrada y el proceso continua. La computación solo continua si ocurre una proyección en .

Teniendo en cuenta la definición de un autómata cuántico, es fácil extender el autómata para operar con lenguajes-.

Definición 3 (autómata cuántico de 1 lado). Un autómata cuántico de 1 lado es una tupla donde

- Q es en un conjunto finito de estados,

- es el alfabeto de entrada,

- es el estado inicial,

- F es el conjunto de estados de aceptación o finales,

- R es el conjunto de estados de rechazo con ,

- es la función de transición donde es el marcador de inicio de cadena, y para un símbol y estados q,r, se tiene que ,

- o para algún es un operador unitario (i.e., ) tal que ,

- M es un observable definido en la base de , donde , , y es el complemento ortogonal de y .

La computación de para una entrada es de la misma forma que el QFA . La diferencia está en que lee una cadena de longitud infinita, y por lo tanto la condición de aceptación cambia. De acuerdo a la condición de aceptación de Büchi [3], en una corrida de aceptación el autómata visita los estados infinitamente, porque la cadena de entrada es de longitud infinita. Para el caso cuántico, el resultado de la observación genera una secuencia infinita de estados . Si el resultado de la observación es un estado de o la entrada es finita, rechaza y para. En cambio, si existe un número infinito de vectores en la secuencia con una proyección no vacía en el subespacio se acepta la entrada.

Problemas Abiertos

Definición de probabilidad de aceptación de lenguajes. Para autómatas clásicos, el autómata se reduce a una cadena de Markov, y la probabilidad de aceptación de una corrida puede definirse en esos términos [3]. Tal vez lo mismo pueda hacerse para , pero usando en su lugar Quantum Walks [4].
Brecha en la complejidad espacial. En el artículo de Ambainis y Nahimovs [5], se demuestra una brecha exponencial en la complejidad espacial entre el 1FA y el 1QFA para un lenguaje regular específico. Existe un lenguaje- con una brecha exponencial en complejidad espacial?.
Reconocimiento de lenguajes. Si un 1QFA acepta un lenguaje L, entonces L es regular [2]. Pero, se sabe que la clase de lenguajes de los 1QFA está estrictamente incluido en la clase de lenguajes de los FA [2]. Cuáles son las propiedades de reconocimiento de lenguajes de los autómatas cuánticos ?.

Referencias

[1] Christel Baier y Joost-Pieter Katoen. Principles of Model Checking. MIT Press, 2008.

[2] Josef Gruska. Quantum Computing. McGraw Hill, 2000.

[3] Christel Baier, Nathalie Bertrand, y Marcus Größer. The Effect of Tossing Coins in Omega-automata. In: Proceedings of CONCUR'09, pages 15-29, 2009.

[4] Julia Kempe. Quantum Random Walks - An Introductory Overview. arXiv:quant-ph/0303081.

[5] Andris Ambainis y Nikolajs Nahimovs. Improved Constructions of Quantum Automata. Theoretical Computer Science, 410(20):1916-1922, 2009.

ICQIT 2009

2009-12-23T06:46:00.007-03:00

Entre el 2 al 5 diciembre se llevó a cabo el International Conference on Quantum Information and Technology 2009 - ICQIT2009 en Tokyo.

El lugar de la conferencia fue el National Institute of Informatics (NIIS)

La conferencia estuvo muy buena en general divido en dos partes principales: Teoría y Experimentos. Honestamente la parte experimental no es mi fuerte, asi que voy a comentar principalmente sobre la parte teórica, la cual se llevó a cabo en el primer día hasta el segundo día al mediodía.

El programa está aquí. Tres presentaciones me gustaron mucho:

1- Miklos Santha "Quantum Walk Based Search Algorithms". Presentó la teoría de de los quantum walks y su relación con las cadenas de Markov clásicas. El objetivo de la investigación es construir la teoría de quantum walks en base a la teoría ya existente de cadenas de Markov. El contenido de esta presentación estuvo basada totalmente en este paper arXiv:0808.0059.

2- Francois Le Galle "Perfect Quantum Network Communications Protocol Based on Classical Network Coding". Esta presentación me gustó mucho, principalmente porque me gusta la teoría de grafos. El problema consiste en transmitir información cuántica producida a partir de dos nodos en un grafo, pasando a traves de un solo enlace que conecta estos dos nodos iniciales a otros dos nodos receptores. La información cuántica se codifica en el enlace único utilizando un código lineal, y se puede transmitir información clásica sin costo desde los nodos origen a los nodos destino. Se puede probar que un bit de información clásica no es suficiente para resolver el problema. Se puede con 3 bits clásicos, y el caso para 2 bits está abierto. El paper lo pueden encontrar aquí arXiv:0902.1299.

3- Iordanis Kerenidis "How Powerful is a Unique Quantum Witness". Esta fue una presentación en complejidad computacional cuántica en el contexto de los Interactive Proof Systems. La contraparte cuántica de la clase NP en computación cuántica es QMA donde tenemos un verificador y un demostrador igual que en MA. El verificador tiene que decidir a partir de la entrada y un mensaje (llamado testigo o witness) del demostrador la aceptación o rechazo de la entrada. En este trabajo estudian como reducir el número de quantum witnesses a 1. De esta forma intentan entender la dificultad de los problemas en QMA. Este paper esta aquí arXiv:0906.4425.

También conocí a gente muy interesante, principalmente físicos y disfrute muchos los recesos con pláticas muy interesantes. Espero volver el próximo año.

Work-in-progress en el QNET y Bisimilaridad

2009-12-21T18:32:00.003-03:00

Como adelanté en un post anterior, el 10 y 11 de Diciembre estuve en Oxford, en el último Workshop QNET donde presenté un "work-in-progress" de mi trabajo. Aquí dejo los slides y pueden encontrar los slides de muchas de las otras charlas en la página del workshop.

En particular me interesó mucho el trabajo de Tim Davidson: "Equivalence Relations for Communicating Quantum Processes". Es un trabajo sobre "bisimilaridad"... la definición dice (más o menos) que dos procesos cuánticos son bisimilares si actúan igual. Ejemplo, una compuerta identidad es bisimilar a dos Hadamards una detrás de otra. Además, existe una propiedad llamada "congruencia", que dice que si dos procesos son bisimilares, ellos son congruentes si, dado un contexto cualquiera, poner cualquiera de los dos procesos, da como resultado lo mismo.

Tim mostró que los procesos bisimilares a la identidad son congruentes entre sí.

Aunque parezca poco intuitivo, esto no es trivial. No siempre los procesos bisimilares serán congruentes. Por ejemplo, medir un qubit es bisimilar a medir un qubit luego de aplicarle una compuerta Hadamard (en términos de matriz densidad, ambos procesos son indistinguibles), sin embargo, si el qbit a la salida de la medición es utilizado para algo más, pues ya no serán bisimilares (las probabilidades serán diferentes).

Bueno, hubo muchos trabajos interesantes, en particular me gustó este porque hace algunos años hubo gente en mi grupo que trabajó en el tema y es un problema que me parece interesante para intentar abordar... veremos.

Papers de STACS2010

2009-12-07T06:05:00.002-03:00

Esta es una entrada breve y rápida, solo para anunciar que STACS 2010 ya publicó en su sitio web la lista de artículos aceptados.

Entre los papers que destacan sobre computación cuántica estan:

- Francois Le Gall. An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem.

- Sergey Bravyi, Aram Harrow, and Avinatan Hassidim. Quantum algorithms for testing properties of distributions. [arXiv:0907.3920]

Otro que me llamó la atención también es el siguiente:

- Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo. Inseparability and Strong Hypotheses for Disjoint NP Pairs. [sitio web de Jack Lutz]

Aún queda por hacer el reporte de la conferencia ICQIT2009. Me saco de encima un par de reportes y me pongo las pilas para preparar el post.

Primer Post

2009-11-30T06:12:00.003-03:00

Muchas gracias Alejandro por la cordial invitación. Esta es una entrada breve como para introducción y primer post.

Para conocer un poco sobre mí, pueden encontrar detalles en mi perfil de usuario de blogger.

Actualmente me encuentro muy ocupado con reportes, examenes, y otras tareas que me dificultan escribir algo bien hecho. Esta entrada la escribo en modo automático, sin pensar mucho, y salga lo que salga. A ver también si al mismo tiempo mejoro un poco la gramática y ortografía del español a medida que va pasando el tiempo :-)

Solo quiero mencionar los tipos de temas sobre los cuales me gustaría escribir.

1-Reportes de conferencias: Conferencias a la que vaya asistiendo dentro de Japón y fuera. Tengo planeado ir este miércoles a esta conferencia International Conference on Quantum Information Science and Technology que se estará desarrollando en Tokyo. Voy a preparar un reporte con fotos.

2-Investigación: Los trabajos de investigación que estoy realizando sobre Query Complexity y Automátas Cuánticos.

3-Papers: Resúmenes de artículos científicos que me gustaron y me parecen muy interesantes para compartir, dentro y fuera de mi área de especialización. Esto espero me ayudará al mismo tiempo a medir que tan bien entendí el paper.

4-Fundamentos de Computación Cuántica: Tal vez de cuando en cuando, escribir sobre las bases matemáticas requeridas para estudiar computación cuántica, Espacios de Hilbert, Complejidad Computacional, Análisis Complejo, etc. Los que venimos de ciencias de la computación estamos muy acostumbrados a matemáticas discretas, y muchas veces pasar a estudiar análisis puede resultar difícil ya que durante el pre-grado no hay tanto énfasis en esas áreas.

Bueno, esa es la idea, a ver que tal va.

Viajes y novedades en el blog

2009-11-28T15:00:00.001-03:00

Viajes pasados y planificados:

La semana pasada estuve en el PPS en París, donde mi director y co-autor del paper del sistema de tipos "Scalar" dio una charla sobre nuestro paper. Los slides ~~los subiré pronto a mi página (y linkearé aquí)~~ aquí están. La idea es que para los seminarios PPS no aceptan estudiantes de doctorado para dar las charlas, así que por eso la dió Pablo.
El 10 y 11 de Diciembre estaré en Oxford, donde iré al último Workshop QNET a presentar un "work-in-progress" de mi trabajo. QNET es una red británica de investigación en semántica de la computación cuántica (más info en su página).
El 7 y 8 de Enero voy al LDP en Marseille, donde daré la misma charla que dió Pablo en el PPS sobre scalar.

Cambios en el blog:

Dado que ya se está tornando aburrido mi blog, porque está demasiado centrado en mi tema de investigación y no tanto en computación cuántica en general, he invitado a Marcos Daniel Villagra, a quien ya conocen porque publicó un post recientemente en este blog, a que sea co-autor del blog, así le damos un poco más de dinámica. Él también anda bastante ocupado, así que no es que por ser dos ahora habrá post mucho más seguidos, pero al menos los habrá más variados.

Bienvenido Danny!

Pruebas cuánticas para teoremas clásicos

2009-10-23T18:39:00.001-03:00

Interesante preprint de Andrew Drucker (MIT) y Ronald de Wolf (CWI Amsterdam): "Pruebas cuánticas para teoremas clásicos" (Quantum Proofs for Classical Theorems, arXiv:0910.3376).

El paper es un interesante review autocontenido de distintos algoritmos cuánticos, pruebas y métodos y plantea el "framework" de la computación cuántica como un método más para probar teoremas clásicos... por lo tanto, más allá de si la computación cuántica se puede lograr físicamente en realidad o no (o peor aún, si la física cuántica es o no un modelo certero de la realidad), ésta igual sirve como una manera de pensar los problemas.

El paper en sí me pareció muy interesante y lo recomiendo, pero además lo recomiendo como un buen review sobre computación cuántica teórica en general.

Química Cuántica con Computadoras Cuánticas por Carlos Amador-Bedolla y Alán Aspuru-Guzik

2009-10-05T17:27:00.003-03:00

Siguiendo con la serie de posts invitados, Carlos Amador-Bedolla y Alán Aspuru-Guzik, dos investigadores mexicanos (Carlos de la UNAM y Alán de Hardvard) me han enviado este PDF titulado:
Computación Cuántica: Química Cuántica con Computadoras Cuánticas.
(Click en el título para descargar)

El artículo está en español, aquí dejo el resumen:

La superposición de estados y el intrincamiento son características de la naturaleza cuántica que invitan a especular acerca de la construcción, la programación y el funcionamiento de computadoras cuánticas. En particular, se ha especulado acerca de la posibilidad de usarlas para resolver la ecuación de Schrödinger y calcular la energía de un sistema cuántico, es decir, la posibilidad de hacer química cuántica en computadoras cuánticas. Recientemente se demostró que, en principio, esto es posible. Presentamos las ideas básicas del algoritmo cuántico para la solución de la ecuación de Schrödinger y las estimaciones de los recursos que deberá tener la computadora cuántica que implemente este algoritmo.

Gracias Carlos y Alán por la colaboración!

Quantum Query Complexity y Quantum Walks por Marcos Daniel Villagra

2009-10-03T06:04:00.000-03:00

Con este post queda inaugurada la sección "posts invitados". Esperemos con el tiempo encontrar a más hispanohablantes investigando en computación cuántica que quieran participar de esta sección.

Este primer post está escrito por Marcos Daniel Villagra, un investigador paraguayo que trabaja en Japón. Aquí nos cuenta su tema de investigación. Gracias Danny!

A continuación en esta entrada voy a dar una explicación sobre dos áreas muy activas de investigación en computación cuántica: “Quantum Query Complexity” y “Quantum Walks”. Espero no haberme alargado mucho, y más importante, espero la explicación haya sido clara. Para una lectura amena, es recomendable un conocimiento básico en análisis de algoritmos.

Query Complexity” consiste en el estudio de la complejidad temporal de los algoritmos basados en oráculos. Un oráculo es como una caja negra, a la cual podemos hacer una pregunta y retorna la respuesta en una unidad de tiempo, e.g., cual es el costo de un camino en un grafo, número de cláusulas satisfechas en de una fórmula Booleana, etc. Aquí el tiempo se mide en cuantas consultas hacemos al oráculo hasta encontrar la respuesta. Considerando un problema de búsqueda general en donde se busca uno o varios elementos de un conjunto de n objetos en total, encontrar la respuesta quiere decir que obtenemos una respuesta del algoritmo con una probabilidad 1 o 1-ε donde ε > 0, i.e., el error ε esta acotado. Entonces “Quantum Query Complexity” es el estudio de la complejidad temporal de algoritmos cuánticos basados en oráculos. El ejemplo más claro de este tipo de algoritmos es el famoso algoritmo de Grover, el cual encuentra una respuesta en O(√n) consultas al oráculo con una probabilidad de por lo menos 1/2. Ni siquiera es necesario mirar todos los objetos para tener una respuesta!! Clásicamente encontramos un objeto en O(n). Fíjense que el algoritmo da una respuesta con 50% de probabilidad, pero gracias a las estadísticas podemos diseñar un experimento para que luego de varias repeticiones del algoritmo, la probabilidad sea muy cercana a 1. Es importante notar que este algoritmo es óptimo, esto quiere decir que para encontrar un objeto con error acotado tenemos que hacer por lo menos √n consultas al oráculo.

Actualmente la investigación en esta área está concentrada en mejorar los algoritmos de búsqueda por una constante, por ejemplo, digamos que hay un algoritmo A que encuentra elementos en a√n consultas al oráculo donde a es una constante dependiente del problema, entonces podemos diseñar un algoritmo B que encuentra elementos en 0.5a√n consultas por medio de mejoras que podemos hacer a A. Encontrar un algoritmo como B no es tarea sencilla, y depende mucho del tipo de problema (SAT, TSP, “Triangle Finding”, etc.) y de la estructura interna del espacio de estados de dicho problema. Por ejemplo, para el problema de encontrar triángulos en un grafo, el algoritmo requiere O(n^7/10) consultas (siempre con error acotado).

Un agregado muy importante que poseen los algoritmos clásicos son las heurísticas. Una heurística es una forma de captar información del problema y utilizarla para hacer un algoritmo más eficiente. En general, no hay forma aun de implementar heurísticas o captar información estructural en los algoritmos de busqueda cuánticos. Existen pocas propuestas, pero no son del tipo de información estructural que puede ser captada por algoritmos clásicos. En este punto es donde entran los “Quantum Walks”.

Un “Quantum Walk” es la contraparte cuántica de los “Random Walks”. Consiste en la simulación del movimiento de una partícula sobre un grafo. Cada arco del grafo posee una probabilidad de transición de un nodo a otro, y la partícula se mueve de un punto a otro teniendo en cuenta estas probabilidades. Pero tratándose de una partícula cuántica, esta se mueve en superposición, esto quiere decir, que la partícula puede estar en varios nodos al mismo tiempo. Los “Random Walks” y “Quantum Walks” se pueden usar para diseñar algoritmos, y existe en la actualidad una vasta literatura que demuestra como este paradigma puede ayudar mucho en mejorar el rendimiento de los algoritmos. Dependiendo de la conectividad, topología, y otras propiedades del grafo la complejidad del algoritmo cambia. De hecho, se puede demostrar que la búsqueda de Grover corresponde a un “Quantum Walk” sobre un grafo totalmente conectado. También depende el tipo de “Quantum Walk” que se utilice, el cual puede ser de tiempo discreto o continuo.

Mi trabajo de investigación consiste en el estudio de los “Quantum Walks”, desde sus propiedades hasta sus aplicaciones algorítmicas y la complejidad de estas soluciones. En este último punto estamos tratando de explotar información estructural de los problemas de búsqueda para crear así algoritmos eficientes.

Para una introducción a los “Quantum Walks” recomiendo http://arxiv.org/abs/quant-ph/0303081. El algoritmo de Grover lo van a poder encontrar en el siguiente enlace http://arxiv.org/abs/quant-ph/9605043.

Computación Cuántica, Teoría de Tipos y Lógicas Cuánticas

2009-09-23T07:14:00.000-03:00

Más de uno me ha preguntado por el significado del subtítulo del blog: "Computación Cuántica, Teoría de Tipos y Lógicas Cuánticas", así que trataré de resumirlo aquí en un lenguaje lo más entendible posible (y cualquier cosa que no quede clara, pregunten en los comentarios (o corríjanme si encuentran algún error))

Este es mi tema de investigación del doctorado. Existen muchas lógicas matemáticas diferentes, como por ejemplo (y estas son sólo algunas): Lógica proposicional, Lógica de primer orden, Lógica de segundo_orden, Lógica difusa, Lógica relevante, Lógica no monotónica, Lógica intuicionista, Lógica modal, Lógica temporal y hasta incluso existe una llamada Lógica cuántica.

Por otro lado, existe una teoría llamada Teoría de Tipos, que, en su forma más básica, permite caracterizar un algoritmo sin necesidad de ejecutarlo. O sea, tenemos un algoritmo y podemos definir qué "tipo" tiene ese algoritmo, lo cual nos da alguna información relevante que queremos saber sobre el resultado al finalizar la ejecución de dicho algoritmo.

La idea es que uno tiene ciertas reglas que dicen cómo decidir si un algoritmo tiene cierto tipo. Veamos un ejemplo sencillo de regla: siempre que tengamos un algoritmo, vamos a llamarlo A1, de "tipo" booleano (cuando tiene tipo booleano lo que estamos diciendo es que su resultado puede ser uno de dos valores: "verdadero" o "falso" y no por ejemplo un número) y otro algoritmo, A2, también booleano, entonces el algoritmo "A1 and A2" tendrá también tipo booleano. Esto se escribe en símbolos así:

A1:Bool     A2:Bool

--------------------

A1 and A2: Bool

Vamos con un ejemplo un poco más complicado:

F: Bool => Numero   A: Bool

-------------------------------

F(A): Numero

Esto dice que si tengo una función que toma un booleano y devuelve un número, entonces la función aplicada a un booleano, será de tipo número.

Y qué tiene que ver esto con lógica?

Bien, la idea es que cada conjunto de reglas define una lógica. Esto fue descubierto por el matemático Haskell Curry y el lógico William Howard y se lo llama la correspondencia de Curry-Howard. Cómo funciona? Pongamos por ejemplo la segunda regla escrita arriba:

F: Bool => Numero   A: Bool

-------------------------------

F(A): Numero

Si nos olvidamos de los "algoritmos" y nos quedamos sólo con los tipos, la regla quedaría así:

Bool => Numero   Bool

----------------------

Numero

La cual no es más que la regla lógica de implicación: Si Bool implica Número y tengo Bool, entonces tengo Número.

Diferentes reglas de tipado nos darán diferentes lógicas. La correspondencia nos asegura que por cada "fórmula bien formada" en nuestra lógica, tendremos un "algoritmo" capaz de producir una salida con ese tipo.

Y qué tiene que ver esto con computación cuántica?

Como mencioné antes, existe una lógica cuántica, pero esa lógica fue inventada mucho antes de la computación cuántica; fue desarrollada en base a la mecánica cuántica, de manera ad-hoc, tratando de capturar su comportamiento. Luego, con el advenimiento de la computación cuántica, se ha tratado intensamente de hacer una correspondencia entre los algoritmos cuánticos y la lógica cuántica, para lo cual se ha ido modificando la lógica a medida que avanzan las investigaciones de manera de adecuarla a los algoritmos.

Mi trabajo de investigación es empezar por el otro lado desde cero: ya hay lenguajes cuánticos definidos¹, por lo tanto, si puedo definir un sistema de tipos para él, tendré una lógica cuántica definida directamente desde los lenguajes cuánticos (y con ello se podría analizar diferentes algoritmos a partir de su lógica).

Espero se haya entendido la explicación, y sino, sientanse libres de preguntar en los comentarios del blog.

----------------------------------------------

1 En particular hay lo que se llama un lambda cálculo, que es una especie de lenguaje muy básico que permite expresar cualquier algoritmo. En realidad, hay varios, yo en particular uso el Linear-Algebraic Lambda-Calculus de Pablo Arrighi y Gilles Dowek.

Reporte desde la escuela: audios

2009-08-28T17:06:00.003-03:00

Los audios (y en algunos casos los slides) de la Canadian Quantum Information Summer School 2009 han sido subidos a www.fields.utoronto.ca/audio (además allí se pueden bajar audios de distintos eventos que se han realizado en el Fields Institut, muchos de ellos sobre computación cuántica). Ya actualicé mis posts del Reporte desde la Escuela agregando los links al lado de cada comentario de cada charla.

Reporte desde la escuela: 5to día

2009-08-21T20:34:00.011-03:00

Quinto y último día de escuela, y aquí va el reporte de hoy:

Por la mañana tuvimos otra clase de Jonathan Baugh (audio de la clase aquí), esta vez hizo un resúmen sobre varias de las implementaciones experimentales más populares de la computación cuántica (aparte del MNR que explicó en detalle ayer):

- Trampas de iones.

El esquema básico se puede leer desde este paper: Quantum Computations with Cold Trapped Ions (disponible gratis aquí). Y sobre cómo se realizan mediciones en este esquema está detallado en este otro paper: High-fidelity readout of trapped-ion qubits.

Mostró además los experimentos que se han realizado en varios laboratorios y cuáles son los problemas actuales, ahora que están enfrentando el desafío de meter muchas trampas de iones en chips de silicio.

- Circuitos superconductores.

El esquema básico está detallado en este paper: Superconducting qubits. Y los artículos más recientes e influyentes (de esos que llegan a la revista Nature) son:

Coupling superconducting qubits via a cavity bus (también en arXiv:0709.2135)
Demonstration of two-qubit algorithms with a superconducting quantum processor (también en arXiv:0903.2030).

- Quantum Dots.

La propuesta original está en Quantum Computation with Quantum Dots. Y algunos de los artículos más recientes e influyentes (en Nature, Science y Nature Physics) son:

Coherent Manipulation of Coupled Electron Spins in Semiconductor Quantum Dots (también en la página del grupo)
Driven coherent oscillations of a single electron spin in a quantum dot (también en arXiv:cond-mat/0608459)
Coherent Control of a Single Electron Spin with Electric Fields (también en arXiv:0707.3080)
Electrically driven single-electron spin resonance in a slanting Zeeman field (también en arXiv:0805.1083)

Además dejó un link donde se pueden encontrar varios tutoriales sobre información cuántica en general y sobre implementaciones en particular: www.iqc.ca/publications/tutorials.php.

Luego fue el turno de Norbert Lütkenhaus (audio aquí), quien habló durante dos horas sobre Quantum Key Distribution. En particular explicó el BB84, con mucho detalle, más de lo que yo conocía. Por ejemplo, explicó el tema de que hay dos ataques que el BB84 no soporta: DoS y Man-in-the-middle. DoS (Denegación de Servicio) es claro que no lo puede soportar desde el punto de vista teórico, porque desde el protocolo, no hay forma de evitar que alguien nos "corte la línea" por ejemplo. Ahora, el man-in-the-middle si tiene una posible solución: El man-in-the-middle funciona de esta manera, supongamos que Alice se quiere contactar con Bob para transmitir la clave. El BB84 es muy seguro, pero resulta que Eve se pone en el medio y Eve se contacta con Alice haciéndole creer que es Bob y con Bob haciéndole creer que es Alice. Entonces, la generación de la clave privada no será secreta, ya que Eve podrá tener una clave k1 con Alice y otra k2 con Bob y lo único que debe hacer es, al recibir un mensaje de Alice, desencriptarlo con la clave k1 y encriptarlo con la clave k2 para reenviárselo a Bob.

Lo que se necesita para evitar este ataque es alguna manera de chequear que Alice y Bob tienen la misma clave. Para hacer esto, simplemente al finalizar de generar la clave, usan algo como RSA o algún método clásico de criptografía para enviarse parte de las claves generadas, una parte que luego descartarán (i.e. previamente tienen que tener las claves públicas de RSA de la otra persona) y todo funciona. Un momento... ¿no es que el RSA no es seguro ya que basa su seguridad en la potencia de las computadoras para factorizar números?, bueno sí, pero para romper el RSA al menos se deberían necesitar unos minutos (bueno, se calcula que se necesitarían años, pero supongamos que Eve cuenta con una computadora muy potente), y ese delay delataría a Eve! O sea: si lo envía como viene y estaba en el medio, Alice y Bob notarán que k1 y k2 son distintas. Si lo envía luego de romper la clave RSA para codificarlo de nuevo, Alice y Bob notarán el delay. Si sólo estaba escuchando y no interviniendo, no importa que rompa la clave RSA, ya que con esa clave sólo se encriptó un pedazo de la clave del BB84 que se descartará.

Lo que siguió fue una explicación del Entanglement based QKD y QKD sobre canales con ruido, de lo que se puede leer un poco más en este paper: Shor and Preskill's and Mayers's security proof for the BB84 quantum key distribution protocol (no lo encontré con acceso libre, así que lo subo a megaupload).

La última hora la dedicó a las implementaciones ópticas del QKD, y dejó este paper: Unconditionally secure one-way quantum key distribution using decoy pulses (también en arXiv:quant-ph/0610015)

El último curso, de dos horas, estuvo a cargo de Daniel Lidar (audio y slides aquí (primera parte) y aquí (segunda parte)). Hablo sobre un método para prevenir y corregir los errores en los experimentos cuánticos llamado Hybrid quantum error prevention, reduction and correction. Los slides aún no están disponibles, pero en su página están los slides de este mismo curso dictado hace unos años. La verdad que de este curso entendí poco y nada porque dio demasiados detalles de la implementación física que no manejo.

Bueno, para finalizar, les cuento que todos los slides y las grabaciones de audio de las charlas ~~van a ser~~ (han sido) puestas en www.fields.utoronto.ca/audio (allí además se pueden encontrar grabaciones y slides de otras charlas dictadas en el Fields Institut). ~~En cuanto estén disponibles, actualizo mis posts para agregar los links a cada una de las charlas.~~ (hecho)

Por último, me queda agradecer por el financiamiento al Fields Institut, a mi grupo de investigación por medio del proyecto QICS y a la escuela doctoral de la Université de Grenoble.

Reporte desde la escuela: 4to día

2009-08-20T20:42:00.005-03:00

Cuarto día de escuela, y continúa el reporte:

Por la mañana, Panos Aliferis continuó su curso (audio aquí), haciendo un resúmen de lo hablado ayer, y continuando con la demostración de su teorema. Demostró el teorema principal de su tesis de doctorado, que básicamente dice "El error (o ruido de ambiente) puede hacerse tan chiquito como uno quiera, con la codificación adecuada del sistema". Para profundizar sobre el tema, su tesis doctoral está disponible en el arXiv: Level Reduction and the Quantum Threshold Theorem (125 páginas).

Luego fue el turno de John Yard (audio), quien habló de teoría de la información cuántica (partiendo desde la teoría de la información clásica se Shannon). La idea original de Shannon básicamente es probar que el error en una comunicación tiende a cero cuando el mensaje a transmitir es mayor. La idea es probar lo mismo para el caso de los canales cuánticos. Para profundizar en este tema, los capítulos 10 y 11 del Nielsen & Chuang son un buen punto de partida, aunque lamentablemente ese libro no está online. También hay un interesante paper que dejó para leer en el arXiv: The private classical capacity and quantum capacity of a quantum channel (20 páginas).

Por la tarde, Jonathan Baugh dio una introducción al NMR (Resonancia Magnética Nuclear) y el NMR QIP (Procesado de la Información Cuántica mediante NMR) (audio). Explicó toda la física de cómo trabaja el NMR y cómo corren algoritmos cuánticos mediante esta técnica, la forma de implementar rotaciones arbitrarias de un qubit y la compuerta CNOT (con lo cual pueden correr cualquier algoritmo, ya que rotaciones de un qubit y CNOT forman un conjunto universal de compuertas). Y dejó varias referencias para profundizar:

Libros sobre NMR:

(ninguno de los tres está disponible gratis)

Spin dynamics: basics of nuclear magnetic resonance de Malcolm Levitt (2003)
The principles of nuclear magnetism de Anatole Abragam (1961)
Principles of magnetic resonance de Charles Slichter (1996)

Reviews de NMR QIP:

NMR techniques for quantum control and computation (33 páginas)
Quantum information processing using nuclear and electron magnetic resonance: review and prospects (24 páginas)
NMR Based Quantum Information Processing: Achievements and Prospects (33 páginas)

Por último, la última de las charlas distinguidas de Matthew Hastings (audio y slides), quien continuó con la simulación cuántica pero esta vez hablando de sistemas que evolucionan en el tiempo. Mencionó el método TEBD (Time-evolving block decimation) y mostró cómo se podía mejorar este método utilizando física relativista, aún cuando la teoría cuántica no es relativista, demostró que se obtiene una muy buena aproximación si se la considera relativista y que nada fuera del cono de luz afecta al sistema (o casi) por lo cual, con analizar sólo lo que está bajo el cono, es suficiente. Básicamente lo que hizo fue explicar dos trabajos suyos recientes: Observations Outside the Light-Cone: Algorithms for Non-Equilibrium and Thermal States (2008) y Light Cone Matrix Product (2009).

Reporte desde la escuela: 3er día

2009-08-19T19:21:00.011-03:00

Tercer Reporte desde la escuela.

Hoy estuvo dedicado al Quantum Error Correction. Por la mañana, empezó Daniel Gottesman con un curso de 2hs (audios y slides aquí (primera parte) y aquí (segunda parte)). En la primer hora presentó los tipos de error y los métodos de corrección para errores de bit flipping (el equivalente a la aplicación de una compuerta X) y phase flipping (el equivalente a la aplicación de una compuerta Z). Luego mostró un teorema que muestra que si se conoce cómo corregir un error equivalente a la aplicación de una compuerta A y otro equivalente a una compuerta B, entonces se conoce cómo corregir ∂A+ßB. Además, es fácil corregir Y=iXZ. Y como cualquier compuerta 2x2 puede expresarse como µI+øX+ßY+∂Z, entonces se puede corregir cualquier error (de un sólo qubit).

Lo que siguió fue una generalización de esto y entrar en detalle con los métodos.

Si alguien está interesado en seguir más en detalle, Daniel dejó unas cuantas fuentes de información para aprender de allí (incluyendo su propia tesis de doctorado):

An Introduction to Quantum Error Correction (15 páginas)
Fault-Tolerant Quantum Computation (6 páginas)
An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation (46 páginas)
Capítulo 10 del libro de M. Nielsen e I. Chuang Quantum Computation and Quantum Information. (Lamentablemente este no se consigue online)
Capítulo 7 del Quantum Information Lecture Notes de John Preskill.
Quantum accuracy threshold for concatenated distance-3 codes (58 páginas)
Stabilizer Codes and Quantum Error Correction (114 páginas) (Esta es la tesis de doctorado de Daniel Gottesman)
Y hay algunas cosas más en su página personal.

El siguiente curso fue de Panos Aliferis (audio aquí), quien continuó hablando sobre Quantum Error Correction, pero desde un punto de vista mucho más físico. Pensando en evolución de sistemas físicos en lugar de algoritmos cuánticos, lo que se tiene es que el "ruido" del ambiente no se reduce, lo que se hace es cambiar el sistema en uno distinto (codificado) el cual tiene el mismo ruido, y ese sistema codificado + ruido es equivalente al sistema original + un ruido menor. Interesante perspectiva!

A eso lo expresó por medio de un teorema:

Quantum Threshold Theorem:

Supongamos que tenemos un ruido probabilístico con una "potencia" de ε < ε0. Entonces, ∀∂ > 0, ∀ circuito de tamaño L, ∃ una codificación del circuito con un ruido efectivo de potencia εeff < ∂.

La demostración de este teorema es realmente compleja, y la inició hoy, explicando algunas ideas intuitivas y la idea es terminarla mañana en detalle.

La tarde de hoy la tuvimos libre, por lo que aproveché para caminar por la ciudad y sacar algunas fotos. Dejo una de un College del campus de la Universidad de Toronto y otra de la CN Tower.

Reporte desde la escuela: 2do día

2009-08-18T20:27:00.005-03:00

Continuando con el Reporte desde la escuela, comento el día de hoy.

Por la mañana, John Watrous dio 2hs de curso sobre complejidad computacional, explicando varias clases de complejidad conocidas con ejemplos de problemas en dichas clases. Si les interesa el tema, el Complexity Zoo de Scott Aaronson tiene un listado muy detallado de las clases de complejidad conocidas. (audio del curso aquí (primera parte) y aquí (segunda parte))

Luego Guifre Vidal dio un curso sobre Entanglement, explicando qué es, la descomposición de Schmidt, algunas mediciones de entanglement, etc. Básicamente siguió el Vol 1, No 1 de Quantum Information and Computation. (audio aquí)

Por la tarde, otra vez el turno de Guifres Vidal, esta vez explicando Entanglement in many-body systems: cómo caracterizar parte de un sistema muy grande, por su nivel de entanglement, lo que sirve para hacer simulaciones de sistemas cuánticos grandes. También explicó el Tensor Network Algorithm el cual es un modelo utilizado para varias simulaciones. (audio aquí)

Para finalizar, otra charla distinguida de Matthew Hastings, esta vez sobre The Computational Complexity of Ground States of Quantum Systems. Lo que hizo fue combinar las dos charlas previas: mostró dos métodos muy conocidos de simulación, Quantum Monte Carlo y Density Matrix Renormalization Group (o DMRG), y sus complejidades. (audio y slides aquí)

Algo interesante sobre las clases de complejidad cuando se habla de simulación, es la caracterización que Hastings hizo, bien simple, en sentido común uno diría que:

Pre-quantum: P es fácil, NP es difícil.
Quantum: P y BQP son fáciles, NP y QMA son difíciles.
Simulando sistemas cuánticos en computadoras clásicas: P y NP son fáciles*, y BQP y QMA son difíciles.

Interesante...

* teniendo un problema NP, al menos se tiene una descripción clásica del estado cuántico!

Reporte desde la escuela: 1er día

2009-08-17T20:07:00.005-03:00

Hoy fue el primer día de la Canadian Quantum Information Summer School en la que estoy participando en el Fields Institute de Toronto.

Por la mañana hubo dos charlas: una a modo de introducción muy rápida a la computación cuántica (por David Kirbs, audio de la charla aquí) y otra sobre algoritmos (por Michele Mosca, audio), que trató de cubrir todos los tipos de algorimos cuánticos conocidos hasta la fecha. Además, Michele dejó un interesante link al Quantum Algorithm Zoo de Stephen Jordan.

Por la tarde, Barry Sanders (audio aquí) habló durante dos horas (sin break) sobre dos tipos de implementaciones prácticas de la computadora cuántica: con fotones, por medio de lasers, sobre lo cual explicó algunos experimentos que se han llevado a cabo, y con chips de silicio, lo que explicó bastante en detalle.

Para terminar, una charla invitada de Matthew Hastings acerca de los quantum channels (audio y slides aquí).

Supongo que cuando termine la escuela, colgarán las transparencias de las charlas en algún lado. Aviso cuando sepa. Update: www.fields.utoronto.ca/audio

A System F accounting for scalars

2009-07-31T09:03:00.002-03:00

Hoy hemos enviado la versión extendida del paper del Scalar Type System a un journal internacional. El preprint se puede descargar del arXiv (arXiv:0903.3741).
Esta versión incluye:

La prueba completa de subject reduction
La prueba completa de strong normalisation
La definición formal y prueba del probabilistic type system
La prueba completa del teorema de no-cloning