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

• Determining Quantum Correlation through Nash Equilibria in Constant-Sum Games [0.0]
  Quantum game theory has emerged as a promising candidate to further the understanding of quantum correlations. Motivated by this, it is demonstrated that pure strategy Nash equilibria can be utilised as a mechanism to witness and determine quantum correlation.
  arXiv  Detail & Related papers  (2024-10-20T14:27:01Z)
• On the role of coherence for quantum computational advantage [0.5825410941577593]
  We introduce path coherence as a measure of the coherent paths interferences arising in a quantum computation. Our results have practical applications for simulating large classes of quantum computations with classical computers.
  arXiv  Detail & Related papers  (2024-10-09T16:06:07Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
  This paper introduces Character Complexity, a novel measure that bridges Group-theoretic concepts with practical quantum computing concerns. I prove several key properties of character complexity and establish a surprising connection to the classical simulability of quantum circuits. I present innovative visualization methods for character complexity, providing intuitive insights into the structure of quantum circuits.
  arXiv  Detail & Related papers  (2024-08-19T01:58:54Z)
• 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)
• 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)
• 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.