# Quantum spatial best-arm identification via quantum walks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 7 Sep 2025.

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

- [Learning agile and dynamic motor skills for legged robots](https://mlsanity.com/paper/1901.08652/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [Quantum-enhanced machine learning](https://mlsanity.com/paper/1610.08251/) (2016)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [Basic protocols in quantum reinforcement learning with superconducting circuits](https://mlsanity.com/paper/1701.05131/) (2017)
- [Dynamic channel selection in wireless communications via a multi-armed bandit algorithm using laser chaos time series](https://mlsanity.com/paper/1909.03629/) (2019)
- [A Bipartite Graph Neural Network Approach for Scalable Beamforming Optimization](https://mlsanity.com/paper/2207.05364/) (2022)
- [Quantum bandit with amplitude amplification exploration in an adversarial environment](https://mlsanity.com/paper/2208.07144/) (2022)
- [Multi-armed Bandit Learning on a Graph](https://mlsanity.com/paper/2209.09419/) (2022)
- [Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk](https://mlsanity.com/paper/2304.10118/) (2023)

## Abstract (arXiv)

Quantum reinforcement learning has emerged as a framework combining quantum computation with sequential decision-making, and applications to the multi-armed bandit (MAB) problem have been reported. The graph bandit problem extends the MAB setting by introducing spatial constraints, where the accessibility of arms is restricted by graph connectivity, yet quantum approaches to this setting remain limited. In this paper, we formulate best-arm identification in graph bandits and propose a quantum algorithmic framework, termed Quantum Spatial Best-Arm Identification (QSBAI), which is applicable to general graph structures. This framework uses quantum walks to encode superpositions over graph-constrained actions, thereby extending amplitude amplification and generalizing the quantum BAI algorithm via Szegedy's walk framework. We focus our theoretical analysis on complete and bipartite graphs, deriving the maximal success probability of identifying the best arm and the time step at which it is achieved. Our results clarify how quantum-walk-based search can be adapted to structurally constrained decision problems and provide a foundation for quantum best-arm identification in graph-structured environments.