Research map / Bandits and online learning / Multi-armed bandits

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

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Fixed-confidence versus fixed-budget identification

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies quantum best arm identification under a limited number of adaptive rounds, giving lower bounds and round-limited algorithms.

Problem

Quantum best arm identification with O(n/Δ[2]) query complexity requires Ω(log(1/Δ[2])) or Ω(log n) adaptive rounds, which is costly on near-term quantum hardware.

Approach

Analyzes the trade-off between query complexity and the number of adaptive rounds in quantum best arm identification, proving lower bounds and designing algorithms that work with a limited number of rounds.

Key results

• Recent quantum algorithms achieve O(n/Δ[2]) query complexity but require Ω(log(1/Δ[2])) or Ω(log n) adaptive rounds (stated as motivation in abstract).

Experimental setup

Metrics: query complexity

Builds on: quantum best arm identification

Closest papers by meaning

• Quantum Best Arm Identification with Quantum Oracles (AAAI 2025 · similarity 0.94)
• Quantum Exploration Algorithms for Multi-Armed Bandits (AAAI 2021 · similarity 0.92)
• Quantum Speedup of Multi-armed Bandits at Scale by Tackling Memory Decoherence (NeurIPS 2026 · similarity 0.88)
• Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.87)
• Quantum Non-Linear Bandit Optimization (AAAI 2026 · similarity 0.87)
• Near Optimal Non-asymptotic Sample Complexity of 1-Identification (ICML 2025 · similarity 0.85)