Quantum-over-classical Advantage in Solving Multiplayer Games
- URL: http://arxiv.org/abs/2006.06965v1
- Date: Fri, 12 Jun 2020 06:36:07 GMT
- Title: Quantum-over-classical Advantage in Solving Multiplayer Games
- Authors: Dmitry Kravchenko, Kamil Khadiev, Danil Serov and Ruslan Kapralov
- Abstract summary: Subtraction games are sometimes referred to as one-heap Nim games.
In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games.
For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the applicability of quantum algorithms in computational game theory
and generalize some results related to Subtraction games, which are sometimes
referred to as one-heap Nim games.
In quantum game theory, a subset of Subtraction games became the first
explicitly defined class of zero-sum combinatorial games with provable
separation between quantum and classical complexity of solving them. For a
narrower subset of Subtraction games, an exact quantum sublinear algorithm is
known that surpasses all deterministic algorithms for finding solutions with
probability $1$.
Typically, both Nim and Subtraction games are defined for only two players.
We extend some known results to games for three or more players, while
maintaining the same classical and quantum complexities:
$\Theta\left(n^2\right)$ and $\tilde{O}\left(n^{1.5}\right)$ respectively.
Related papers
- Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before.
In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
arXiv Detail & Related papers (2024-06-23T00:27:28Z) - Repeated quantum game as a stochastic game: Effects of the shadow of the
future and entanglement [0.0]
We present a systematic investigation of the quantum games, constructed using a novel repeated game protocol.
We find that how two pure strategies fare against each other is crucially dependent on the discount factor.
In the quantum game setup, always-defect strategy can be beaten by the tit-for-tat strategy for high enough discount factor.
arXiv Detail & Related papers (2023-12-08T15:54:51Z) - 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) - Photonic implementation of the quantum Morra game [69.65384453064829]
We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case.
We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game.
We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
arXiv Detail & Related papers (2023-11-14T19:41:50Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [7.962205145083434]
We propose the first online quantum algorithm for zero-sum games with $tilde O(1)$ regret under the game setting.
Our quantum algorithm computes an $varepsilon$-approximate Nash equilibrium of an $m times n$ matrix zero-sum game in quantum time.
arXiv Detail & Related papers (2023-04-27T14:02:54Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
We develop the concepts of Mean-Field correlated and coarse-correlated equilibria.
We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
arXiv Detail & Related papers (2022-08-22T08:31:46Z) - Winning Mastermind Overwhelmingly on Quantum Computers [0.2320417845168326]
We have a systematic study on quantum strategies for playing Mastermind.
We construct optimal quantum algorithms in both non-adaptive and adaptive settings.
We develop a framework for designing quantum algorithms for the general string learning problem.
arXiv Detail & Related papers (2022-07-19T16:02:28Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games.
This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
arXiv Detail & Related papers (2022-02-03T18:18:28Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
arXiv Detail & Related papers (2021-12-09T21:06:52Z) - Infinitely Repeated Quantum Games and Strategic Efficiency [0.0]
Repeated quantum game theory addresses long term relations among players who choose quantum strategies.
In the conventional quantum game theory, single round quantum games or at most finitely repeated games have been widely studied.
arXiv Detail & Related papers (2020-05-12T07:39:42Z)
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.