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.
