Research map / Learning theory and algorithms / Submodular and game algorithms
Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Quantizes multi-scale MWU and a dynamic-Gibbs-sampling CCE algorithm to compute ε-correlated and coarse correlated equilibria of m-player normal-form games with Õ(m√n) and Õ(m√n/ε^2.5) quantum queries, plus a matching Ω(m√n) query lower bound.
Problem
Computing ε-approximate correlated equilibria (CE) and coarse correlated equilibria (CCE) of multi-player general-sum normal-form games, given only quantum oracle access to the loss function, with query complexity that is near-optimal in the number of players m and actions n.
Approach
Store all historical sampled action profiles in a single QRAM and build amplitude encodings of MWU loss vectors from it, so quantum Gibbs sampling replaces classical exponentiation of n-dimensional loss vectors; for CCE, extend the two-player quantum zero-sum dynamic-Gibbs framework to m players using QRAM in place of sampler trees. A lower bound comes from reducing m copies of unstructured search
Key results
- Quantum CE algorithm uses m√n(log(mn))^{O(1/ε)} queries, versus Ω(mn) for classical multi-scale MWU.
- Quantum CCE algorithm uses Õ(m√n/ε^{2.5}) queries, improving the classical Õ(mn/ε^2) dependence on n.
- Quantum query lower bound Ω(m√n) for both ε-CE and ε-CCE, matching the upper bounds in m and n up to polylog factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum-ce instead of the classical LP-based algorithm | Computing ε-CE in an m-player, n-action normal-form game · ε-CE | query complexity | Helped |
| Use quantum-cce instead of the classical MWU-based algorithm | Computing ε-CCE in an m-player, n-action normal-form game · ε-CCE | query complexity | Helped |
| Use quantum-ce instead of the classical LP-based algorithm | Computing ε-CE in an m-player, n-action normal-form game · ε-CE | time complexity | Mixed |
| Use quantum-cce instead of the classical MWU-based algorithm | Computing ε-CCE in an m-player, n-action normal-form game · ε-CCE | time complexity | Mixed |
Limitations
- Time complexity exceeds query complexity by a factor of O(m) due to per-player QRAM access, leaving Õ(m√n) time open.
- The CCE ε-dependence (ε^-2.5) is not improved; quantizing optimistic MWU appears difficult due to sensitivity to sampling noise.
- Results are theoretical; the CE algorithm's ε-dependence is (log(mn))^{O(1/ε)}, which is exponential in 1/ε.
Experimental setup
Metrics: query complexity time complexity
Baselines: classical multi-scale MWU (Ω(mn) queries) classical sampling-based MWU for CCE (Õ(mn/ε^2)) quantum zero-sum game algorithms
Builds on: multi-scale MWU quantum Gibbs sampler dynamic Gibbs sampling for zero-sum games Grigoriadis-Khachiyan algorithm
Closest papers by meaning
- Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling (ICML 2023 · similarity 0.91)
- Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games (NeurIPS 2023 · similarity 0.90)
- Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games (NeurIPS 2024 · similarity 0.88)
- The Complexity of Correlated Equilibria in Generalized Games (NeurIPS 2025 · similarity 0.87)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.86)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.