Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

arXiv:2609.38835 · quant-ph, cs.GT, cs.LG, math.OC · Submitted 2026-09-30 · Read on arXiv

quant-ph, cs.GT, cs.LG, math.OC

Submitted: 2026-09-30

Updated: 2026-09-30

Terminology

• Accuracy — 13× in this paper · explained in 1 episode
• Nash Equilibrium — 13× in this paper · explained in 2 episodes
• Trace — 5× in this paper · explained in 2 episodes
• Alignment — 2× in this paper · explained in 1 episode
• Angular Error — 1× in this paper · explained in 1 episode
• Approximation Bound — 1× in this paper · explained in 1 episode
• Elias — 1× in this paper · explained in 2 episodes
• Embeddings — 1× in this paper · explained in 2 episodes
• Generative AI — 1× in this paper · explained in 2 episodes

Sources

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
• Nash equilibria in semidefinite games and Lemke-Howson paths
• Parallel approximation of non-interactive zero-sum quantum games
• Learning in quantum games
• Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity