28 de agosto de 2009

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.

21 de agosto de 2009

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):

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.

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

20 de agosto de 2009

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)
Reviews de NMR QIP:
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).

19 de agosto de 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):

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.

18 de agosto de 2009

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!

17 de agosto de 2009

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