© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2509.05890 · Quantum Information Processing

Quantum spatial best-arm identification on a complete bipartite graph

Tomoki Yamagami, Etsuo Segawa, Takatomo Mihana, André Röhm, Atsushi Uchida, Ryoichi Horisaki

Published May 18, 2026• 0 citations

Abstract

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.

DOI: 10.1007/s11128-026-05189-y

Related papers

Quantum Reinforcement Learning for Multi-Armed Bandits

Yi-Pei Liu, Kuo Li, Xi Cao +2 more

This work focuses on the multi-armed bandits (MAB) problem and proposes a quantum reinforcement learning (RL) algorithm for action selection. Existing quantum RL algorithms generally assume that some prior information about the optimal action is known, and initial probability is set unequally. Our algorithm can be executed with equal initial probability on each action, and can greatly accelerate the learning process.

Chinese Control Conference (CCC)•Jul 25, 2022•1 citation

Quantum Exploration Algorithms for Multi-Armed Bandits

Daochen Wang, Xuchen You, Tongyang Li +1 more

Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

arXiv:2007.07049•Proceedings of the AAAI Conference on Artificial Intelligence•May 18, 2021•20 citations

Quantum Top Arms Identification in Multi-Armed Bandits

Xuchuang Wang, Yu-Zhen Janice Chen, Matheus Guedes de Andrade +3 more

We investigate the top-$m$arm identification problem in a quantum multi-armed bandit (MAB) setting. Given$K$arms whose rewards follow Bernoulli distributions with unknown means, the objective is to return the$m$arms with the largest means with confidence at least$1-\delta$. Many practical tasks-e.g., selecting the best$m$routing paths in a quantum network or the best$m$quantum circuits for a given computation-fit naturally into this framework. We introduce Q-GapE, an elimination-based algorithm that queries each arm through a weak quantum oracle.$\mathrm{Q}$- GapE attains the query complexity guarantee$\tilde{O}\left(\sum_{k=1}^{K}\left(1 / \Delta_{k}^{(m)}\right) \log (1 / \delta)\right)$, where$\Delta_{k}^{(m)}$denotes the gap between arm$k$'s mean and the$m$-th largest mean. Compared with the best classical-oracle bound, this result offers a quadratic quantum speed-up. Extensive simulations confirm that$\mathrm{Q}-\text{GapE}$consistently outperforms leading classical MAB algorithms in both query complexity and running time. These findings highlight the potential of quantum bandit algorithms to deliver substantial efficiency gains over their classical counterparts.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Quantum Best Arm Identification

Xuchuang Wang, Yu-Zhen Janice Chen, Matheus Guedes de Andrade +3 more

Recent progress on building quantum computers [1] envisages wide applications of quantum algorithms in the near future. With the advantage of quantum computer, one can speed up not only fundamental algorithms, e.g., unstructured search [6] and factoring [11], but recent machine learning algorithms [3] as well. In this paper, we study the quantum speedup on a canonical task of reinforcement learning-best arm identification in multi-armed bandits.

ACM SIGMETRICS Performance Evaluation Review•Sep 28, 2023•1 citation

Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk

Tomoki Yamagami, Etsuo Segawa, Takatomo Mihana +3 more

Quantum walks (QWs) have a property that classical random walks (RWs) do not possess-the coexistence of linear spreading and localization-and this property is utilized to implement various kinds of applications. This paper proposes RW- and QW-based algorithms for multi-armed-bandit (MAB) problems. We show that, under some settings, the QW-based model realizes higher performance than the corresponding RW-based one by associating the two operations that make MAB problems difficult-exploration and exploitation-with these two behaviors of QWs.

arXiv:2304.10118•Entropy•May 25, 2023•7 citations

Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

Maoli Liu, Zhuohua Li, John C. S. Lui

We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon $T$ with regret $O(K\log T)$ for QMAB with $K$ arms and $O(d^2\operatorname{polylog} T)$ for $d$-dimensional QLB. This leaves open the optimal dependence on $K$ and $T$ and whether the dependence on $d$ can be further improved. In this work, we prove the first tight minimax regret bound of $Θ(K\log(1+T/K))$ for QMAB and the first lower bound of $Ω(d\log(1+T/d))$ for finite-action QLB, ruling out regret independent of $T$. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support $G$-optimal design through a query allocation matched to the design weights. When the action set has size $\operatorname{poly}(d)$, its regret is nearly linear in $d$ and matches our lower bound up to polylogarithmic factors.

cs.LGCross-listedarXiv:2608.14319•Aug 17, 2026•0 citations

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.

Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

We investigate the top-

m

arm identification problem in a quantum multi-armed bandit (MAB) setting. Given

K

arms whose rewards follow Bernoulli distributions with unknown means, the objective is to return the

m

arms with the largest means with confidence at least

1-\delta

. Many practical tasks-e.g., selecting the best

m

routing paths in a quantum network or the best

m

quantum circuits for a given computation-fit naturally into this framework. We introduce Q-GapE, an elimination-based algorithm that queries each arm through a weak quantum oracle.

\mathrm{Q}

- GapE attains the query complexity guarantee

\tilde{O}\left(\sum_{k=1}^{K}\left(1 / \Delta_{k}^{(m)}\right) \log (1 / \delta)\right)

, where

\Delta_{k}^{(m)}

denotes the gap between arm

k

's mean and the

m

-th largest mean. Compared with the best classical-oracle bound, this result offers a quadratic quantum speed-up. Extensive simulations confirm that

\mathrm{Q}-\text{GapE}

consistently outperforms leading classical MAB algorithms in both query complexity and running time. These findings highlight the potential of quantum bandit algorithms to deliver substantial efficiency gains over their classical counterparts.

Quantum walks (QWs) have a property that classical random walks (RWs) do not possess-the coexistence of linear spreading and localization-and this property is utilized to implement various kinds of applications. This paper proposes RW- and QW-based algorithms for multi-armed-bandit (MAB) problems. We show that, under some settings, the QW-based model realizes higher performance than the corresponding RW-based one by associating the two operations that make MAB problems difficult-exploration and exploitation-with these two behaviors of QWs.

We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon

T

with regret

O(K\log T)

for QMAB with

K

arms and

O(d^2\operatorname{polylog} T)

for

d

-dimensional QLB. This leaves open the optimal dependence on

K

and

T

and whether the dependence on

d

can be further improved. In this work, we prove the first tight minimax regret bound of

Θ(K\log(1+T/K))

for QMAB and the first lower bound of

Ω(d\log(1+T/d))

for finite-action QLB, ruling out regret independent of

T

. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support

G

-optimal design through a query allocation matched to the design weights. When the action set has size

\operatorname{poly}(d)

, its regret is nearly linear in

d

and matches our lower bound up to polylogarithmic factors.