Attested & literatureAlgorithmsMarkov-chain sampling2026-08-12

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.

Optimization

zero-sum gamenash equilibriumgibbs samplingpayoff matrixquantum data structures

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

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.

Circuit & simulation

problem

encodetransform

algorithm

transformmeasure

readout

measure

What this takes and returns

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 →

How it works

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..

Implementation

FrameworkUnsupported

zero-sum-game-equilibria.txt

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.

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.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling2023 · Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, Kevin Tian

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.

arxiv.org/abs/2301.03763 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Approximating Nash Equilibria" (Optimization, Numerics, and Machine Learning); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (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."). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: nothing was constructed, compiled, simulated, run or benchmarked, and no game was solved here. The runtime is asymptotic and its Õ suppresses factors neither source names, so no gate count, qubit count, constant factor, error-correction budget or wall-clock time follows from it. The abstract attaches the condition ε = Ω((m+n)^(-1)) to its improvement claim, so outside that range of ε neither comparison it makes is asserted, and the gain in dimension, √(m+n) against m+n, is bought with a worse dependence on the accuracy, ε^(-2.5) plus an additive ε^(-3) against ε^(-2); this record does not establish where the crossover falls for any concrete m, n and ε. The result assumes a standard quantum oracle for the payoff matrix and bounded entries, and the cost of providing that oracle, together with what the new quantum data structures cost to build and maintain, is outside this record. Neither source defines what ε-approximate means for the equilibrium, and the statement is for zero-sum games only, so nothing here bears on general-sum games. The classical figure is attributed by the abstract to [GK95] as the runtime being improved on rather than as a proved lower bound, and the prior quantum runtime is attributed to [vAG19]. The Zoo cites by number only, and its numbers do not line up with those two: [ 485 ] is the algorithm this record covers and [ 486 ] the prior result it improves on. The Zoo states no runtime for [ 486 ] and attaches no reference number to the classical figure at all. This record reads none of those references and does not establish which papers the Zoo's numbers denote.

Facts

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.
Secondary source for the speedup class: Quantum Algorithm Zoo — "Approximating Nash Equilibria"
Section it is filed under: Optimization, Numerics, and Machine Learning
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

Source

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply