报告题目：Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

报告时间：2024-11-08   15:00-16:00

报 告 人：Minbo Gao 博士（中国科学院软件研究所）

报告地点：理学院东北楼四楼报告厅（404）

Abstract: We propose the first online quantum algorithm for zero-sum games with O ̃(1)regret under the game setting. Moreover, our quantum algorithm computes an ε-approximate Nash equilibrium of an m×nmatrix zero-sum game in quantum time O ̃(√(m+n)/ε^2.5 ), yielding a quadratic improvement over classical algorithms in terms of m,n. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm ‘quantizes’ classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.