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.

我们提出了首个在线量子算法，用于零和游戏，可以在 $\tilde O (1)$ 的时间内计算 $m \times n$ 矩阵零和游戏的 $\varepsilon$- 近似纳什均衡，与 $m$，$n$ 的经典算法相比，取得了二次的改进，同时实现了一个快速的量子线性规划求解器。