Limits found for algorithms finding quantum zero sum game equilibria
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Computer Science and Game TheoryMachine Learning
Summary
Finding stable strategies called Nash equilibria in quantum zero-sum games helps understand strategic situations in quantum settings. The authors showed that a popular algorithm for this task cannot improve beyond certain speed limits based on how accurate the solution is. They also demonstrated examples where the algorithm's final outputs get closer to the solution slowly, not rapidly, contradicting hopes for fast convergence. This means certain optimistic algorithm variants may inherently require much time to find precise equilibria in quantum games.
What this means in practice
- •For quantum algorithm developers: Assess algorithm speed limits when computing quantum game Nash equilibria to better design or choose methods.
- •For applied mathematicians: Understand convergence behaviors in quantum optimization algorithms for improved mathematical modeling in quantum contexts.
A theory result. No direct application yet.
Authors
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
Abstract
Optimistic matrix mirror-prox (OMMP) computes $ε$-approximate Nash equilibria in quantum zero-sum games with an $O(1/\varepsilon)$ average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an $Ω(1/\varepsilon)$ lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium $Θ(1/t)$ and duality gap $Θ(1/t^3)$ for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as $Θ(1/t)$, while the duality gap decays as $Θ(1/t^2)$.