Quantum Best Arm Identification with Limited Round of Adaptivity: Lower Bounds and Algorithms

Best arm identification, also known as pure exploration, is a fundamental problem in the multi-armed bandit (MAB) model. Recent quantum algorithms achieve $O(n/\Delta_{[2]})$ query complexity for identifying the best arm with high constant probability, but all of them require $\Omega(\log(1/\Delta_{[2]}))$ or $\Omega(\log n)$ adaptive rounds. Motivated by the practical cost of adaptivity on near-term quantum hardware, where each round incurs substantial overhead from state re-preparation and classical--quantum communication, we study quantum best arm identification with no or very limited adaptivity. On the lower bound side, we prove that any non-adaptive quantum algorithm must make $\Omega(n\log n)$ queries when $\Delta_{[2]}=O(1)$, establishing a separation between adaptive and non-adaptive algorithms. To complement this lower bound, we present an algorithm that identifies the best arm with high constant probability using $O(n/\Delta_{[2]})$ queries and only $\log^*(n)+1$ adaptive rounds. En route to the lower bound, we show that the instances and techniques used to prove adaptivity lower bounds for classical bandits, such as those of Agarwal et al. [COLT'17], do not extend to the quantum setting. As such, we employ the polynomial method to prove our adaptivity lower bounds. To the best of our knowledge, this represents the first application of the polynomial method in this context, which may be of independent interest.