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!