Breaking $1\mathrm{/}\epsilon$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes

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\mathrm{/}\epsilon )$ 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\mathrm{/}\epsilon ))$ 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 $\tilde{O}(1\mathrm{/}\epsilon )$ last-iterate guarantee, while showing that any $O(\log (1\mathrm{/}\epsilon ))$ 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.