ROLANDO SOMMA - Métodos Cuánticos para Optimización

Rolando Somma.

Los Alamos National Laboratory

Martes 7/8/2018, 10 hs.

Aula Seminario, 2do piso, Pab. I.

La optimización combinatoria discreta consiste en encontrar la configuración óptima que minimiza cierta función objetivo discreta. Métodos eficientes para optimización son entonces muy importantes en varias ramas de ciencia y tecnología. Por varios años, se ha conjeturado que las computadoras cuánticas podrían resolver problemas de optimización que son imposibles de resolver con computadoras clásicas. Sin embargo, no existen resultados rigurosos que prueben que esto sea cierto en casos genéricos. En este seminario presentaré algunos resultados que indicarían que las computadoras cuánticas podrían ser, de hecho, importantes para optimización. Motivado por el método de quantum annealing (temple cuántico), presentaré tres estrategias para resolver problemas de optimización con computadoras cuánticas y demostraré, en forma rigurosa, que la complejidad cuántica es razonablemente menor para ciertas instancias de estos problemas. La primer estrategia utiliza un mapeo de sistemas clásicos a sistemas cuánticos. Con este mapeo, un método clásico de optimización como simulated annealing (enfriamiento simulado) se puede transformar a un método cuántico de optimización como quantum annealing. La segunda estrategia utiliza el mismo mapeo y también emplea una técnica de amplificación de brechas de energía para reducir la complejidad de preparar el estado cuántico que resuelve el problema de optimización. Esta estrategia resulta en una mejoría cuadrática sobre la complejidad atribuída al método clásico de simulated annealing. La tercer estrategia utiliza procesos cuánticos diabáticos y resulta en una mejoría exponencial sobre la complejidad de métodos clásicos para ciertos problemas.