21 de diciembre de 2010

Explicación del paper, legible por humanos.

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.

17 de diciembre de 2010

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

(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 announced "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 anunciado "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.

9 de diciembre de 2010

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

(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

30 de noviembre de 2010

Communication complexity lower bounds

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”,

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:
  1. Embed the communication matrix onto the reals. This is done by a mapping from some operator norm to an euclidean norm.
  2. Formulate the problem using the embedding as a maximization problem.
  3. 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.

23 de noviembre de 2010

Back to blogging in spanglish

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.


22 de noviembre de 2010

Empezando a bloggear en English

(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

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

18 de octubre de 2010

Slides Types 2010

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.

30 de septiembre de 2010

Types 2010

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.

21 de septiembre de 2010

Más novedades: Caminatas Cuánticas

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.

8 de septiembre de 2010

Algunas novedades

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:


  1. 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.
  2. 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.
  3. Ya está el CFP de STOC'11.
  4. También la conferencia LAGOS'11 que se llevará a cabo en Bariloche. Esto es para los fanáticos de teoría de grafos.

16 de agosto de 2010

La importancia de P vs NP

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.

10 de agosto de 2010

Una prueba de que P ≠ NP?

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?

22 de julio de 2010

Número de sumas de subconjuntos

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 Fq un campo finito con característica p tal que p < q (i.e. no es un campo primo). Sea D Fq un subconjunto con |D| = n. El problema de la suma de subconjuntos consiste en encontrar un subconjunto no vacío {x1,,xk}⊆ D tal que x1 + ...  xk = s dado s Fq. 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 \begin{pmatrix} n\\ k \end{pmatrix} candidatos. Sea D = {a1,,an} y definamos la variable aleatoria X como la suma de k elementos de D, i.e. X = ax1 + ... + axk. Las variables xi son índices. Tenemos asi que Pr(X = 0) = P(X = 1) =\dots= P(X = s) = \dotsP(X = q - 1) = \frac{1}{q}. 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 x1 + ... + xk. Para una D aleatoria con |D| = n la probabilidad p de que todas las xi 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 xi. 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.

11 de julio de 2010

Theory Overflow

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.

2 de julio de 2010

Papers de FOCS 2010

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

25 de junio de 2010

Panel de expertos en Computación Cuántica

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.

17 de junio de 2010

Oxford → Marsella → Turín

Las últimas semanas he estado viajando un poco:

1 de junio de 2010

Matematicas para Computación Cuántica

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.

18 de mayo de 2010

Criptografía cuántica «comercial», crackeada

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:

Equivalencia de λ-cálculos algebraicos

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 Vauxalg), el cual es un fragmento del differential λ-Calculus, puede simular el Linear-Algebraic λ-Calculus de Pablo Arrighi y Gilles Doweklin), 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

(\lambda x.x\ x)\ (\alpha.t+\beta.u)

reduce a

(\alpha.t+\beta.u)\ (\alpha.t+\beta.u)\ \to\ \alpha.((t)\ \ (\alpha.t+\beta.u))+\beta.((u)\ \ (\alpha.t+\beta.u))

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

\alpha.(\lambda x.x\ x)\ t+\beta.(\lambda x.x\ x)\ u\ \to\  \alpha.(t\ t)+\beta.(u\ u)

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.

12 de mayo de 2010

Computational Complexity in a Nutshell

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.


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

18 de abril de 2010

Arquitectura de Computadores Cuánticos

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.

12 de abril de 2010

Papers de ICALP 2010

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.

27 de marzo de 2010

Trabajos en progreso

  • 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 Update: Paper aceptado en DCM 2011
  • 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"). Update: paper finalizado y aceptado 
  • 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 JaskelioffUpdate: el trabajo final, en forma de paper, ya fue publicado 
  • 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

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.

11 de marzo de 2010

Videos de QIP 2010

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.

1 de marzo de 2010

Escuela de verano canadiense en Información Cuántica

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.

23 de febrero de 2010

AQIS 2010

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.

16 de febrero de 2010

Amplificación de Amplitud

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 |\Psi\rangle un estado cuántico definido en un espacio de Hilbert \mathcal{H}=span\{|i\rangle\quad : \quad 1\leq i \leq n\}, donde cada |i\rangle es un vector de la base de \mathcal{H} (siempre \parallel |\Psi\rangle \parallel=1). En un problema de búsqueda sin información, para encontrar un índice dado k, donde 1\leq k \leq n, la técnica de amplificación de amplitud ubica el vector base |k\rangle en |\Psi\rangle=\alpha_1|1\rangle+\cdots+\alpha_k|k\rangle+\cdots+\alpha_n|n\rangle con amplitud \alpha_k, y sustituye ese valor por otro \alpha_k' 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 |\Psi\rangle 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 k con probabilidad |\alpha_k|^2 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 |0\rangle un operador que genera el vector
 |\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i,j}|i\rangle\langle j|,
i.e., una superposición con la misma amplitud para todos los elementos de la base. Luego, sobre |\psi\rangle se aplica un número t de veces dos operadores unitarios: el oráculo O y el operador de difusión G. Entonces el algoritmo luce algo como \left(GO\right)^t|\psi\rangle. Vamos a probar que t=O(\sqrt{n}), y retorna k con una probabilidad O(1-1/n).

Primero el oráculo O es un operador de fase (reflexión), y su acción se basa en cambiarle el signo a la amplitud de la base |k\rangle dejando el resto sin alterar. Se define como O|x\rangle|q\rangle=|x\rangle|q\oplus f(x)\rangle, donde x es la entrada a la función del oráculo, y q es el bit del oráculo el cual se invierte si f(x)=1 (el operador \oplus 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 q a (|0\rangle-|1\rangle)/\sqrt{2} , la acción del oráculo puede resumirse en

O|x\rangle=(-1)^{f(x)}|x\rangle,

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

G=\begin{bmatrix}2/n-1    & 2/n & \cdots & 2/n\\2/n      & 2n-1 & \cdots & 2/n\\\vdots &      &  \ddots      & \vdots\\ 2/n   & 2/n  & \cdots & 2/n-1\end{bmatrix},

o en notación de Dirac

G=\sum_{i=1}^n (\frac{2}{n}-1) |i\rangle\langle i|+\sum_{i\neq j} \frac{2}{n}|i\rangle\langle j|.

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 G=2|\psi\rangle\langle\psi|-I.

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

|\Psi\rangle=\alpha|k\rangle+\sum_{i\neq k}\beta|i\rangle.
La norma de los vectores debe de ser siempre 1, por lo tanto \alpha^2+(n-1)\beta^2=1(tenemos un solo \alpha porque solo hay un único vector objetivo, y (n-1)\beta porque esos vectores no representan una solución al problema). Denotemos por |\Psi\rangle^{(t)} el estado del algoritmo en el tiempo t. Vamos a calcular cual es la realción entre |\Psi\rangle^{(t)} y |\Psi\rangle^{(t+1)}. Primero aplicamos el oráculo

O|\Psi\rangle^{(t)}=-\alpha|k\rangle+\sum_{k\neq i}\beta|i\rangle.
A continuación aplicamos el operador G, y obtenemos

\begin{array}{ll}G\left(-\alpha|k\rangle+\sum_{k \neq i}\beta|i\rangle\right) &=-\alpha(\frac{2}{n}-1)|k\rangle-\sum_{i\neq k}^n \alpha \frac{2}{n}|i\rangle+\left(\sum_{i=1}^n (\frac{2}{n}-1)|i\rangle\langle i|\right)\left(\sum_{i \neq k}\beta|i\rangle\right)\\&=\alpha\frac{(n-2)}{n}|k\rangle-\alpha\sum_{i\neq k}^n\frac{2}{n}|i\rangle+\sum_{i\neq k}^n(\frac{2}{n}-1)\beta|i\rangle+\beta\frac{2}{n}\sum_{i\neq k}^n(n-2)|i\rangle+\beta\frac{2}{n}(n-1)|k\rangle\end{array}.

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

|\Psi\rangle^{(t+1)}=\left[\frac{(n-2)}{n}\alpha+2\frac{(n-1)}{n}\beta\right]|k\rangle+\left[\frac{(n-2)}{n}\beta-\frac{2}{n}\alpha\right]\sum_{i=1}^n|i\rangle.

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

|\Psi\rangle^{(t)}=\sin((2t+1)\theta)|k\rangle+\sum_i\frac{1}{\sqrt{n-1}}\cos((2j+1)\theta)|i\rangle

donde \sin^2\theta=1/n. 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 |k\rangle sea cercana a 1, y el resto sea cercano a 0. Si t=(\pi-2\theta)4\theta el coseno se vuelve 0, pero el problema es que ese número no es necesariamente un entero. Entonces elijamos un entero \tilde{t}=\lfloor\pi/4\theta\rfloor. Tenemos que |(2\tilde{t}+1)\theta-(2t+1)\theta| \leq \theta y \cos((2t+1)\theta)=\pi/2 implican\cos((2\tilde{t}+1)\theta)\leq\sin\theta. Por lo tanto, para un ángulo pequeño \theta, \cos^2((2\tilde{t}+1)\theta) \leq \sin^2\theta=1/n. De esta forma la probabilidad de éxito, i.e., la probabilidad de obtener el vector |k\rangle es 1-1/n.

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 \tilde{t}=\lfloor\pi/4\theta\rfloor=O(\sqrt{n}). 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 K objetos marcados, podemos encontrar uno de esos objetos en O(\sqrt{n/K}) con 1-K/n probabilidades de éxito.

En el caso general nuestra iteración principal \left(GO\right)^t|\psi\rangle la podemos escribir de la siguiente forma

-AS_0A^{-1}S_k

donde A es un operador unitario, S_0 cambia el signo de la amplitud si es el vector 0, y S_k es el oráculo que cambia el signo al vector |k\rangle. 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 A=W.

Otro problema es intentar encontrar todos los objetos marcados, para ello se requiere O(\sqrt{Kn}) con una probabilidad de éxito de 2^{-\Omega(K)}.

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.