Learning in Quantum Common-Interest Games and the Separability Problem

• URL: http://arxiv.org/abs/2302.04789v3
• Date: Sun, 30 Mar 2025 12:13:11 GMT
• Title: Learning in Quantum Common-Interest Games and the Separability Problem
• Authors: Wayne Lin, Georgios Piliouras, Ryann Sim, Antonios Varvitsiotis,
• Abstract summary: We introduce quantum common-interest games (CIGs) where players have density matrices as strategies and their interests are perfectly aligned.<n>We bridge the gap between optimization and game theory by establishing the equivalence between KKT (first-order stationary) points of an instance of the Best Separable State (BSS) problem and the Nash equilibria of its corresponding quantum CIG.<n>Taking the perspective of learning in games, we then introduce non-commutative extensions of the continuous-time replicator dynamics and the discrete-time best response dynamics/linear multiplicative weights update for learning in quantum
• Score: 29.768913836823973
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning in games has emerged as a powerful tool for machine learning with numerous applications. Quantum games model interactions between strategic players who have access to quantum resources, and several recent works have studied {learning in} the competitive regime of quantum zero-sum games. Going beyond this setting, we introduce quantum common-interest games (CIGs) where players have density matrices as strategies and their interests are perfectly aligned. We bridge the gap between optimization and game theory by establishing the equivalence between KKT (first-order stationary) points of an instance of the Best Separable State (BSS) problem and the Nash equilibria of its corresponding quantum CIG. This allows learning dynamics for the quantum CIG to be seen as decentralized algorithms for the BSS problem. Taking the perspective of learning in games, we then introduce non-commutative extensions of the continuous-time replicator dynamics and the discrete-time best response dynamics/linear multiplicative weights update for learning in quantum CIGs. We prove analogues of classical convergence results of the dynamics and explore differences which arise in the quantum setting. Finally, we corroborate our theoretical findings through extensive experiments.

Related papers

• Hybrid quantum-classical approach for combinatorial problems at hadron colliders [7.2572969510173655]
  We explore the potential of quantum algorithms to resolve the problems in particle physics experiments. We consider top quark pair production in the fully hadronic channel at the Large Hadron Collider. We show that the efficiency for selecting the correct pairing is greatly improved by utilizing quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-29T18:00:07Z)
• 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)
• Transfer of quantum game strategies [0.0]
  We show a new class of QNS correlations needed for the transfer of strategies between games. We define jointly tracial correlations and show they correspond to traces acting on tensor products of canonical $rm C*$-algebras associated with individual game parties.
  arXiv  Detail & Related papers  (2024-10-12T17:25:58Z)
• 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)
• Solving the Turbine Balancing Problem using Quantum Annealing [0.0]
  We describe how the Turbine Balancing Problem can be solved with quantum computing. Small yet relevant instances occur in industry, which makes the problem interesting for early quantum computing benchmarks.
  arXiv  Detail & Related papers  (2024-05-10T11:52:40Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Challenges and Opportunities in Quantum Optimization [14.7608536260003]
  Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. Across computer science and physics, there are different approaches for major optimization problems.
  arXiv  Detail & Related papers  (2023-12-04T19:00:44Z)
• 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)
• No-Regret Learning and Equilibrium Computation in Quantum Games [32.52039978254151]
  This paper delves into the dynamics of quantum-enabled agents within decentralized systems. We show that no-regret algorithms converge to separable quantum Nash equilibria in time-average. In the case of general multi-player quantum games, our work leads to a novel solution concept, (separable) quantum coarse correlated equilibria (QCCE)
  arXiv  Detail & Related papers  (2023-10-12T16:29:56Z)
• Exploring the topological sector optimization on quantum computers [5.458469081464264]
  topological sector optimization (TSO) problem attracts particular interests in the quantum many-body physics community. We demonstrate that the optimization difficulties of TSO problem are not restricted to the gaplessness, but are also due to the topological nature. To solve TSO problems, we utilize quantum imaginary time evolution (QITE) with a possible realization on quantum computers.
  arXiv  Detail & Related papers  (2023-10-06T14:51:07Z)
• Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
  We explore the applicability of quantum-data learning to practical problems in high-energy physics. We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states. The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
  arXiv  Detail & Related papers  (2023-06-29T18:00:01Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• Recent Advances for Quantum Neural Networks in Generative Learning [98.88205308106778]
  Quantum generative learning models (QGLMs) may surpass their classical counterparts. We review the current progress of QGLMs from the perspective of machine learning. We discuss the potential applications of QGLMs in both conventional machine learning tasks and quantum physics.
  arXiv  Detail & Related papers  (2022-06-07T07:32:57Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)
• Quantum Federated Learning with Quantum Data [87.49715898878858]
  Quantum machine learning (QML) has emerged as a promising field that leans on the developments in quantum computing to explore large complex machine learning problems. This paper proposes the first fully quantum federated learning framework that can operate over quantum data and, thus, share the learning of quantum circuit parameters in a decentralized manner.
  arXiv  Detail & Related papers  (2021-05-30T12:19:27Z)
• Quantum Go Machine [15.33065067850941]
  We experimentally demonstrate a quantum version of Go using correlated photon pairs entangled in polarization degree of freedom. Some quantum resources, like coherence or entanglement, can also be encoded to represent the state of quantum stones. Our results establish a paradigm of inventing new games with quantum-enabled difficulties.
  arXiv  Detail & Related papers  (2020-07-23T18:00:01Z)
• Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
  We review and extend the application of deep learning to quantum geometric control problems. We demonstrate enhancements in time-optimal control in the context of quantum circuit synthesis problems. Our results are of interest to researchers in quantum control and quantum information theory seeking to combine machine learning and geometric techniques for time-optimal control problems.
  arXiv  Detail & Related papers  (2020-06-19T19:12:14Z)
• Quantum mean field games [0.0]
  Quantum games represent the 21st century branch of game theory, tightly linked to the modern development of quantum computing and quantum technologies. In this paper we are merging these two exciting new branches of game theory. We derive the new nonlinear Schr"odinger equation as the limit of continuously observed and controlled system of large number of interacting quantum particles.
  arXiv  Detail & Related papers  (2020-05-05T17:35:54Z)

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.