We explore whether quantum advantages can be found for the zeroth-order feedback online exp-concave optimization problem, which is also known as bandit exp-concave optimization with multi-point feedback. We present quantum online quasi-Newton methods to tackle the problem and show that there exists quantum advantages for such problems. Our method approximates the Hessian by quantum estimated inexact gradient and can achieve $O(n\log T)$ regret with $O(1)$ queries at each round, where $n$ is the dimension of the decision set and $T$ is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of $T^{2/3}$.
We explore whether quantum advantages can be found for the zeroth-order feedback online exp-concave optimization problem, which is also known as bandit exp-concave optimization with multi-point feedback. We present quantum online quasi-Newton methods to tackle the problem and show that there exists quantum advantages for such problems. Our method approximates the Hessian by quantum estimated inexact gradient and can achieve O(nlogT) regret with O(1) queries at each round, where n is the dimension of the decision set and T is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of T2/3.
Abstract We explore whether quantum advantages can be found for the zeroth-order online convex optimization (OCO) problem, which is also known as bandit convex optimization with multi-point feedback. In this setting, given access to zeroth-order oracles (that is, the loss function is accessed as a black box that returns the function value for any queried input), a player attempts to minimize a sequence of adversarially generated convex loss functions. This procedure can be described as a T round iterative game between the player and the adversary. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible for problems of OCO. Specifically, our contributions are as follows. (i) When the player is allowed to query zeroth-order oracles O (1) times in each round as feedback, we give a quantum algorithm that achieves O ( T ) regret without additional dependence of the dimension n , which outperforms the already known optimal classical algorithm only achieving O ( n T ) regret. Note that the regret of our quantum algorithm has achieved the lower bound of classical first-order methods. (ii) We show that for strongly convex loss functions, the quantum algorithm can achieve O (log T ) regret with O (1) queries as well, which means that the quantum algorithm can achieve the same regret bound as the classical algorithms in the full information setting.
As a fundamental tool in AI, convex optimization has been a significant research field for many years, and the same goes for its online version. Recently, general convex optimization problem has been accelerated with the help of quantum computing, and the technique of online convex optimization has been used for accelerating the online quantum state learning problem, thus we want to study whether online convex optimization (OCO) model can also be benefited from quantum computing. In this paper, we consider the OCO model, which can be described as a T round iterative game between the player and the adversary. A key factor for measuring the performance of an OCO algorithm A is the regret denoted by regretT(A), and it is said to perform well if its regret is sublinear as a function of T. Another factor is the computational cost (e.g., query complexity) of the algorithm. We give a quantum algorithm for the online convex optimization model with only zeroth-order oracle available, which can achieve O(T) and O(logT) regret for general convex loss functions and α-strong loss functions respectively, where only O(1) queries are needed in each round. Our results show that the zeroth-order quantum oracle is as powerful as the classical first-order oracle, and show potential advantages of quantum computing over classical computing in the OCO model where only zeroth-order oracle available.
We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set K⊆Rn and a function F:Rn→R such that there exists a convex function f:K→R satisfying supx∈K∣F(x)−f(x)∣≤ε/n, our quantum algorithm finds an x∗∈K such that F(x∗)−minx∈KF(x)≤ε using O~(n3) quantum evaluation queries to F. This achieves a polynomial quantum speedup compared to the best-known classical algorithms. As an application, we give a quantum algorithm for zeroth-order stochastic convex bandits with O~(n5log2T) regret, an exponential speedup in T compared to the classical Ω(T) lower bound. Technically, we achieve quantum speedup in n by exploiting a quantum framework of simulated annealing and adopting a quantum version of the hit-and-run walk. Our speedup in T for zeroth-order stochastic convex bandits is due to a quadratic quantum speedup in multiplicative error of mean estimation.
Given a convex function f:Rd→R, the problem of sampling from a distribution ∝e−f(x) is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants ∫Rde−f(x)dx. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number κ and dimension d) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error ε. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity O(κ1/2d) and O(κ1/2d3/2/ε) for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in κ,d,ε over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a 1/ε1−o(1) quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in ε.
We study the problem of online learning of quantum states with logarithmic loss, which is a quantum generalization of online portfolio selection and has applications to quantum state tomography, the task of estimating an unknown quantum state from measurement outcomes. We first establish a regret lower bound, showing that the regret rates of Exponential Weights and the algorithm of Tseng et al. (2025) have optimal polynomial dependence on the dimension. Our analysis leads to two further results. First, our lower-bound proof leads to a quantum state tomography algorithm that is sample optimal up to polylogarithmic factors in the sample size. Second, we develop an algorithm for constructing confidence sequences for the mean of a matrix-valued random variable. A numerical experiment shows that the latter algorithm is competitive with existing methods.
Bandits with knapsacks (BwK) constitute a fundamental model that combines aspects of stochastic integer programming with online learning. Classical algorithms for BwK with a time horizon T achieve a problem-independent regret bound of O(T) and a problem-dependent bound of O(logT). In this paper, we initiate the study of the BwK model in the setting of quantum computing, where both reward and resource consumption can be accessed via quantum oracles. We establish both problem-independent and problem-dependent regret bounds for quantum BwK algorithms. For the problem-independent case, we demonstrate that a quantum approach can improve the classical regret bound by a factor of (1+B/OPTLP), where B is budget constraint in BwK and OPTLP denotes the optimal value of a linear programming relaxation of the BwK problem. For the problem-dependent setting, we develop a quantum algorithm using an inexact quantum linear programming solver. This algorithm achieves a quadratic improvement in terms of the problem-dependent parameters, as well as a polynomial speedup of time complexity on problem's dimensions compared to classical counterparts. Compared to previous works on quantum algorithms for multi-armed bandits, our study is the first to consider bandit models with resource constraints and hence shed light on operations research.