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 show that we can find the best arm
with fixed confidence using
$\tilde{O}\bigl(\sqrt{\sum_{i=2}^n\Delta^{\smash{-2}}_i}\bigr)$ quantum
queries, where $\Delta_{i}$ represents the difference between the mean reward
of the best arm and the $i^\text{th}$-best arm. This algorithm, based on
variable-time amplitude amplification and estimation, gives a quadratic speedup
compared to the best possible classical result. We also prove a matching
quantum lower bound (up to poly-logarithmic factors).

文章研究了一个量子计算版本的多臂老虎机问题，使用相干的 Oracle 访问状态，用 amplitudes 编码每个臂的奖励概率。特别地，作者提出了一种基于可变时间幅度放大和估计，用  Θ(| 根号 (n)| 乘以 | 根号 ∑_i=2^n Δ^(-2)_i|) 次量子查询可以找到最佳臂的算法。这个算法与经典算法相比，速度提升了一个平方级别。作者也证明了相匹配的量子下界（多项式对数因子）