# Quantum Bandits

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2020.

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

- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning](https://mlsanity.com/paper/2302.08617/) (2023)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [Quantum contextual bandits and recommender systems for quantum data](https://mlsanity.com/paper/2301.13524/) (2023)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Multi-Armed Bandits and Quantum Channel Oracles](https://mlsanity.com/paper/2301.08544/) (2023)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Quantum spatial best-arm identification via quantum walks](https://mlsanity.com/paper/2509.05890/) (2025)
- [Variational Quantum Circuits in Offline Contextual Bandit Problems](https://mlsanity.com/paper/2509.07633/) (2025)
- [Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits](https://mlsanity.com/paper/2603.18431/) (2026)
- [Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization](https://mlsanity.com/paper/2607.01080/) (2026)
- [Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms](https://mlsanity.com/paper/2608.14319/) (2026)
- [Quantum Monte Carlo Tree Search with Fixed Confidence](https://mlsanity.com/paper/2609.33132/) (2026)

## Abstract (arXiv)

We consider the quantum version of the bandit problem known as em best arm identification (BAI). We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum; we then propose an algorithm based on quantum amplitude amplification to solve BAI. We formally analyze the behavior of the algorithm on all instances of the problem and we show, in particular, that it is able to get the optimal solution quadratically faster than what is known to hold in the classical case.