Research map / Bandits and online learning / Multi-armed bandits
Quantum Best Arm Identification with Quantum Oracles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies best arm identification in bandits with quantum oracles (weak one-arm and m-constrained multi-arm coherent queries), proposing Q-Elim and Q-Part with near-matching query complexity bounds and Qiskit simulations.
Problem
Best arm identification with fixed confidence in multi-armed bandits when the learner can query arms through quantum oracles, aiming to reduce query complexity below classical bounds.
Approach
Introduces a weak quantum oracle (one arm per query, enabling quantum mean estimation) and an m-constrained quantum oracle (coherent access to m arms per query); an elimination algorithm (Q-Elim) built on quantum mean estimation for the weak case and a partition-based algorithm (Q-Part) using variable-time amplitude amplification for the constrained case, with matching lower bounds.
Key results
- Q-Elim achieves query complexity upper bound of about O~(sum_k Delta_k^-1 log(1/delta)), improving the classical Delta^-2 dependence by a factor of Delta^-1.
- Q-Part achieves O~((K/sqrt(m)) Delta^-1 log(1/delta)) upper bound and matching lower bounds up to log factors within the partition algorithm class.
- Qiskit simulation (50 trials) shows Q-Elim outperforms SuccElim and Q-Part query counts decrease as m grows; under a simulated 127-qubit IBM noise model Q-Elim degrades by 2.38% (m=2) and 8.09% (m=4), and Q-Part fails at m=8.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use quantum estimation instead of classical reward estimation | BAI with a weak oracle · BAI | query complexity dependence on reward gap: Δ^{-2} to Δ^{-1} | Helped |
| use Q-Part with an m-constrained oracle instead of the m=1 case | BAI · BAI | query complexity: a factor of √m | Helped |
| increase the oracle constraint from m=2 to m=4 or m=8 | Q-Part · Qiskit simulation, K=8 | query complexity | Helped |
| simulate quantum noise on Q-Part with m=2 | Q-Part · Qiskit simulated 127-qubit device, gap = 0.01 | performance: 2.38% | Hurt |
| simulate quantum noise on Q-Part with m=4 | Q-Part · Qiskit simulated 127-qubit device, gap = 0.01 | performance: 8.09% | Hurt |
| use m=8 under simulated quantum noise | Q-Part · Qiskit simulated 127-qubit device, gap = 0.01 | algorithm success | Hurt |
Surprising findings
- Under simulated hardware noise, the m=8 (strong oracle) Q-Part implementation fails because the qubit and gate requirements exceed practical limits.
Limitations
- Q-Part with m=8 fails under simulated noise due to qubit and gate overhead.
- Lower bound for the m-constrained case is proven only for the partition algorithm class.
- Experiments are simulation-only on small (K=8) Bernoulli instances; the quantum constant factors may be larger than assumed.
Experimental setup
Benchmarks: simulated 8-arm Bernoulli bandit instances
Metrics: query complexity query count vs gap
Baselines: SuccElim classical BAI (Mannor and Tsitsiklis 2004; Karnin et al. 2013) Wang et al. 2021 strong quantum oracle algorithm
Builds on: successive elimination quantum mean estimation (QuEst) variable-time amplitude amplification strong quantum oracle BAI (Wang et al. 2021)
Closest papers by meaning
- Quantum Best Arm Identification with Limited Round of Adaptivity: Lower Bounds and Algorithms (NeurIPS 2026 · similarity 0.94)
- Quantum Exploration Algorithms for Multi-Armed Bandits (AAAI 2021 · similarity 0.92)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.86)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.85)
- Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? (NeurIPS 2026 · similarity 0.85)
- Near Optimal Best Arm Identification for Clustered Bandits (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.