Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
Authors: Adam Bouland, Yosheb M Getachew, Yujia Jin, Aaron Sidford, Kevin Tian
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a quantum algorithm for computing an ϵ-approximate Nash equilibrium of a zero-sum game in an m n payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time e O( m + n ϵ 2.5 +ϵ 3) and outputs a classical representation of the ϵ-approximate Nash equilibrium. This improves upon the best prior quantum runtime of e O( m + n ϵ 3) obtained by (van Apeldoorn & Gilyén, 2019) and the classical e O((m + n) ϵ 2) runtime due to (Grigoriadis & Khachiyan, 1995) whenever ϵ = Ω((m + n) 1). We obtain this result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution. |
| Researcher Affiliation | Collaboration | 1Stanford University, Stanford, CA, USA. 2Microsoft Research, Redmond, WA, USA. |
| Pseudocode | Yes | Algorithm 1: Matrix Game Solver(δ, η, T) |
| Open Source Code | No | The paper does not contain any statement or link indicating that the code for the described methodology is open-source or publicly available. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and proofs; it does not describe empirical evaluation on datasets or mention the use of publicly available datasets for training or evaluation. |
| Dataset Splits | No | As a theoretical paper focused on algorithm design and complexity, it does not discuss training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and complexity analysis, not on practical implementation details or experimental results. Therefore, it does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe an implementation or empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments. Therefore, no experimental setup details, such as hyperparameters or training settings, are provided. |