ICQIT 2009

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
  

Algunas novedades

Bueno, hace mucho que no escribo nada por acá, así que comentaré un poco en qué ando.

• El paper del Scalar Type System lo ampliamos bastante con todas las demostraciones y detalles y estamos a punto de enviarlo a la revista Theoretical Computer Science. Pronto subiré la versión extendida. Aquí está.
• Estuve trabajando en agregar subtyping al Vectorial Type System con Barbara Petit a quién visité hace unos meses y también haciendo muchos cambios a ese sistema de tipos.
• El 18 de Mayo fui a visitar al grupo LAMA en Chambéry, donde dí una charla acerca de este sistema de tipos.
• En agosto voy a Toronto, Canadá a una escuela de verano: Canadian Quantum Information Summer School, lo cual me genera muchas expectativas ya que espero poder ampliar un poco el panorama y tomar algún otro tema en paralelo con el que estoy desarrollando (para no quedarme estancado sólo con esto).

Bueno, esto es un resumen de los últimos meses, ya que he tenido bastante abandonado el blog. Dentro de poco estaré subiendo la versión extendida de Scalar al arXiv (ni bien la enviemos al journal) y pondré un link por aquí (arxiv:0903.3741), y a mi vuelta de Canadá, comentaré un poco de la escuela.

Video Abstracts en el Quantiki

Hoy me llegó un email de Martin Plenio del Imperial College. En su email me comentaba que él y Daniel Burgarth (Oxford) han creado una nueva herramienta para la difusión de papers a la cual llaman Video Abstracts. La idea es bien simple: grabar un pequeño video de unos 5 minutos en frente a un pizarrón, donde el autor explique de qué se trata el paper. O sea, en lugar de tener un abstract escrito, tenemos un video del abstract, lo cual puede ser mucho mas interesante.
Estos videos son subidos a YouTube y linkeados a los papers del arXiv.
Es una idea reciente, pero los primeros video abstracts ya pueden encontrarse en el Quantiki, bajo el artítulo Video Abstracts.
Espero pronto estar grabando alguno para contribuir con la idea, la cual me parece muy buena!

Visita al TypiCal

Los días lunes y martes pasados estuve visitando a Benoît Valiron del proyecto TypiCal en la École Polytechnique de París. Allí dí un seminario (abstract y transparencias aquí) y estuvimos debatiendo con Benoît sobre el trabajo que estoy haciendo.

Fue una muy productiva visita!

Estación de RER donde está la École

Mi hotel estaba a sólo unas cuadras de la torre, así que el martes a la mañana aproveché para ir hasta allí y tomar algunas fotos antes de ir al Laboratorio.

Vectorial, Lógica Lineal y Ortogonalidad

El miércoles y jueves pasados estuve en Lyon, invitado por Barbara Petit del grupo PLUME de la École Normale Supérieure de Lyon. Allí di un seminario sobre los sistemas de tipos que he desarrollado: Scalar, Additive y Vectorial, y algunos de los problemas sobre cómo chequear ortogonalidad entre términos y algunas pistas para resolverlo.

Olivier Laurent se dio cuenta de simplemente ver la presentación, la conexión entre Additive y Intuitionistic Multiplicative Exponential Linear Logic.

Pronto estaré publicando un nuevo paper sobre Additive (con esa conexión a la lógica lineal) y Vectorial. Además, hemos empezado a trabajar juntos con Barbara en el problema de la ortogonalidad, usando subtyping.

Próximos viajes:
Los días 4 y 5 de Mayo voy a París a visitar a Benoît Valiron y Gilles Dowek del proyecto TypiCal, en la École Polytechnique de París, donde daré otro seminario. Luego, el 18 de Mayo estaré en Chambery, donde iremos con mi director, Pablo Arrighi, a participar de una serie de seminarios organizados por Lionel Vaux del grupo LAMA.

System F escalar: los slides

Subí a mi home page los slides que usé para la presentación del System F escalar. Aquí pueden bajar la versión para ver en pantalla (qpl09-talk.pdf) y aquí una versión print friendly (qpl09-talk-to-print.pdf).

La presentación era de 15 minutos, así que los slides están muy resumidos, lo que puede ser útil para un primer pantallazo sobre de qué se trata. Si les interesa, el paper completo está aquí: arXiv:0903.3741v1.

El workshop en general estuvo muy bueno. Filmaron todas las presentaciones, así que supongo que pronto estarán online (avisaré cuando estén y dónde).

System F escalar: hacia una lógica cuántica.

Primer paper desde que empecé con este proyecto de doctorado. Fue aceptado en el VI Workshop Quantum Physics and Logic que se va a llevar a cabo en Oxford el 8 y 9 de Abril próximos. Está disponible para descargar libremente aquí: arXiv:0903.3741.

Título:

Scalar System F for Linear-Algebraic λ-Calculus: Towards a Quantum Physical Logic

(System F escalar para el λ-Cálculo Algebraico Lineal: Hacia una Lógica Física Cuántica)

Y acá dejo el abstract en español:

El λ-cálculo algebraico lineal [1] extiende el λ-cálculo con la posibilidad de crear combinaciones lineales arbitrarias de términos α.t+β.u. Dado que se pueden expresar operadores de punto fijo sobre sumas en este cálculo, surge la noción de infinito, y por lo tanto, la noción de formas indefinidas. Como consecuencia, a fin de garantizar confluencia, t-t no siempre reduce a 0, sólo si t es cerrado y en forma normal. En este paper proveemos un sistema de tipos estilo System F para el λ-cálculo algebraico lineal, el cual garantiza normalización y por lo tanto no hay necesidad de esas restricciones: t-t siempre reduce a 0. Además este sistema de tipos lleva la cuenta de "la cantidad de un tipo". Por lo tanto puede verse como un sistema de tipos probabilístico, garantizando que los términos definen funciones probabilísticas correctas. Por último, se puede ver este sistema de tipos como un paso en la búsqueda de una lógica física cuántica a través del isomorfismo de Curry-Howard [2].

Bueno, tal como se expresa en el abstract, lo que hicimos fue darle tipos al λ-cálculo algebraico lineal. Usamos System F, o sea un sistema de tipos polimórfico, expresado à la Curry. Los tres resultados que se podrían destacar son:

• Con System F tenemos strong normalization, o sea, todo término que tiene un tipo normaliza, siguiendo cualquier vía de reducción. Por lo tanto, no tenemos más el problema de los infinitos del λ-cálculo algebraico lineal.
• El sistema de tipos hace que cualquier función probabilística expresada en el lenguaje, esté bien definida, o sea, que, por ejemplo, en una función que devuelve una cosa u otra dependiendo de su argumento, ambos branches suman lo mismo.
• La idea de darle tipos a este cálculo, no es por el lenguaje en sí, sino para extraer una lógica utilizando el isomorfismo de Curry-Howard, lo cual, a diferencia de la lógica cuántica definida en 1936 por Barkhoff y von Neumann [3] (la cual no se sabe cómo relacionar con la computación cuántica), esta lógica no está definida ad hoc sino extraída de un sistema de tipos de un cálculo que permite expresar la computación cuántica. Por supuesto, este es el primer paso, aún falta trabajo por hacer hasta tener un sistema de tipos que sólo admita programas representables por la computadora cuántica (i.e. que sus términos estén normalizados y que sus compuertas sean unitarias), pero aquí, con este primer sistema de tipos, hacemos un intento de interpretación de la lógica: como ya dije, esta lógica no está inventada ad hoc, sino extraída automáticamente del sistema de tipos, entonces ¿qué significa esta lógica? ¿qué interpretación le podemos dar? A modo de discusión dejamos algunas ideas en la última sección del paper.

Referencias:

[1] Pablo Arrighi y Gilles Dowek. Linear-algebraic λ-calculus: higher-order, encodings and confluence. Lecture Notes in Computer Science (RTA'08), 5117:17-31, 2008. (arXiv:quant-ph/0612199).

[2] Morten H. Sørensen y Pawel Urzyczyn.Lectures on the Curry-Howard Isomorphism, Volume 149 (Studies in Logic and the Foundations of Mathematics). Elsevier Science Inc., New York, NY, USA, 2006. (PDF).

[3] George D. Birkhoff y John von Neumann. The logic of quantum mechanics. Annals of Mathematics, 37:823-843, 1936. (JSTOR).

Update 11/04/09: Slides disponibles
Update 31/07/09: Versión extendida disponible

Función de lista de secuentes en arboles de pruebas: ¿Alguien conoce algo así?

Buenas,

Este post es para preguntar si alguien conoce algo parecido a esto (dado que ya he buscado en varios lugares y preguntado y nadie me ha sabido responder que haya algo así... pero debería haberlo ¿no?)

La idea es, dado un sistema de tipos deterministico, i.e. si me das un secuente y una regla de tipado, te doy la conclusión determinísticamente (Para ponerlo más claro, piensen en un sistema de tipos de segundo orden, donde hay un y la regla me dice que lo puedo eliminar reemplazando la por algo, bueno, eso no sería determinístico ya que a la la puedo reemplazar por diferentes cosas, algo determinístico en cambio sería si la regla fuese una familia de reglas (una por cada posible)), bueno, entonces, dado un sistema de tipos determinístico, lo que quiero es algo parecido a una función que tome una lista de sequentes y devuelva un árbol de prueba completo. O sea, es como si la función tuviera un árbol de pruebas vacío, donde sólo están las reglas a aplicar y los sequentes que hay en los axiomas, y cuando toma la lista de secuentes, los acomoda en los espacios vacíos de las hojas del árbol (o sea, los toma como hipótesis).

¿Se entiende la idea? Definirlo formalmente no es muy difícil, de hecho ya lo tengo hecho, pero quería saber si alguien conocía que ya exista algo así (como para no redefinir lo que ya existe).

Ya he preguntado a varias personas y nadie me supo decir que haya algo así, pero bueno, si a alguien esta "función" le suena parecido a algo que conozcan, avisen.

Tercera Escuela Mexicana de Verano en Computación e Información Cuánticas

Retransmito la información que me llegó sobre la Escuela Mexicana de Verano de Computación Cuántica:

 
Tercera Escuela Mexicana de Verano en Computación e Información Cuánticas
http://www.cem.itesm.mx/dia/mexqc09/
1 al 19 de junio de 2009
 
El grupo de procesamiento cuántico de la información del Tecnológico de Monterrey Campus Estado de México y el grupo Aspuru-Guzik de la Universidad de Harvard tienen el placer de convocar a la comunidad científica a participar en la
 
Tercera Escuela Mexicana de Verano en Computación e Información Cuánticas
 
del 1 al 19 de junio de 2009 en las instalaciones del Tecnológico de Monterrey Campus Estado de México. 

Actividades
- Primera semana (1-6 de junio). Curso de introducción (36 horas) a la computación e información cuánticas.
- Segunda semana (8-12 junio). Conferencias de once investigadores de talla mundial, demostración experimental de un sistema comercial de criptografía cuántica y pláticas técnicas por parte de la empresa SmartQuantum, y talleres de ejercicios en: algoritmos cuánticos, información cuántica, criptografía cuántica y un paquete de simulación de algoritmos cuánticos. Además, habrá carteles y charlas cortas por parte de los becarios de la escuela.
- Tercera semana (15-19 junio). Curso de introducción (30 horas) a los sistemas cuánticos abiertos.

Conferencistas
Dr. Daniel Browne, One-way Quantum Computation, Univ. College London. 
Dr. Bob Coecke, Category Theory in Quantum Computation, Oxford University. 
Prof. Ivan Deutsch, Quantum Control, University of New Mexico.
Prof. Edward Farhi, (Keynote speaker), Adiabatic Quantum Computing, MIT. 
Dr. Marco Lanzagorta, Quantum Cryptography, ITT Corporation, US Naval Research Lab. Contractor. 
Prof. Peter Love, Quantum Entanglement Quantification. Haverford College. 
Dr. Keye Martin, Domain Theory in Quantum Computation. US Naval Research Laboratory. 
Prof. Cristopher Moore, Scattering Algorithms. University of New Mexico and Santa Fe Institute.
Drs. Nicolas Pelloquin y François Guignot, A commercial quantum cryptography system, SmartQuantum.
Dr. Donald Sofge, Quantum Programming Languages, US Navy Center for Applied Research in Artificial Intelligence.
Dr. Rolando Somma, Quantum Simulated Annealing, Perimeter Institute.
Dr. Marko Znidaric, Entanglement Properties of Random Quantum States, University of Ljubljana.

Becas
Deseamos apoyar a estudiantes con alto desempeño académico y potencial para la investigación científica. En consecuencia, hemos diseñado un programa de becas completas y medias becas. Fecha límite para solicitud de becas: 1 de abril de 2009. Visite la página del evento para conocer los requisitos y documentos solicitados.

Perfil de asistentes 
- Estudiantes de licenciatura (últimos dos años), maestría o doctorado en ingeniería, matemáticas, física o computación.
- Profesores-investigadores interesados en el cómputo cuántico.
- La lengua oficial de la escuela de verano es el inglés.

Más información sobre programa, becas, inscripciones y alojamiento, en nuestra página: http://www.cem.itesm.mx/dia/mexqc09/

Agradecemos el apoyo de las siguientes instituciones: COMECyT, CLAF, CINVESTAV, Universidad de Cambridge, AMC, SMF y UNAM.

Blog Boliviano sobre Computación Cuántica

Buenas,
Les comento que hace unos seis meses ha surgido un nuevo weblog en Español sobre Computación Cuántica, mantenido por Hernán Payrumani: http://computacioncuantica.wordpress.com/
Tiene algunos posts en Inglés y otros en Español, y trata diversos temas dentro de la Computación Cuántica. Y algo importante: lo actualiza mucho más seguido que yo :) (pero prometo pronto enviar algo nuevo!).
Saludos y mucha suerte a Hernán con su blog!