Speakers
Description
This work revisits the conjectured $1/\epsilon$ barrier for gradient-based methods in quantum zero-sum games and shows that the correct picture is geometric rather than universal. Our main technical contribution is a spectraplex analogue of Hoffman-type error bounds, formulated through the SP--MS condition, which converts small duality gap into Frobenius-distance control to the Nash set. This error-bound mechanism replaces the finite active-constraint structure of polytopes by tight spectral constraints and semidefinite normal-cone geometry. As a consequence, two classical Euclidean dynamics, Nesterov-style iterative smoothing and projected optimistic gradient dynamics, extend to the matrix setting and obtain geometric last-iterate convergence, yielding $\mathcal{O}(\log(1/\epsilon))$ iteration complexity up to game-dependent conditioning constants. These positive results show that the previously conjectured lower barrier does not apply to all gradient methods, but only to methods whose geometry cannot exploit this metric structure.
At the same time, our analysis identifies a genuine obstruction for entropic dynamics. Although explicit $\delta$-exploration or entropy regularization gives a positive route through the quantum quantal-response equilibrium, achieving an $\epsilon$-Nash approximation requires choosing $\delta\asymp\epsilon$, leading to a $\widetilde{\mathcal{O}}_d(1/\epsilon)$ dependence. Moreover, in the low-precision, dimension-sensitive regime, entropy is too weak to control nearly flat spectral directions of the spectraplex. Our lower bound for unregularized $\texttt{OMMWU}$ makes this conditioning barrier explicit through families requiring $\Omega(d^{\alpha}\log(1/\varepsilon))$ iterations. Together, the results delineate when fast last-iterate convergence is possible and when entropic methods are inherently conditioned, pointing toward a deeper study of quantum game dynamics and the geometric intricacies of spectraplexes across algorithms, regimes, and matrix geometries.
| Topic | Other |
|---|---|
| Additional Topic | Theoretical foundations of quantum learning |