Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the equivalence between non-factorizable mixed-strategy classical games and quantum games
256
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A game-theoretic setting provides a mathematical basis for analysis of strategic interaction among competing agents and provides insights into both classical and quantum decision theory and questions of strategic choice. An outstanding mathematical question, is to understand the conditions under which a classical game-theoretic setting can be transformed to a quantum game, and under which conditions there is an equivalence. In this paper, we consider quantum games as those that allow non-factorizable probabilities. We discuss two approaches for obtaining a non-factorizable game and study the outcome of such games. We demonstrate how the standard version of a quantum game can be analyzed as a non-factorizable game and determine the limitations of our approach.
rate research
Read More
A framework for discussing relationships between different types of games is proposed. Within the framework, quantum simultaneous games, finite quantum simultaneous games, quantum sequential games, and finite quantum sequential games are defined. In addition, a notion of equivalence between two games is defined. Finally, the following three theorems are shown: (1) For any quantum simultaneous game G, there exists a quantum sequential game equivalent to G. (2) For any finite quantum simultaneous game G, there exists a finite quantum sequential game equivalent to G. (3) For any finite quantum sequential game G, there exists a finite quantum simultaneous game equivalent to G.
We introduce a new class of non-local games, and corresponding densities, which we call bisynchronous. Bisynchronous games are a subclass of synchronous games and exhibit many interesting symmetries when the algebra of the game is considered. We develop a close connection between these non-local games and the theory of quantum groups which recently surfaced in studies of graph isomorphism games. When the number of inputs is equal to the number of outputs, we prove that a bisynchronous density arises from a trace on the quantum permutation group. Each bisynchronous density gives rise to a completely positive map and we prove that these maps are factorizable maps.
We consider two aspects of quantum game theory: the extent to which the quantum solution solves the original classical game, and to what extent the new solution can be obtained in a classical model.
We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix $Ainmathbb{R}^{ntimes d}$, sublinear algorithms for the matrix game $min_{xinmathcal{X}}max_{yinmathcal{Y}} y^{top} Ax$ were previously known only for two special cases: (1) $mathcal{Y}$ being the $ell_{1}$-norm unit ball, and (2) $mathcal{X}$ being either the $ell_{1}$- or the $ell_{2}$-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed $qin (1,2]$, we solve the matrix game where $mathcal{X}$ is a $ell_{q}$-norm unit ball within additive error $epsilon$ in time $tilde{O}((n+d)/{epsilon^{2}})$. We also provide a corresponding sublinear quantum algorithm that solves the same task in time $tilde{O}((sqrt{n}+sqrt{d})textrm{poly}(1/epsilon))$ with a quadratic improvement in both $n$ and $d$. Both our classical and quantum algorithms are optimal in the dimension parameters $n$ and $d$ up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Caratheodory problem and the $ell_{q}$-margin support vector machines as applications.
Quantum pseudo-telepathy is an intriguing phenomenon which results from the application of quantum information theory to communication complexity. To demonstrate this phenomenon researchers in the field of quantum communication complexity devised a number of quantum non-locality games. The setting of these games is as follows: the players are separated so that no communication between them is possible and are given a certain computational task. When the players have access to a quantum resource called entanglement, they can accomplish the task: something that is impossible in a classical setting. To an observer who is unfamiliar with the laws of quantum mechanics it seems that the players employ some sort of telepathy; that is, they somehow exchange information without sharing a communication channel. This paper provides a formal framework for specifying, implementing, and analysing quantum non-locality games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
