2025/09/07 by Tomoki Yamagami, Yamagami, Tomoki, Etsuo Segawa +9
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Bipartite graph #Computation #Graph #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum machine learning #Quantum state #Quantum walk
paper · pdf · doi:10.1007/s11128-026-05189-y
published in Quantum Information Processing 25(6) (Springer Science+Business Media)
openalex publication_date 2026/05/18 · openalex created_date 2026/05/19 · openalex updated_date 2026/05/19
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, 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.