Algorithms · Markov-chain sampling
Approximate Nash equilibria of zero-sum games by dynamic Gibbs sampling
Given oracle access to the m × n payoff matrix of a zero-sum game with bounded entries, compute a classical representation of an ε-approximate Nash equilibrium of that game.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costÕ(√(m+n)·ε^(-2.5) + ε^(-3)) time, given a standard quantum oracle for accessing the payoff matrix, to output a classical representation of an ε-approximate Nash equilibrium; the abstract sets this against the best prior quantum runtime Õ(√(m+n)·ε^(-3)) and the classic Õ((m+n)·ε^(-2)), and states the improvement whenever ε = Ω((m+n)^(-1)). The Zoo quotes the same quantum runtime and the same classical Õ((m+n)·ε^(-2)), and states no runtime for the prior result it says this algorithm improves on.
- Papers1
Given oracle access to the m × n payoff matrix of a zero-sum game with bounded entries, compute a classical representation of an ε-approximate Nash equilibrium of that game. The Zoo states the route in one clause: the runtime is reached by making a connection between Nash equilibria and Gibbs sampling. Bouland, Getachew, Jin, Sidford and Tian write that they obtain their result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution, which the paper's title calls improved dynamic Gibbs sampling. The input model is a standard quantum oracle for accessing the payoff matrix, whose entries are assumed bounded, and the stated output is a classical representation of the ε-approximate Nash equilibrium. The paper sets that runtime against the best prior quantum runtime and against the classical runtime it cites, and names the range of ε over which its improvement is claimed.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
The Zoo states the route in one clause: the runtime is reached by making a connection between Nash equilibria and Gibbs sampling. Bouland, Getachew, Jin, Sidford and Tian write that they obtain their result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution, which the paper's title calls improved dynamic Gibbs sampling. The input model is a standard quantum oracle for accessing the payoff matrix, whose entries are assumed bounded, and the stated output is a classical representation of the ε-approximate Nash equilibrium. The paper sets that runtime against the best prior quantum runtime and against the classical runtime it cites, and names the range of ε over which its improvement is claimed. This record's speedup class, "Polynomial", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: Õ(√(m+n)·ε^(-2.5) + ε^(-3)) time, given a standard quantum oracle for accessing the payoff matrix, to output a classical representation of an ε-approximate Nash equilibrium; the abstract sets this against the best prior quantum runtime Õ(√(m+n)·ε^(-3)) and the classic Õ((m+n)·ε^(-2)), and states the improvement whenever ε = Ω((m+n)^(-1)). The Zoo quotes the same quantum runtime and the same classical Õ((m+n)·ε^(-2)), and states no runtime for the prior result it says this algorithm improves on..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- Õ(√(m+n)·ε^(-2.5) + ε^(-3)) time, given a standard quantum oracle for accessing the payoff matrix, to output a classical representation of an ε-approximate Nash equilibrium; the abstract sets this against the best prior quantum runtime Õ(√(m+n)·ε^(-3)) and the classic Õ((m+n)·ε^(-2)), and states the improvement whenever ε = Ω((m+n)^(-1)). The Zoo quotes the same quantum runtime and the same classical Õ((m+n)·ε^(-2)), and states no runtime for the prior result it says this algorithm improves on.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:2301.03763 (TeX rendered into Unicode: widetilde O written Õ, epsilon written ε, \cdot written ·, \sqrt{m+n} written √(m+n), math delimiters removed): "Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time Õ(√(m + n)·ε^{-2.5} + ε^{-3}) and outputs a classical representation of the ε-approximate Nash equilibrium", and "This improves upon the best prior quantum runtime of Õ(√(m + n)·ε^{-3}) obtained by [vAG19] and the classic Õ((m + n)·ε^{-2}) runtime due to [GK95] whenever ε = Ω((m +n)^{-1})." The Quantum Algorithm Zoo entry "Approximating Nash Equilibria" states the same contrast, rendered the same way and with its reference-number spacing left as written: "Classically, the best algorithm for this has runtime Õ((m+n) ε^{-2}). The quantum algorithm of [ 485 ], improving on the prior result of [ 486 ] achieves this in runtime Õ(√(m+n) ε^{-2.5} + ε^{-3}) by making a connection between Nash equilibria and Gibbs sampling."
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Markov-chain sampling with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Approximate Nash equilibria of zero-sum games by dynamic Gibbs sampling
PROBLEM: Given oracle access to the m × n payoff matrix of a zero-sum game with bounded entries, compute a classical representation of an ε-approximate Nash equilibrium of that game.
IDEA: The Zoo states the route in one clause: the runtime is reached by making a connection between Nash equilibria and Gibbs sampling. Bouland, Getachew, Jin, Sidford and Tian write that they obtain their result by designing new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution, which the paper's title calls improved dynamic Gibbs sampling. The input model is a standard quantum oracle for accessing the payoff matrix, whose entries are assumed bounded, and the stated output is a classical representation of the ε-approximate Nash equilibrium. The paper sets that runtime against the best prior quantum runtime and against the classical runtime it cites, and names the range of ε over which its improvement is claimed.
REPORTED COST: Õ(√(m+n)·ε^(-2.5) + ε^(-3)) time, given a standard quantum oracle for accessing the payoff matrix, to output a classical representation of an ε-approximate Nash equilibrium; the abstract sets this against the best prior quantum runtime Õ(√(m+n)·ε^(-3)) and the classic Õ((m+n)·ε^(-2)), and states the improvement whenever ε = Ω((m+n)^(-1)). The Zoo quotes the same quantum runtime and the same classical Õ((m+n)·ε^(-2)), and states no runtime for the prior result it says this algorithm improves on.
BASIS: abstract of arXiv:2301.03763 (TeX rendered into Unicode: widetilde O written Õ, epsilon written ε, \cdot written ·, \sqrt{m+n} written √(m+n), math delimiters removed): "Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time Õ(√(m + n)·ε^{-2.5} + ε^{-3}) and outputs a classical representation of the ε-approximate Nash equilibrium", and "This improves upon the best prior quantum runtime of Õ(√(m + n)·ε^{-3}) obtained by [vAG19] and the classic Õ((m + n)·ε^{-2}) runtime due to [GK95] whenever ε = Ω((m +n)^{-1})." The Quantum Algorithm Zoo entry "Approximating Nash Equilibria" states the same contrast, rendered the same way and with its reference-number spacing left as written: "Classically, the best algorithm for this has runtime Õ((m+n) ε^{-2}). The quantum algorithm of [ 485 ], improving on the prior result of [ 486 ] achieves this in runtime Õ(√(m+n) ε^{-2.5} + ε^{-3}) by making a connection between Nash equilibria and Gibbs sampling."
PRIMARY SOURCE: Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, Kevin Tian (2023), Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling — https://arxiv.org/abs/2301.03763
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Thermal Gibbs state sampling
Algorithms
- Quantum simulated annealing
Algorithms
- Optimization by decoded quantum interferometry
Algorithms
References
- Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, Kevin Tian · 2023
Primary source: it states the bounded-entry m × n payoff matrix, the standard quantum oracle input model, the Õ(√(m+n)·ε^(-2.5) + ε^(-3)) runtime, the classical representation of the output, and the comparison with Õ(√(m+n)·ε^(-3)) from [vAG19] and Õ((m+n)·ε^(-2)) from [GK95] under ε = Ω((m+n)^(-1)). It attributes the speedup to new quantum data structures for efficiently sampling from a slowly-changing Gibbs distribution. Consult it for the definition of the ε-approximation and for what those data structures cost per update, neither of which the abstract states.