Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games

• URL: http://arxiv.org/abs/2304.14197v2
• Date: Mon, 30 Sep 2024 15:59:21 GMT
• Title: Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
• Authors: Minbo Gao, Zhengfeng Ji, Tongyang Li, Qisheng Wang,
• Abstract summary: 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.
• Score: 10.79781442303645
• License:
• Abstract: We propose the first online quantum algorithm for solving zero-sum games with $\widetilde O(1)$ regret under the game setting. Moreover, our quantum algorithm computes an $\varepsilon$-approximate Nash equilibrium of an $m \times n$ matrix zero-sum game in quantum time $\widetilde O(\sqrt{m+n}/\varepsilon^{2.5})$. Our algorithm uses standard quantum inputs and generates classical outputs with succinct descriptions, facilitating end-to-end applications. Technically, our online quantum algorithm "quantizes" classical algorithms based on the optimistic multiplicative weight update method. At the heart of our algorithm is a fast quantum multi-sampling procedure for the Gibbs sampling problem, which may be of independent interest.

Related papers

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
  arXiv  Detail & Related papers  (2024-09-06T03:32:02Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Predicting Gibbs-State Expectation Values with Pure Thermal Shadows [1.4050836886292868]
  We propose a quantum algorithm that can predict $M$ linear functions of an arbitrary Gibbs state with only $mathcalO(logM)$ experimental measurements. We show that the algorithm can be successfully employed as a subroutine for training an eight-qubit fully connected quantum Boltzmann machine.
  arXiv  Detail & Related papers  (2022-06-10T18:00:08Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• Quantum algorithms for escaping from saddle points [7.191453718557392]
  We study quantum algorithms for escaping from saddle points with provable guarantee. Our main contribution is the idea of replacing the classical perturbations in gradient descent methods. We also show how to use a quantum gradient computation algorithm due to Jordan.
  arXiv  Detail & Related papers  (2020-07-20T16:42:53Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.