Fetching the paper…

Reading the bibliography…

2019

Quantum algorithms for zero-sum games

van Apeldoorn, Joran, Gilyén, András

Original
PDF
Post on X

Understand

We derive sublinear-time quantum algorithms for computing the Nash equilibrium of two-player zero-sum games, based on efficient Gibbs sampling methods.

We are able to achieve speed-ups for both dense and sparse payoff matrices at the cost of a mildly increased dependence on the additive error compared to classical algorithms.
In particular we can find $\varepsilon$-approximate Nash equilibrium strategies in complexity $\tilde{O}(\sqrt{n+m}/\varepsilon^3)$ and $\tilde{O}(\sqrt{s}/\varepsilon^{3.5})$ respectively, where $n\times m$ is the size of the matrix describing the game and $s$ is its sparsity.
Our algorithms use the LP formulation of the problem and apply techniques developed in recent works on quantum SDP-solvers.

Quantum algorithms for zero-sum games · Around

Built on

A sublinear-time randomized approximation algorithm for matrix games
Michael D. Grigoriadis and Leonid G. Khachiyan · 1995
Earlier work this paper cites.
A quantum algorithm for finding the minimum
Christoph Dürr and Peter Høyer · 1996
Earlier work this paper cites.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp · 2002
Earlier work this paper cites.
Creating superpositions that correspond to efficiently integrable probability distributions
Lov Grover and Terry Rudolph · 2002
Earlier work this paper cites.
Black-box Hamiltonian simulation and unitary implementation
Original
Dominic W. Berry and Andrew M. Childs · 2012
Earlier work this paper cites.

Similar

Quantum SDP-solvers: Better upper and lower bounds
Original
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf · 2017
Cited alongside, same era.
Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning
Original
Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu · 2017
Cited alongside, same era.
Quantum speed-ups for solving semidefinite programs
Original
Fernando G. S. L. Brandão and Krysta M. Svore · 2017
Cited alongside, same era.
Quantum recommendation systems
Original
Iordanis Kerenidis and Anupam Prakash · 2017
Cited alongside, same era.
Hamiltonian simulation by uniform spectral amplification
Original
Guang Hao Low and Isaac L. Chuang · 2017
Cited alongside, same era.

Then

Improvements in quantum SDP-solving with applications
Original
Joran van Apeldoorn and András Gilyén · 2018
Later among the works it cites.
Product decomposition of periodic functions in quantum signal processing
Original
Jeongwan Haah · 2018
Later among the works it cites.
A rank-1 sketch for matrix multiplicative weights
Original
Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian · 2019
Closest in time.
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
Original
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…