[Todos] Charla Martes 7, 14hs- Algoritmos Cuánticos Adiabáticos para Problemas de Optimización

[Augusto Roncaglia]

Hola,

Mañana Martes 7 a las 14hs en el aula Federman, Rolando Somma
del Perimeter Institute de Canada dará una charla sobre 
algoritmos cuánticos.

Están todos cordialmente invitados.

Saludos,
Augusto.

"Algoritmos Cuánticos Adiabáticos para Problemas de Optimización"
                          Rolando Somma
  Perimeter Institute for Theoretical Physics, Waterloo, Canada


Las computadoras cuánticas pueden resolver ciertos problemas, incluyendo
factorización, en forma más eficiente que las computadoras
convencionales. Comunmente, los algoritmos cuánticos se describen en el
modelo estándard, en el que una secuencia de operaciones básicas se
aplican a cierto estado inicial, y una medición se realiza al estado
evolucionado. La complejidad del algoritmo está determinada por la
cantidad de operaciones necesarias para preparar el estado deseado.
Otros modelos de computación cuántica existen en la literatura. En
particular, la computación cuántica adiabática (ACA) ha sido propuesta
recientemente como una alternativa al modelo de computación estándard.
En ACA, la computación se realiza a través de cambios lentos en las
interacciones entre los componentes de la computadora cuántica. La idea
es que, luego de la evolución, el estado cuántico que ha sido preparado
contiene información sobre la solución al problema a resolver. La
complejidad de un algoritmo cuántico está dada por el tiempo de
evolución y depende de las propiedades del Hamiltoniano que describe las
interacciones. Sin embargo, calcular la complejidad de estos algoritmos
en forma rigurosa es una tarea difícil y, comunmente, la complejidad
obtenida está fuertemente sobreestimada. Esta sobreestimación es
claramente no deseada si uno quiere comparar el rendimiento de una
computadora cuántica con el de una computadora convencional.
En esta charla voy a describir diferentes modelos adiabáticos que
incluyen randomización en el tiempo de evolución. El modelo que voy a
presentar puede considerarse como una variante del efecto Zeno cuántico,
en el que el estado deseado es preparado a través de mediciones en las
direcciones correspondientes. Voy a mostrar que la complejidad
algorítmica en estos modelos puede ser obtenida exactamente y, en
particular, voy a presentar un algoritmo cuántico que nos permite
resolver problemas de optimización en forma mucho más eficiente que las
computadoras convencionales.