  We propose the first online quantum algorithm for zero-sum games with $\tilde
O(1)$ regret under the game setting. Moreover, our quantum algorithm computes
an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix
zero-sum game in quantum time $\tilde O(\sqrt{m+n}/\varepsilon^{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. As an application,
we obtain a fast quantum linear programming solver. 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.
