Related papers: Quantum-over-classical Advantage in Solving Multiplayer Games

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

A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
arXiv Detail & Related papers (2024-08-13T08:11:56Z)
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 [10.79781442303645]
We propose the first online quantum algorithm for solving zero-sum games. Our algorithm generates classical outputs with succinct descriptions. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem.
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)
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.