Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

• URL: http://arxiv.org/abs/2608.02826v1
• Date: Mon, 03 Aug 2026 19:38:31 GMT
• Title: Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
• Abstract summary: We propose new quantum algorithms for computing approximate optimal policies.<n>Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.

Related papers

• Optimal Quantum Likelihood Estimation [0.0]
  A hybrid quantum-classical algorithm is a computational scheme in which quantum circuits are used to extract information.<n>We improve the performance of a hybrid algorithm through principled, information-theoretic optimization.
  arXiv  Detail & Related papers  (2025-08-31T12:51:44Z)
• An em algorithm for quantum Boltzmann machines [40.40469032705598]
  We develop a quantum version of the em algorithm for training quantum Boltzmann machines.<n>We implement the algorithm on a semi-quantum restricted Boltzmann machine, where quantum effects are confined to the hidden layer.
  arXiv  Detail & Related papers  (2025-07-29T07:59:22Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach.<n>The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• Warm-Start Variational Quantum Policy Iteration [39.04157716488156]
  Reinforcement learning is a powerful framework aiming to determine optimal behavior in highly complex decision-making scenarios. We propose the variational quantum policy iteration (VarQPI) algorithm, realizing this step with a NISQ-compatible quantum-enhanced subroutine. Its scalability is supported by an analysis of the structure of generic reinforcement learning environments.
  arXiv  Detail & Related papers  (2024-04-16T13:16:19Z)
• 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)
• Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
  We introduce an innovative quantum framework for the agent's engagement with an unknown MDP.<n>We show that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning.
  arXiv  Detail & Related papers  (2023-10-18T03:17:51Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• Quantum Policy Gradient Algorithm with Optimized Action Decoding [1.3946033794136758]
  We introduce a novel quality measure that enables us to optimize the classical post-processing required for action selection. With this technique, we successfully execute a full training routine on a 5-qubit hardware device.
  arXiv  Detail & Related papers  (2022-12-13T15:42:10Z)
• Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning [7.122914046030916]
  We show how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached.
  arXiv  Detail & Related papers  (2022-06-09T19:23:10Z)
• Parametrized Complexity of Quantum Inspired Algorithms [0.0]
  Two promising areas of quantum algorithms are quantum machine learning and quantum optimization. Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-22T06:19:36Z)

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.