Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Online Convex Optimization with Classical and Quantum Evaluation Oracles

Jianhao He, Feidiao Yang, Jialin Zhang, Lvzhou Li

Published Jul 29, 2020• 1 citation
OpenAlex

Abstract

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 ${\cal A}$ is the regret denoted by $\text{regret}_{T}(\mathcal{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(\sqrt{T})$ and $O(\log{T})$ regret for general convex loss functions and $\alpha$-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.

Related papers

Quantum algorithm for online convex optimization

Jianhao He, Feidiao Yang, Jialin Zhang +1 more

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.

arXiv:2007.15046•Quantum Science and Technology•Feb 28, 2022•3 citations

Quantum Algorithm for Online Exp-concave Optimization

Jianhao He, Chengchang Liu, Xutong Liu +2 more

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}$.

arXiv:2410.19688•Oct 25, 2024•0 citations

Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits

Tongyang Li, Ruizhe Zhang

We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set ${\cal K}\subseteq\mathbb{R}^{n}$ and a function $F\colon\mathbb{R}^{n}\to\mathbb{R}$ such that there exists a convex function $f\colon\mathcal{K}\to\mathbb{R}$ satisfying $\sup_{x\in{\cal K}}|F(x)-f(x)|\leq ε/n$, our quantum algorithm finds an $x^{*}\in{\cal K}$ such that $F(x^{*})-\min_{x\in{\cal K}} F(x)\leqε$ using $\tilde{O}(n^{3})$ 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 $\tilde{O}(n^{5}\log^{2} T)$ regret, an exponential speedup in $T$ compared to the classical $Ω(\sqrt{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.

arXiv:2209.12897•neural information processing systems•Jan 1, 2022•1 citation

Quantum algorithms and lower bounds for convex optimization

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li +1 more

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.

arXiv:1809.01731•Quantum•Jan 13, 2020•43 citations

Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss

Hao Wang, Zhang, Chenyi, Tongyang Li

The problem of minimizing the maximum of $N$ convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring $O(Nε^{-2/3} + ε^{-8/3})$ queries to a first-order oracle to compute an $ε$-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of $\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})$. On the other hand, we prove that quantum algorithms must take $\tildeΩ(\sqrt{N}ε^{-2/3})$ queries to a first order quantum oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic factors.

arXiv:2402.12745•Feb 20, 2024•0 citations

Convex optimization using quantum oracles

Joran van Apeldoorn, András Gilyén, Sander Gribling +1 more

We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.

arXiv:1809.00643•Quantum•Jan 13, 2020•35 citations
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 TTT round iterative game between the player and the adversary. A key factor for measuring the performance of an OCO algorithm A{\cal A}A is the regret denoted by regretT(A)\text{regret}_{T}(\mathcal{A})regretT​(A), and it is said to perform well if its regret is sublinear as a function of TTT. 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)O(\sqrt{T})O(T​) and O(log⁡T)O(\log{T})O(logT) regret for general convex loss functions and α\alphaα-strong loss functions respectively, where only O(1)O(1)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.
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.
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(nlog⁡T)O(n\log T)O(nlogT) regret with O(1)O(1)O(1) queries at each round, where nnn is the dimension of the decision set and TTT is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of T2/3T^{2/3}T2/3.
We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set K⊆Rn{\cal K}\subseteq\mathbb{R}^{n}K⊆Rn and a function F ⁣:Rn→RF\colon\mathbb{R}^{n}\to\mathbb{R}F:Rn→R such that there exists a convex function f ⁣:K→Rf\colon\mathcal{K}\to\mathbb{R}f:K→R satisfying sup⁡x∈K∣F(x)−f(x)∣≤ε/n\sup_{x\in{\cal K}}|F(x)-f(x)|\leq ε/nsupx∈K​∣F(x)−f(x)∣≤ε/n, our quantum algorithm finds an x∗∈Kx^{*}\in{\cal K}x∗∈K such that F(x∗)−min⁡x∈KF(x)≤εF(x^{*})-\min_{x\in{\cal K}} F(x)\leqεF(x∗)−minx∈K​F(x)≤ε using O~(n3)\tilde{O}(n^{3})O~(n3) quantum evaluation queries to FFF. 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~(n5log⁡2T)\tilde{O}(n^{5}\log^{2} T)O~(n5log2T) regret, an exponential speedup in TTT compared to the classical Ω(T)Ω(\sqrt{T})Ω(T​) lower bound. Technically, we achieve quantum speedup in nnn by exploiting a quantum framework of simulated annealing and adopting a quantum version of the hit-and-run walk. Our speedup in TTT for zeroth-order stochastic convex bandits is due to a quadratic quantum speedup in multiplicative error of mean estimation.
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.
The problem of minimizing the maximum of NNN convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nε−2/3+ε−8/3)O(Nε^{-2/3} + ε^{-8/3})O(Nε−2/3+ε−8/3) queries to a first-order oracle to compute an εεε-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of NNN convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O~(Nε−5/3+ε−8/3)\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})O~(N​ε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3)\tildeΩ(\sqrt{N}ε^{-2/3})Ω~(N​ε−2/3) queries to a first order quantum oracle, showing that our dependence on NNN is optimal up to poly-logarithmic factors.
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.