Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning

• URL: http://arxiv.org/abs/2206.04741v2
• Date: Wed, 10 May 2023 08:36:41 GMT
• Title: Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning
• Authors: Simon Wiedemann, Daniel Hein, Steffen Udluft, Christian Mendl
• Abstract summary: 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.
• Score: 7.122914046030916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error-free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.

Related papers

• Robustness and Generalization in Quantum Reinforcement Learning via Lipschitz Regularization [2.8445375187526154]
  We propose a regularized version of a quantum policy gradient approach, named the RegQPG algorithm. We show that training with RegQPG improves the robustness and generalization of the resulting policies.
  arXiv  Detail & Related papers  (2024-10-28T15:20:35Z)
• Optimal Quantum Purity Amplification [2.05170973574812]
  Quantum purity amplification (QPA) offers a novel approach to counteract the pervasive noise that degrades quantum states. We present the optimal QPA protocol for general quantum systems against global depolarizing noise. Our findings suggest that QPA could improve the performance of quantum information processing tasks.
  arXiv  Detail & Related papers  (2024-09-26T17:46:00Z)
• 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)
• Quantum Imitation Learning [74.15588381240795]
  We propose quantum imitation learning (QIL) with a hope to utilize quantum advantage to speed up IL. We develop two QIL algorithms, quantum behavioural cloning (Q-BC) and quantum generative adversarial imitation learning (Q-GAIL) Experiment results demonstrate that both Q-BC and Q-GAIL can achieve comparable performance compared to classical counterparts.
  arXiv  Detail & Related papers  (2023-04-04T12:47:35Z)
• Improved iterative quantum algorithm for ground-state preparation [4.921552273745794]
  We propose an improved iterative quantum algorithm to prepare the ground state of a Hamiltonian system. Our approach has advantages including the higher success probability at each iteration, the measurement precision-independent sampling complexity, the lower gate complexity, and only quantum resources are required when the ancillary state is well prepared.
  arXiv  Detail & Related papers  (2022-10-16T05:57:43Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• Quantum Reinforcement Learning via Policy Iteration [6.961253535504979]
  We provide a general framework for performing quantum reinforcement learning via policy iteration. We validate our framework by designing and analyzing: emphquantum policy evaluation methods for infinite horizon discounted problems. We study the theoretical and experimental performance of our quantum algorithms on two environments from OpenAI's Gym.
  arXiv  Detail & Related papers  (2022-03-03T18:08:17Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• 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)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Hybrid quantum variational algorithm for simulating open quantum systems with near-term devices [0.0]
  Hybrid quantum-classical (HQC) algorithms make it possible to use near-term quantum devices supported by classical computational resources. We develop an HQC algorithm using an efficient variational optimization approach to simulate open system dynamics.
  arXiv  Detail & Related papers  (2020-08-12T13:49:29Z)

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.