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

arXiv: https://arxiv.org/abs/2206.04741 · HTML: https://mlsanity.com/paper/2206.04741/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 9 Jun 2022.

## Builds on (most cited first, 7 of 7)

- [Variational Quantum Circuits for Deep Reinforcement Learning](https://mlsanity.com/paper/1907.00397/) (2019)
- [Quantum-enhanced machine learning](https://mlsanity.com/paper/1610.08251/) (2016)
- [Reinforcement Learning with Quantum Variational Circuits](https://mlsanity.com/paper/2008.07524/) (2020)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Quantum Reinforcement Learning via Policy Iteration](https://mlsanity.com/paper/2203.01889/) (2022)
- [Framework for learning agents in quantum environments](https://mlsanity.com/paper/1507.08482/) (2015)
- [Exponential improvements for quantum-accessible reinforcement learning](https://mlsanity.com/paper/1710.11160/) (2017)

## Built on by (most cited first, 21 of 21)

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Asynchronous training of quantum reinforcement learning](https://mlsanity.com/paper/2301.05096/) (2023)
- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Benchmarking Quantum Reinforcement Learning](https://mlsanity.com/paper/2501.15893/) (2025)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Model-based Offline Quantum Reinforcement Learning](https://mlsanity.com/paper/2404.10017/) (2024)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search](https://mlsanity.com/paper/2412.18208/) (2024)
- [Provable Quantum Algorithm Advantage for Gaussian Process Quadrature](https://mlsanity.com/paper/2502.14467/) (2025)
- [Quantum deep Q learning with distributed prioritized experience replay](https://mlsanity.com/paper/2304.09648/) (2023)
- [GPA: Grover Policy Agent for Generating Optimal Quantum Sensor Circuits](https://mlsanity.com/paper/2502.13755/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Scalable Quantum Reinforcement Learning on NISQ Devices with Dynamic-Circuit Qubit Reuse and Grover Optimization](https://mlsanity.com/paper/2509.16002/) (2025)
- [Differentiable Quantum Computing for Large-scale Linear Control](https://mlsanity.com/paper/2411.01391/) (2024)
- [HCQA: Hybrid Classical-Quantum Agent for Generating Optimal Quantum Sensor Circuits](https://mlsanity.com/paper/2508.21246/) (2025)
- [From Classical Data to Quantum Advantage -- Quantum Policy Evaluation on Quantum Hardware](https://mlsanity.com/paper/2509.07614/) (2025)
- [Variational Quantum Circuits in Offline Contextual Bandit Problems](https://mlsanity.com/paper/2509.07633/) (2025)
- [Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding](https://mlsanity.com/paper/2607.11936/) (2026)
- [Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model](https://mlsanity.com/paper/2608.02826/) (2026)
- [Do Quantum AIs Dream in Paths? Path-Integral Slow Thinking through Grover Interference](https://mlsanity.com/paper/2609.05842/) (2026)

## Abstract (arXiv)

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.