Quantum game theory and the complexity of approximating quantum Nash
equilibria
- URL: http://arxiv.org/abs/2102.00512v2
- Date: Fri, 16 Dec 2022 18:12:14 GMT
- Title: Quantum game theory and the complexity of approximating quantum Nash
equilibria
- Authors: John Bostanci and John Watrous
- Abstract summary: This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory.
In particular, we prove that the computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is included in (and therefore complete for) the complexity class PPAD.
- Score: 0.6091702876917281
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: This paper is concerned with complexity theoretic aspects of a general
formulation of quantum game theory that models strategic interactions among
rational agents that process and exchange quantum information. In particular,
we prove that the computational problem of finding an approximate Nash
equilibrium in a broad class of quantum games is, like the analogous problem
for classical games, included in (and therefore complete for) the complexity
class PPAD. Our main technical contribution, which facilitates this inclusion,
is an extension of prior methods in computational game theory to strategy
spaces that are characterized by semidefinite programs.
Related papers
- Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process.
We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable.
Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs.
We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
arXiv Detail & Related papers (2024-05-12T09:05:13Z) - Where Quantum Complexity Helps Classical Complexity [2.5751645168025297]
Adapting problem-solving strategies is crucial to harness the full potential of quantum computing.
This paper concentrates on aggregating prior research efforts dedicated to solving intricate classical computational problems through quantum computing.
arXiv Detail & Related papers (2023-12-16T16:02:21Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Does Quantum Mechanics Breed Larger, More Intricate Quantum Theories?
The Case for Experience-Centric Quantum Theory and the Interactome of Quantum
Theories [0.0]
We show that the recently proposed experience-centric quantum theory (ECQT) is a larger and richer theory of quantum behaviors.
ECQT allows the quantum information of the closed quantum system's developed state history to continually contribute to defining manybody interactions.
The interplay of unitarity and non-Markovianity in ECQT brings about a host of diverse behavioral phases.
arXiv Detail & Related papers (2023-08-04T16:33:24Z) - The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for
Deep Quantum Machine Learning [52.77024349608834]
Building a quantum analog of classical deep neural networks represents a fundamental challenge in quantum computing.
Key issue is how to address the inherent non-linearity of classical deep learning.
We introduce the Quantum Path Kernel, a formulation of quantum machine learning capable of replicating those aspects of deep machine learning.
arXiv Detail & Related papers (2022-12-22T16:06:24Z) - Complex Field Formulation of the Quantum Estimation Theory [0.0]
We present a complex field formulation of the quantum Fisher estimation theory that works with complex statistics on the dependence of complex parameters.
This can be useful in contexts where the quantum states are described through complex parameters, as coherent states or squeezed states.
arXiv Detail & Related papers (2022-03-06T22:34:30Z) - Computation in a general physical setting [0.0]
This paper reviews and extends some results on the computational ability of quantum theory.
It provides a refined version of the conjecture that a quantum computer can simulate the computation in any theory.
It ends by describing an important relation between this conjecture and delegated computation, similar to the relation between quantum non-locality and device-independent cryptography.
arXiv Detail & Related papers (2021-08-25T20:00:20Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks.
Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts.
We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
arXiv Detail & Related papers (2021-06-11T18:00:09Z) - A general quantum algorithm for open quantum dynamics demonstrated with
the Fenna-Matthews-Olson complex [0.0]
We develop a quantum algorithm to simulate any dynamical process represented by either the operator sum representation or the Lindblad master equation.
We demonstrate the quantum algorithm by simulating the dynamics of the Fenna-Matthews-Olson complex on the IBM QASM quantum simulator.
arXiv Detail & Related papers (2021-01-13T19:00:02Z) - Preferred basis, decoherence and a quantum state of the Universe [77.34726150561087]
We review a number of issues in foundations of quantum theory and quantum cosmology.
These issues can be considered as a part of the scientific legacy of H.D. Zeh.
arXiv Detail & Related papers (2020-06-28T18:07:59Z) - From a quantum theory to a classical one [117.44028458220427]
We present and discuss a formal approach for describing the quantum to classical crossover.
The method was originally introduced by L. Yaffe in 1982 for tackling large-$N$ quantum field theories.
arXiv Detail & Related papers (2020-04-01T09:16:38Z)
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.