2023/01/10 by Bouland, Adam, Getachew, Yosheb, Jin, Yujia +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2301.03763
We give a quantum algorithm for computing an ε-approximate Nash equilibrium of a zero-sum game in a m × n payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time \widetildeO(√(m + n)⋅ ε-2.5 + ε-3) and outputs a classical representation of the ε-approximate Nash equilibrium. This improves upon the best prior quantum runtime of \widetildeO(√(m + n) ⋅ ε-3) obtained by [vAG19] and the classic \widetildeO((m + n) ⋅ ε-2) runtime due to [GK95] whenever ε= Ω((m +n)-1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution.