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

arXiv:2406.03006

Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

Yexin Zhang, Zhang, Chenyi, Cong Fang, Liwei Wang, Tongyang Li

Published Jun 5, 2024• 3 citations
arXivHTMLPDF

Abstract

Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let $f_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $ψ\colon\mathbb{R}^d\to\mathbb{R}$ be a $μ$-strongly convex proximal function. The goal is to find an $ε$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tildeΘ\big(n+\sqrt{n\ell/μ}\big)$. We also prove a quantum lower bound $\tildeΩ(n+n^{3/4}(\ell/μ)^{1/4})$ when $d$ is large enough. Both our quantum upper and lower bounds can extend to the cases where $ψ$ is not necessarily strongly convex, or each $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $ε$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)$ queries.

DOI
10.48550/arxiv.2406.03006

Related papers

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•1 citation

Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions

Zhang, Chenyi, Tongyang Li

Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for nonconvex optimization are still widely open. In this paper, we conduct a systematic study of quantum query lower bounds on finding $ε$-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to $p$-th order derivatives; or 2) having access to stochastic gradients. The classical query lower bounds is $Ω\big(ε^{-\frac{1+p}{p}}\big)$ regarding the first setting, and $Ω(ε^{-4})$ regarding the second setting (or $Ω(ε^{-3})$ if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding $ε$-stationary points of nonconvex functions with $p$-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, our quantum lower bounds are obtained by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially.

arXiv:2212.03906•Dec 7, 2022•9 citations

Continuous optimization

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers applications of quantum computing in the area of continuous optimization, including both convex and nonconvex optimization. We discuss quantum algorithms for computing Nash equilibria for zero-sum games and for solving linear, second-order, and semidefinite programs. These algorithms are based on quantum implementations of the multiplicative weights update method or interior point methods. We also discuss general quantum algorithms for convex optimization which can provide a speedup in cases where the objective function is much easier to evaluate than the gradient of the objective function. Finally, we cover quantum algorithms for escaping saddle points and finding local minima in nonconvex optimization problems.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Improved Quantum Lower and Upper Bounds for Matrix Scaling

Sander Gribling, Harold A. Nieuwboer

Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for $n \times n$ matrices with at most $m$ non-zero entries and with $\ell_2$-error $\varepsilon=\widetildeΘ(1/m)$ must make $\widetildeΩ(m)$ queries to the matrix, even when the success probability is exponentially small in $n$. Additionally, we show that for $\varepsilon\in[1/n,1/2]$, any quantum algorithm capable of producing $\frac{\varepsilon}{100}$-$\ell_1$-approximations of the row-sum vector of a (dense) normalized matrix uses $Ω(n/\varepsilon)$ queries, and that there exists a constant $\varepsilon_0>0$ for which this problem takes $Ω(n^{1.5})$ queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-$\varepsilon$ regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an $\varepsilon$-$\ell_1$-scaling in time $\widetilde O(n^{1.5}/\varepsilon^2)$, whereas the best previously known bounds were $\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))$ (classical) and $\widetilde O(n^{1.5}/\varepsilon^3)$ (quantum).

arXiv:2109.15282•Leibniz international proceedings in informatics•Sep 30, 2021•7 citations

Linear regression by quantum amplitude estimation and its extension to convex optimization

Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda +1 more

Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ${N}_{D}$. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ${N}_{D}$, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.

arXiv:2105.13511•Physical Review A•Aug 25, 2021•9 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•6 citations
Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let f1,…,fn ⁣:Rd→Rf_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}f1​,…,fn​:Rd→R be ℓ\ellℓ-smooth convex functions and ψ ⁣:Rd→Rψ\colon\mathbb{R}^d\to\mathbb{R}ψ:Rd→R be a μμμ-strongly convex proximal function. The goal is to find an εεε-optimal point for F(x)=1n∑i=1nfi(x)+ψ(x)F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})F(x)=n1​∑i=1n​fi​(x)+ψ(x). We give a quantum algorithm with complexity O~(n+d+ℓ/μ(n1/3d1/3+n−2/3d5/6))\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)O~(n+d​+ℓ/μ​(n1/3d1/3+n−2/3d5/6)), improving the classical tight bound Θ~(n+nℓ/μ)\tildeΘ\big(n+\sqrt{n\ell/μ}\big)Θ~(n+nℓ/μ​). We also prove a quantum lower bound Ω~(n+n3/4(ℓ/μ)1/4)\tildeΩ(n+n^{3/4}(\ell/μ)^{1/4})Ω~(n+n3/4(ℓ/μ)1/4) when ddd is large enough. Both our quantum upper and lower bounds can extend to the cases where ψψψ is not necessarily strongly convex, or each fif_ifi​ is Lipschitz but not necessarily smooth. In addition, when FFF is nonconvex, our quantum algorithm can find an εεε-critial point using O~(n+ℓ(d1/3n1/3+d)/ε2)\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)O~(n+ℓ(d1/3n1/3+d​)/ε2) 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.
Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quantum lower bounds for convex optimization, quantum lower bounds for nonconvex optimization are still widely open. In this paper, we conduct a systematic study of quantum query lower bounds on finding εεε-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to ppp-th order derivatives; or 2) having access to stochastic gradients. The classical query lower bounds is Ω(ε−1+pp)Ω\big(ε^{-\frac{1+p}{p}}\big)Ω(ε−p1+p​) regarding the first setting, and Ω(ε−4)Ω(ε^{-4})Ω(ε−4) regarding the second setting (or Ω(ε−3)Ω(ε^{-3})Ω(ε−3) if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding εεε-stationary points of nonconvex functions with ppp-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, our quantum lower bounds are obtained by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially.
This chapter covers applications of quantum computing in the area of continuous optimization, including both convex and nonconvex optimization. We discuss quantum algorithms for computing Nash equilibria for zero-sum games and for solving linear, second-order, and semidefinite programs. These algorithms are based on quantum implementations of the multiplicative weights update method or interior point methods. We also discuss general quantum algorithms for convex optimization which can provide a speedup in cases where the objective function is much easier to evaluate than the gradient of the objective function. Finally, we cover quantum algorithms for escaping saddle points and finding local minima in nonconvex optimization problems.
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for n×nn \times nn×n matrices with at most mmm non-zero entries and with ℓ2\ell_2ℓ2​-error ε=Θ~(1/m)\varepsilon=\widetildeΘ(1/m)ε=Θ(1/m) must make Ω~(m)\widetildeΩ(m)Ω(m) queries to the matrix, even when the success probability is exponentially small in nnn. Additionally, we show that for ε∈[1/n,1/2]\varepsilon\in[1/n,1/2]ε∈[1/n,1/2], any quantum algorithm capable of producing ε100\frac{\varepsilon}{100}100ε​-ℓ1\ell_1ℓ1​-approximations of the row-sum vector of a (dense) normalized matrix uses Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) queries, and that there exists a constant ε0>0\varepsilon_0>0ε0​>0 for which this problem takes Ω(n1.5)Ω(n^{1.5})Ω(n1.5) queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-ε\varepsilonε regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an ε\varepsilonε-ℓ1\ell_1ℓ1​-scaling in time O~(n1.5/ε2)\widetilde O(n^{1.5}/\varepsilon^2)O(n1.5/ε2), whereas the best previously known bounds were O~(n2polylog(1/ε))\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))O(n2polylog(1/ε)) (classical) and O~(n1.5/ε3)\widetilde O(n^{1.5}/\varepsilon^3)O(n1.5/ε3) (quantum).
Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ND{N}_{D}ND​. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ND{N}_{D}ND​, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.
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.