Quantum multi-armed bandits (MAB) and stochastic linear bandits (SLB) have recently attracted significant attention, as their quantum counterparts can achieve quadratic speedups over classical MAB and SLB. However, most existing quantum MAB algorithms assume ideal quantum Monte Carlo (QMC) procedures on noise-free circuits, overlooking the impact of noise in current noisy intermediate-scale quantum (NISQ) devices. In this paper, we study a noise-robust QMC algorithm that improves estimation accuracy when querying quantum reward oracles. Building on this estimator, we propose noise-robust QMAB and QSLB algorithms that enhance performance in noisy environments while preserving the advantage over classical methods. Experiments show that our noise-robust approach improves QMAB estimation accuracy and reduces regret under several quantum noise models.
In this paper, we study multi-armed bandits (MAB) and stochastic linear bandits (SLB) with heavy-tailed rewards and quantum reward oracle. Unlike the previous work on quantum bandits that assumes bounded/sub-Gaussian distributions for rewards, here we investigate the quantum bandits problem under a weaker assumption that the distributions of rewards only have bounded
(1+v)-th moment for some
v∈(0,1]. In order to achieve regret improvements for heavy-tailed bandits, we first propose a new quantum mean estimator for heavy-tailed distributions, which is based on the Quantum Monte Carlo Mean Estimator and achieves a quadratic improvement of estimation error compared to the classical one. Based on our quantum mean estimator, we focus on quantum heavy-tailed MAB and SLB and propose quantum algorithms based on the Upper Confidence Bound (UCB) framework for both problems with $\Tilde{O}(T^{\frac{1-v}{1+v}})$ regrets, polynomially improving the dependence in terms of
T as compared to classical (near) optimal regrets of $\Tilde{O}(T^{\frac{1}{1+v}})$, where
T is the number of rounds. Finally, experiments also support our theoretical results and show the effectiveness of our proposed methods.
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(KlogT) for QMAB with
K arms and
O(d2polylogT) 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
Θ(Klog(1+T/K)) for QMAB and the first lower bound of
Ω(dlog(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
poly(d), its regret is nearly linear in
d and matches our lower bound up to polylogarithmic factors.
Variational quantum circuits (VQCs) are central to near-term quantum computing, yet their practical deployment is severely hindered by noise. While existing error mitigation methods, such as zero-noise extrapolation (ZNE), typically assume static noise, real noisy intermediate-scale quantum (NISQ) systems exhibit dynamic, time-varying noise that remains largely unaddressed. To overcome this critical gap, our work introduces a novel adaptive noise mitigation framework for VQCs that integrates ZNE with contextual multi-armed bandits (CMAB), enabling dynamic, context-aware selection of circuit-folding levels based on ansatz parameters (e.g., depth, parameter count) and the evolving noise environment. Unlike fixed-fold or heuristic ZNE, our approach uses online adaptation to improve the accuracy of ZNE and reduce redundant quantum circuit executions. Our extensive simulations and experiments on real quantum hardware reveal the following important properties: (i) deeper VQCs accumulate noise, degrading accuracy and increasing the number of quantum circuit executions; (ii) ZNE restores estimator fidelity when the folding level is chosen appropriately; and (iii) CMAB-guided folding cuts quantum circuit execution round trips by up to 40\%, bytes exchanged by up to 35\%, and end-to-end cost by up to 30\% under a 10~Mbps budget, with up to 6.9\% higher estimator fidelity (CIFAR-10, depth 3, noise band
η=0.05), versus fixed-fold and grid-search ZNE. These results demonstrate substantial performance gains over existing noise mitigation methods, underscoring the effectiveness of our design in supporting robust noise mitigation for VQCs. The source code is also publicly released to support reproducibility.
Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer from the regret of at least the square root of T. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with the order of the polylog T regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.
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).
The Lipschitz bandit is a key variant of stochastic bandit problems where the expected reward function satisfies a Lipschitz condition with respect to an arm metric space. With its wide-ranging practical applications, various Lipschitz bandit algorithms have been developed, achieving the optimal regret performance in the classical setting. Motivated by recent advancements in quantum computing and the demonstrated success of quantum Monte Carlo in simpler bandit settings, we introduce the first quantum Lipschitz bandit algorithms to address the challenges of continuous action spaces and non-linear reward functions. Specifically, we first leverage the elimination-based framework to propose an efficient quantum Lipschitz bandit algorithm named Q-LAE. Next, we present novel modifications to the classical Zooming algorithm, which results in a simple quantum Lipschitz bandit method, Q-Zooming. Both algorithms exploit the computational power of quantum methods to obtain a provably improved regret bound over classical Lipschitz bandit algorithms. Comprehensive experiments further validate our improved theoretical findings, demonstrating superior empirical performance compared to existing Lipschitz bandit methods.