Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
For researchers in quantum computing and optimization, this resolves a long-standing open problem by showing that semidefinite geometry does not preclude linear convergence rates in quantum zero-sum games.
The paper proves that quantum zero-sum games admit algorithms with O(log(1/ε)) last-iterate convergence to Nash equilibrium, breaking the previous O(1/ε) barrier. This is achieved via matrix variants of Nesterov's smoothing and Optimistic Gradient Descent-Ascent, matching classical polyhedral rates.
Quantum zero-sum games provide a framework for non-local games, quantum interactive proofs, and quantum machine learning, where players optimize a bilinear payoff over quantum states. In contrast to classical bilinear games over polyhedral domains, for which gradient methods achieve linear last-iterate convergence, comparable guarantees over spectraplexes have remained open. Recent work achieved only an $O(1/\varepsilon)$ average-iterate rate and suggested that semidefinite geometry may preclude classical-style linear rates. We refute this obstruction. We prove that quantum zero-sum games admit algorithms with $O(\log(1/\varepsilon))$ last-iterate convergence to Nash equilibrium. In particular, matrix variants of Nesterov's iterative smoothing and Optimistic Gradient Descent--Ascent match the asymptotic rate of the classical polyhedral case. The key technical ingredient is a new error-bound theory for semidefinite games, establishing metric subregularity of the relevant monotone operator over spectrahedra despite the absence of polyhedral structure. We also give a geometric characterization of Nash equilibria via slack operators, classifying strategic directions as essential, neutral, or non-essential. Under strict complementarity or nondegeneracy, this reduces to a sharp classical-style dichotomy. Finally, we revisit Optimistic Matrix Multiplicative Weights Update. By extending the Quantal Response Equilibrium framework to spectraplex games, we prove an $\widetilde O(1/\varepsilon)$ last-iterate guarantee, while showing that any $O(\log(1/\varepsilon))$ speedup for this method must depend on a natural, dimension-dependent condition number. Experiments support the theoretical picture, with Optimistic Gradient Descent--Ascent outperforming Optimistic Matrix Multiplicative Weights Update in the regimes studied.