Combinatorial bandits offer a principled framework for sequential decisionmaking under uncertainty.However, in drug discovery, classical algorithms often struggle to model complex fragment interactions and suffer from high sample complexity.This paper introduces three quantum-enhanced combinatorial bandit algorithms that leverage the expressive power of parameterized quantum circuits.Quantum Thompson Sampling (Q-TS) samples actions directly from a quantum posterior.Quantum Combinatorial UCB (Q-CUCB) uses the diagonal elements of the quantum Fisher information matrix as an intrinsic uncertainty measure.Quantum-Neural Bandit (Q-Neural) combines quantum feature extraction with a classical neural network for context-aware decisions.Experiments on data from the ChEMBL database demonstrate that while classical linear methods achieve the lowest mean regret, the quantum methods excel in stability, near-optimal performance, and interpretability-unique advantages that are critical for reliable drug discovery.This work establishes quantum combinatorial bandits as a versatile tool offering benefits beyond raw regret minimization.
Combinatorial bandits offer a principled framework for sequential decisionmaking under uncertainty.However, in drug discovery, classical algorithms often struggle to model complex fragment interactions and suffer from high sample complexity.This paper introduces three quantum-enhanced combinatorial bandit algorithms that leverage the expressive power of parameterized quantum circuits.Quantum Thompson Sampling (Q-TS) samples actions directly from a quantum posterior.Quantum Combinatorial UCB (Q-CUCB) uses the diagonal elements of the quantum Fisher information matrix as an intrinsic uncertainty measure.Quantum-Neural Bandit (Q-Neural) combines quantum feature extraction with a classical neural network for context-aware decisions.Experiments on data from the ChEMBL database demonstrate that while classical linear methods achieve the lowest mean regret, the quantum methods excel in stability, near-optimal performance, and interpretability-unique advantages that are critical for reliable drug discovery.This work establishes quantum combinatorial bandits as a versatile tool offering benefits beyond raw regret minimization.
Stochastic contextual bandits are fundamental for sequential decision-making but pose significant challenges for existing neural network-based algorithms, particularly when scaling to quantum neural networks (QNNs) due to issues such as massive over-parameterization, computational instability, and the barren plateau phenomenon. This paper introduces the Quantum Neural Tangent Kernel-Upper Confidence Bound (QNTK-UCB) algorithm, a novel algorithm that leverages the Quantum Neural Tangent Kernel (QNTK) to address these limitations.
By freezing the QNN at a random initialization and utilizing its static QNTK as a kernel for ridge regression, QNTK-UCB bypasses the unstable training dynamics inherent in explicit parameterized quantum circuit training while fully exploiting the unique quantum inductive bias. For a time horizon T and K actions, our theoretical analysis reveals a significantly improved parameter scaling of Ω((TK)3) for QNTK-UCB, a substantial reduction compared to Ω((TK)8) required by classical NeuralUCB algorithms for similar regret guarantees. Empirical evaluations on non-linear synthetic benchmarks and quantum-native variational quantum eigensolver tasks demonstrate QNTK-UCB's superior sample efficiency in low-data regimes. This work highlights how the inherent properties of QNTK provide implicit regularization and a sharper spectral decay, paving the way for achieving ``quantum advantage'' in online learning.
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.
We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle, which has been successfully applied in many critical applications such as drug discovery and materials design. Existing works have showed that with the aid of quantum computing, it is possible to break the classical Ω(T) regret lower bound and achieve the new O(polylogT) upper bound. However, they usually assume that the objective function sits within the reproducing kernel Hilbert space and their algorithms suffer from the curse of dimensionality. In this paper, we propose the new Q-NLB-UCB algorithm which enjoys an \emph{input dimension-free} O(polylogT) upper bound, making it applicable for high-dimensional tasks. At the heart of our algorithm design are quantum Monte Carlo mean estimator, parametric function approximation technique, and a new quantum non-linear regression oracle, which can be of independent interests in more quantum machine learning problems. Our algorithm is also validated for its efficiency compared with other quantum algorithms on both high-dimensional synthetic and real-world tasks.
We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle, which has been successfully applied in many critical applications such as drug discovery and materials design. Existing works have showed that with the aid of quantum computing, it is possible to break the classical Ω(√T) regret lower bound and achieve the new O(poly log T) upper bound. However, they usually assume that the objective function sits within the reproducing kernel Hilbert space and their algorithms suffer from the curse of dimensionality. In this paper, we propose the new Q-NLB-UCB algorithm which enjoys an input dimension-free O(poly log T) upper bound, making it applicable for high-dimensional tasks. At the heart of our algorithm design are quantum Monte Carlo mean estimator, parametric function approximation technique, and a new quantum non-linear regression oracle, which can be of independent interests in more quantum machine learning problems. Our algorithm is also validated for its efficiency compared with other quantum algorithms on both high-dimensional synthetic and real-world tasks.
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.
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.