Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes

• URL: http://arxiv.org/abs/2509.21570v1
• Date: Thu, 25 Sep 2025 20:51:13 GMT
• Title: Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
• Authors: Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong,
• Abstract summary: We prove that matrix variants of $textitNesterov's iterative smoothing$ achieve last-iterate convergence at a linear rate in quantum zero-sum games.<n>As a byproduct, we obtain an exponential speed-up over the classical Jain-Watrous [arXiv:0808.2775] method for parallel approximation of strictly positive semidefinite programs.
• Score: 2.7340036787711646
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Long studied as a toy model, quantum zero-sum games have recently resurfaced as a canonical playground for modern areas such as non-local games, quantum interactive proofs, and quantum machine learning. In this simple yet fundamental setting, two competing quantum players send iteratively mixed quantum states to a referee, who performs a joint measurement to determine their payoffs. In 2025, Vasconcelos et al. [arXiv:2311.10859] connected quantum communication channels with a hierarchy of quantum optimization algorithms that generalize Matrix Multiplicative Weights Update ($\texttt{MMWU}$) through extra-gradient mechanisms, establishing an average-iterate convergence rate of $\mathcal{O}(1/\epsilon)$ iterations to $\epsilon$-Nash equilibria. While a long line of work has shown that bilinear games over polyhedral domains admit gradient methods with linear last-iterate convergence rates of $\mathcal{O}(\log(1/\epsilon))$, it has been conjectured that a fundamental performance gap must persist between quantum feasible sets (spectraplexes) and classical polyhedral sets (simplices). We resolve this conjecture in the negative. We prove that matrix variants of $\textit{Nesterov's iterative smoothing}$ ($\texttt{IterSmooth}$) and $\textit{Optimistic Gradient Descent-Ascent}$ ($\texttt{OGDA}$) achieve last-iterate convergence at a linear rate in quantum zero-sum games, thereby matching the classical polyhedral case. Our analysis relies on a new generalization of error bounds in semidefinite programming geometry, establishing that (SP-MS) holds for monotone operators over spectrahedra, despite their uncountably many extreme points. Finally, as a byproduct, we obtain an exponential speed-up over the classical Jain-Watrous [arXiv:0808.2775] method for parallel approximation of strictly positive semidefinite programs.

Related papers

• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• From Classical to Quantum: Explicit Classical Distributions Achieving Maximal Quantum $f$-Divergence [4.956709222278243]
  Explicit classical states achieving maximal $f$-divergence are given, allowing for a simple proof of Matsumoto's Theorem.<n>Our methodology is particularly simple as it does not require any elaborate matrix analysis machinery but only basic linear algebra.
  arXiv  Detail & Related papers  (2025-01-24T09:06:13Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret$+$ (RM$+$)<n>Our analysis builds on a new characterization of the geometric structure of the limit points of our algorithms, marking a significant departure from most of the literature on last-iterate convergence.
  arXiv  Detail & Related papers  (2023-11-01T17:34:58Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  Despite progress in classical lower bounds for non optimization, these bounds are still widely open. Omegabig(frac-1+ppp)$ regarding the first setting. Omegano()$ regarding the second setting. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth.
  arXiv  Detail & Related papers  (2022-12-07T19:02:36Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.