We derive sublinear-time quantum algorithms for computing the Nash
equilibrium of two-player zero-sum games, based on efficient Gibbs sampling
methods. We are able to achieve speed-ups for both dense and sparse payoff
matrices at the cost of a mildly increased dependence on the additive error
compared to classical algorithms. In particular we can find
$\varepsilon$-approximate Nash equilibrium strategies in complexity
$\tilde{O}(\sqrt{n+m}/\varepsilon^3)$ and
$\tilde{O}(\sqrt{s}/\varepsilon^{3.5})$ respectively, where $n\times m$ is the
size of the matrix describing the game and $s$ is its sparsity. Our algorithms
use the LP formulation of the problem and apply techniques developed in recent
works on quantum SDP-solvers. We also show how to reduce general LP-solving to
zero-sum games, resulting in quantum LP-solvers that have complexities
$\tilde{O}(\sqrt{n+m}\gamma^3)$ and $\tilde{O}(\sqrt{s}\gamma^{3.5})$ for the
dense and sparse access models respectively, where $\gamma$ is the relevant
"scale-invariant" precision parameter

提出量子计算的次线性时间的算法，基于 LP 问题和量子 SDP 求解器，用有效的 Gibbs 采样方法计算二人零和游戏的 Nash 均衡点。