mlsanityData to 14 Oct 2026

Quantum spatial best-arm identification via quantum walks

arXiv 2509.05890 ↗First posted 7 Sep 2025quant-ph cs.AI cs.LGcited by 0

Not on the map. Why?

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.

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

13 of 58 references.

References · 13

  1. 2019Learning agile and dynamic motor skills for legged robotscited by 504
  2. 2019Introduction to Multi-Armed Banditscited by 481
  3. 2016Quantum Machine Learningcited by 326
  4. 2024Reinforcement learningcited by 247
  5. 2016Quantum-enhanced machine learningcited by 79
  6. 2020Quantum exploration algorithms for multi-armed banditscited by 22
  7. 2020Quantum Banditscited by 18
  8. 2017Basic protocols in quantum reinforcement learning with superconducting circuitscited by 8
  9. 2019Dynamic channel selection in wireless communications via a multi-armed bandit algorithm using laser chaos time seriescited by 7
  10. 2022A Bipartite Graph Neural Network Approach for Scalable Beamforming Optimizationcited by 7
  11. 2022Quantum bandit with amplitude amplification exploration in an adversarial environmentcited by 5
  12. 2022Multi-armed Bandit Learning on a Graphcited by 3
1 more
  1. 2023Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walkcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search
  2. 2025QSearchNet: A Quantum Walk Search Framework for Link Prediction
  3. 2023Multi-Armed Bandits and Quantum Channel Oracles
  4. 2024Hamiltonian-based Quantum Reinforcement Learning for Neural Combinatorial Optimization
  5. 2026Reinforcement learning for quantum processes with memory
  6. 2026Reinforcement Learning for Quantum Technology
  7. 2026Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
  8. 2025BenchRL-QAS: Benchmarking reinforcement learning algorithms for quantum architecture search