Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
- URL: http://arxiv.org/abs/2301.03763v1
- Date: Tue, 10 Jan 2023 02:56:49 GMT
- Title: Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
- Authors: Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, Kevin Tian
- Abstract summary: We give a quantum algorithm for computing an $epsilon$-approximate Nash equilibrium of a zero-sum game in a $m times n$ payoff matrix with bounded entries.
Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time $widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$ and outputs a classical representation of the $epsilon$-approximate Nash equilibrium.
- Score: 30.53587208999909
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a quantum algorithm for computing an $\epsilon$-approximate Nash
equilibrium of a zero-sum game in a $m \times n$ payoff matrix with bounded
entries. Given a standard quantum oracle for accessing the payoff matrix our
algorithm runs in time $\widetilde{O}(\sqrt{m + n}\cdot \epsilon^{-2.5} +
\epsilon^{-3})$ and outputs a classical representation of the
$\epsilon$-approximate Nash equilibrium. This improves upon the best prior
quantum runtime of $\widetilde{O}(\sqrt{m + n} \cdot \epsilon^{-3})$ obtained
by [vAG19] and the classic $\widetilde{O}((m + n) \cdot \epsilon^{-2})$ runtime
due to [GK95] whenever $\epsilon = \Omega((m +n)^{-1})$. We obtain this result
by designing new quantum data structures for efficiently sampling from a
slowly-changing Gibbs distribution.
Related papers
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
Gradient descent is one of the most basic algorithms for solving continuous optimization problems.
We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$.
We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
arXiv Detail & Related papers (2024-07-04T11:03:48Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
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.
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) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions.
We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$.
We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
arXiv Detail & Related papers (2023-04-25T15:32:37Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
We show that quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
We also characterize the domains where quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
arXiv Detail & Related papers (2022-12-05T19:10:32Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
A quantum algorithm finds an $x*incal K$ such that $F(x*)-min_xincal K F(x)leqepsilon$ using $tildeO(n3)$ quantum evaluation queries to $F$.
As an application, we give a quantum function algorithm for zeroth-order convex bandits with $tildeO(n5log2 T)$ regret, an exponential speedup in $T$ compared to the classical $
arXiv Detail & Related papers (2022-09-26T03:19:40Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
We study the fixed-support Wasserstein barycenter problem (FS-WBP)
We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
arXiv Detail & Related papers (2020-02-12T03:40:52Z)
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.