Robustness of Quantum Algorithms for Nonconvex Optimization

## Abstract

Abstract Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimization algorithms is their robustness against experimental and statistical noises. In this paper, we systematically study quantum algorithms for finding an ϵ italic-ϵ \epsilon -approximate second-order stationary point ( ϵ italic-ϵ \epsilon -SOSP) of a d 𝑑 d -dimensional nonconvex function, a fundamental problem in nonconvex optimization, with noisy zeroth- or first-order oracles as inputs. We first prove that, up to noise of O ​ ( ϵ 10 / d 5 ) 𝑂 superscript italic-ϵ 10 superscript 𝑑 5 O(\epsilon^{10}/d^{5}) , accelerated perturbed gradient descent equipped with quantum gradient estimation takes O ​ ( log ⁡ d / ϵ 1.75 ) 𝑂 𝑑 superscript italic-ϵ 1.75 O(\log d/\epsilon^{1.75}) quantum queries to find an ϵ italic-ϵ \epsilon -SOSP. We then prove that standard perturbed gradient descent is robust to the noise of O ​ ( ϵ 6 / d 4 ) 𝑂 superscript italic-ϵ 6 superscript 𝑑 4 O(\epsilon^{6}/d^{4}) and O ​ ( ϵ / d 0.5 + ζ ) 𝑂 italic-ϵ superscript 𝑑 0.5 𝜁 O(\epsilon/d^{0.5+\zeta}) for ζ > 0 𝜁 0 \zeta>0 on the zeroth- and first-order oracles, respectively, which provides a quantum algorithm with poly-logarithmic query complexity. We then propose a stochastic gradient descent algorithm using quantum mean estimation on the Gaussian smoothing of noisy oracles, which is robust to O ​ ( ϵ 1.5 / d ) 𝑂 superscript italic-ϵ 1.5 𝑑 O(\epsilon^{1.5}/d) and O ​ ( ϵ / d ) 𝑂 italic-ϵ 𝑑 O(\epsilon/\sqrt{d}) noise on the zeroth- and first-order oracles, respectively. The quantum algorithm takes O ​ ( d 2.5 / ϵ 3.5 ) 𝑂 superscript 𝑑 2.5 superscript italic-ϵ 3.5 O(d^{2.5}/\epsilon^{3.5}) and O ​ ( d 2 / ϵ 3 ) 𝑂 superscript 𝑑 2 superscript italic-ϵ 3 O(d^{2}/\epsilon^{3}) queries to the two oracles, giving a polynomial speedup over the classical counterparts. As a complement, we characterize the domains where quantum algorithms can find an ϵ italic-ϵ \epsilon -SOSP with poly-logarithmic, polynomial, or exponential number of queries in d 𝑑 d , or the problem is information-theoretically unsolvable even with an infinite number of queries. In addition, we prove an Ω ​ ( ϵ − 12 / 7 ) Ω superscript italic-ϵ 12 7 \Omega(\epsilon^{-12/7}) lower bound on ϵ italic-ϵ \epsilon for any randomized classical and quantum algorithm to find an ϵ italic-ϵ \epsilon -SOSP using either noisy zeroth- or first-order oracles. As far as we know, this is the first quantum lower bound in ϵ italic-ϵ \epsilon for finding ϵ italic-ϵ \epsilon -approximate second-order stationary points in nonconvex optimization.

## 1 Introduction

Optimization theory is a central topic in computer science and applied mathematics, with wide applications in machine learning, operations research, statistics, and many other areas.
Currently, various quantum algorithms for optimization have been proposed, ranging from linear programs [, ] and semidefinite programs [, , , ] to general convex optimization [, ] and nonconvex optimization [, ].

A crucial factor of quantum optimization algorithms is their robustness. On the one hand, current quantum applications suffer from noises generated by near-term quantum devices [], which may create adversarial perturbations in the worst-case that result in disastrous failures. To deal with this issue, some (elements of) quantum algorithms, such as some adiabatic quantum algorithms [], quantum gates [], and machine learning algorithms [, , ], are robustness against experimental noises or noisy quantum queries []. An alternative solution is to develop error correction [] or error mitigation [, ] mechanisms to reduce the influences of experimental noises. In the context of nonconvex optimization, developing robust quantum algorithms is essential for future practical implementations of these algorithms on near-term devices.

On the other hand, robustness is a natural and crucial requirement for solving classical optimization problems. For instance, statistical machine learning, which is a widely explored task, concerns the problem with data generated from an underlying probability distribution $\mathcal{D}$ (i.e., population), and optimizes the objective function (i.e., population risk) $F$ defined by the expectation:

$$ $\displaystyle F(\theta)=\mathbb{E}_{\mathbf{z}\sim\mathcal{D}}[L(\theta;\mathbf{z})],$ (1) $$

where the expectation is averaged over all possible continuous loss functions $\{L(\cdot\,;\mathbf{z})\}$ with $\mathbf{z}\sim\mathcal{D}$. The optimization algorithm does not access $F$ directly but can take queries to the empirical risk function $f(\theta)=\sum_{i=1}^{n}L(\theta;\mathbf{z}_{i})/n$ via querying the loss function values at $L$ sample points. The optimization of $F$ given access to the empirical risk $f$ is known as the *empirical risk minimization* [, , ].
Under this setting, the noisy evaluation of $F$ can be poorly behaved – it might have exponentially many shallow local minima even if $F$ has a good landscape and satisfies smoothness or Lipschitz assumptions [, ].

To analyze the problem of nonconvex optimization using noisy queries, previous literature on classical optimization (see e.g. [, ]) assumed that $f$ and $F$ are pointwise close to each other:

$$ $\displaystyle\|F-f\|_{\infty}\leq\nu,$ (2) $$

where the error $\nu$ usually decays with the number of samples. Under this assumption, $f$ may still be non-smooth and contain additional shallow local minima independent of $F$. Nevertheless, it is possible to exploit the pointwise closeness between $f$ and $F$ to escape from highly suboptimal local minima that only exist in $f$ and find an approximate local minimum of $F$.

Another nonconvex optimization model using noisy queries is to find local minima of $F$ with empirical first-order information []. Similar to ([2](#S1.E2)), we query a stochastic gradient $\nabla f$ uniformly close to the actual gradient $\nabla F$. This model is widely considered in stochastic scenarios where we evaluate the gradient information using a sampling procedure to zeroth-order function values. A well-known example is the *stochastic gradient descent* [, ],
where we obtain an approximated gradient value by sampling mini-batch function values. As the mini-batch size $m$ increases, the gradient evaluation converges to the actual gradient with high probability:

$$ $\displaystyle\norm{\nabla F-\nabla f}_{\infty}\leq\tilde{\nu},$ (3) $$

where the error $\tilde{\nu}$ typically decreases with the mini-batch size $m$. Here, $\norm{\nabla F-\nabla f}_{\infty}$ take the maximal value of the infinity-norm taken both over the input $\mathbf{x}$ and the $d$ different entries of the gradient at the $\mathbf{x}$.

Various approaches have been developed to investigate the robustness of optimization algorithms from different perspectives [, , , , , , , ]. In the context of convex optimization, Ref. [] proposed an algorithm for finding an $\epsilon$-approximate global minimum of an approximate convex function, where $\epsilon$ is the precision guarantee for the optimization output (see [Assumption 1](#Thmassumption1) and [Assumption 2](#Thmassumption2) for the formal definition). This algorithm requires $\tilde{O}(d^{7.5}/\epsilon^{2})$(^1^11The $\tilde{O}$ notation omits poly-logarithmic terms, i.e., $\tilde{O}(g)=O(g\operatorname{poly}(\log g))$.) queries to the stochastic noisy function evaluation oracle, which has zero-mean and sub-Gaussian distributed noise. Very recently, Ref. [] improved this result by proposing a quantum algorithm with query complexity $\tilde{O}(d^{5}/\epsilon)$ for the same task, giving a polynomial quantum speedup compared to the classical counterpart. In addition, Ref. [] proposed an information-theoretic lower bound for any convex optimization algorithms to find minima within $\epsilon$ multiplicative error using noisy function evaluation oracles. In Ref. [], an algorithm with optimal dependence on $d$ was proposed to find an $\epsilon$-approximate minimum taking queries to noisy function evaluation oracles.

In the context of nonconvex optimization, Refs. [, ] considered querying oracles with bounded noise $\nu\leq O(\epsilon^{2}/d^{8})$, where $\epsilon$ is the precision and $d$ is the dimension of $F$. This work developed an efficient classical algorithm to escape from the noise-induced “shallow” local minima using simulated annealing and stochastic gradient Langevin dynamics (SGLD). More recently, improved polynomial algorithms to solve the nonconvex optimization problem with bounded noise of $O(\epsilon^{1.5}/d)$ and $O(\epsilon/\sqrt{d})$ using zeroth- and first- order noisy oracles were obtained in Ref. []. Ref. [] further discussed the noise threshold to guarantee the existence of polynomial-query classical algorithms for finding an $\epsilon$-approximate local minimum of $F$. In contrast, little has been known about the influence of noises on quantum algorithms for general nonconvex optimization problems, upon which this paper systematically investigates.

### 1.1 Nonconvex Optimization with Noisy Oracle

We consider the nonconvex optimization problem with a twice-differentiable target function $F\colon\mathbb{R}^{d}\to\mathbb{R}$ satisfying

- •
$F$ is $B$-bounded: $\sup_{\mathbf{x}\in\mathbb{R}^{d}}\absolutevalue{F(\mathbf{x})}\leq B$;
- •
$F$ is $\ell$-smooth ($\ell$-gradient Lipschitz): $\norm{\nabla F(\mathbf{x}_{1})-\nabla F(\mathbf{x}_{2})}\leq\ell\norm{\mathbf{x}_{1}-\mathbf{x}_{2}},\quad\forall\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{R}^{d}$;
- •
$F$ is $\rho$-Hessian Lipshitz: $\norm{\nabla^{2}F(\mathbf{x}_{1})-\nabla^{2}F(\mathbf{x}_{2})}\leq\rho\norm{\mathbf{x}_{1}-\mathbf{x}_{2}},\quad\forall\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{R}^{d}$.

The goal is to find an $\epsilon$-approximate second order stationary point ($\epsilon$-SOSP)(^2^22A more general target is to find an $(\epsilon,\gamma)$-SOSP $\mathbf{x}$ such that $\norm{F(\mathbf{x})}\leq\epsilon$ and $\lambda_{\min}(\nabla^{2}F(\mathbf{x}))\geq-\gamma$. The definition of an $\epsilon$-SOSP in ([4](#S1.E4)) was proposed first by Ref. [] and has been taken as a standard assumption in the subsequent papers [, , , , , , , , , ].) such that

$$ $\displaystyle\norm{F(\mathbf{x})}\leq\epsilon,\qquad\lambda_{\min}(\nabla^{2}F(\mathbf{x}))\geq-\sqrt{\rho\epsilon}.$ (4) $$

Instead of directly querying $F$, we assume one can access a noisy function $f$ that is pointwise close to $F$.

###### Assumption 1 (Noisy evaluation query) .

The target function $F$ is $B$-bounded, $\ell$-smooth, and $\rho$-Hessian Lipschitz, and we can query a noisy function $f$ that is $\nu$-pointwise close to $F$:

$$ $\displaystyle\norm{F-f}_{\infty}\leq\nu.$ (5) $$

We further consider finding an $\epsilon$-SOSP of $F$ given an alternative condition that the gradient $\nabla f$ of function $f$ is pointwise close to $\nabla F$.

###### Assumption 2 (Noisy gradient query) .

The target function $F$ is $B$-bounded, $\ell$-smooth, and $\rho$-Hessian Lipschitz, and we can query the gradient $\mathbf{g}\coloneqq\nabla f$ of an $L$-smooth function $f$. The gradient $\mathbf{g}$ is pointwise close to gradient of $F$:

$$ $\displaystyle\norm{\nabla F-\nabla f}_{\infty}\leq\tilde{\nu}.$ (6) $$

In the quantum context, the oracles are unitary operators rather than classical procedures. Under [Assumption 1](#Thmassumption1), one can query a quantum evaluation oracle (quantum zeroth-order oracle) $U_{f}$, which can be represented as

$$ $\displaystyle U_{f}(\ket{\mathbf{x}}\otimes\ket{0})\to\ket{\mathbf{x}}\otimes\ket{f(\mathbf{x})},\qquad\forall\mathbf{x}\in\mathbb{R}^{d}.$ (7) $$

Furthermore, quantum oracles allow coherent superpositions of queries. Given $m$ vectors $\ket{\mathbf{x}_{1}},\ldots,$ $\ket{\mathbf{x}_{m}}\in\mathbb{R}^{d}$ and a coefficient vector $\mathbf{c}\in\mathbb{C}^{m}$ such that $\sum_{i=1}^{m}\absolutevalue{\mathbf{c}_{i}}^{2}=1$, the quantum oracle outputs $U_{f}(\sum_{i=1}^{m}\mathbf{c}_{i}\ket{\mathbf{x}_{i}}\otimes\ket{0})\to\sum_{i=1}^{m}\mathbf{c}_{i}\ket{\mathbf{x}_{i}}\otimes\ket{f(\mathbf{x}_{i})}$. Compared to the classical evaluation oracle, the ability to query different locations simultaneously in superposition is the essence of quantum speedup. In addition, if a classical oracle can be implemented by a classical circuit, the corresponding quantum oracle can be implemented by a quantum circuit of the same size.

Similarly, in the first-order scenario we assume that one can access the quantum gradient oracle $U_{\mathbf{g}}$ under [Assumption 2](#Thmassumption2),
which can be represented as

$$ $\displaystyle U_{\mathbf{g}}(\ket{\mathbf{x}}\otimes\ket{\mathbf{0}})\to\ket{\mathbf{x}}\otimes\ket{\nabla f(\mathbf{x})},\qquad\forall\mathbf{x}\in\mathbb{R}^{d}.$ (8) $$

###### Assumption 1 (Noisy evaluation query) .

###### Assumption 2 (Noisy gradient query) .

### 1.2 Contributions

In this paper, we conduct a systematic study of quantum algorithms for nonconvex optimization using noisy oracles. Using zeroth- or first-order oracles as inputs, we rigorously characterize different domains where quantum algorithms can find an $\epsilon$-SOSP using poly-logarithmic, polynomial, or exponential number of queries, respectively. We also identify the domain where it is information-theoretically unsolvable to find an $\epsilon$-SOSP even using an infinite number of queries.

In some of the domains, we further develop lower bounds on the query complexity for any classical algorithms and propose quantum algorithms with polynomial or exponential speedups compared to either the classical lower bounds or the complexities of corresponding state-of-the-art classical algorithms. We summarize our main results under [Assumption 1](#Thmassumption1) and [Assumption 2](#Thmassumption2) in [Table 1](#S1.T1) and [Table 2](#S1.T2), respectively.

**Table 1: A summary of our results and comparisons with the state-of-the-art classical upper and lower bounds under [Assumption 1](#Thmassumption1). The query complexities are highlighted in terms of the dimension $d$ and the precision $\epsilon$. ($*$) In the last row, we can obtain the desired classical lower bound and thus an exponential speedup in the query complexity when $\nu=\tilde{\Omega}(\operatorname{poly}(1/d,\epsilon))$ as [Theorem 7](#Thmtheorem7) works for $\nu=\tilde{\Omega}(\operatorname{poly}(1/d,\epsilon))$.**
| Noise Strength | Classical Bounds | Quantum Bounds | Speedup in $d$ |
| --- | --- | --- | --- |
| $\nu=\Omega(\epsilon^{1.5})$ | Unsolvable [] | Unsolvable ([Theorem 6](#Thmtheorem6)) | N/A |
| $\nu=O(\epsilon^{1.5})$, $\nu=\tilde{\Omega}(\epsilon^{1.5}/d)$ | $O(\exp(d))$, $\Omega(d^{\log d})$ [] | $\Omega(d^{\log d})$ ([Theorem 5](#Thmtheorem5)) | N/A |
| $\nu=O(\epsilon^{1.5}/d)$, $\nu=\tilde{\Omega}(\epsilon^{6}/d^{4})$ | $\tilde{O}(d^{4}/\epsilon^{5})$ [, ] | $\tilde{O}(d^{2.5}/\epsilon^{3.5})$ ([Theorem 3](#Thmtheorem3)) | Polynomial |
| $\nu=\tilde{O}(\epsilon^{6}/d^{4})$, $\nu=\tilde{\Omega}(\epsilon^{10}/d^{5})$ | $\Omega(d/\log d)$ ([Theorem 7](#Thmtheorem7)) | $O(\log^{4}d/\epsilon^{2})$ ([Theorem 2](#Thmtheorem2)) | Exponential |
| $\nu=\tilde{O}(\epsilon^{10}/d^{5})$ | $\Omega(d/\log d)^{*}$ ([Theorem 7](#Thmtheorem7)) | $O(\log d/\epsilon^{1.75})$ ([Theorem 1](#Thmtheorem1)) | Exponential^∗ |

**Table 2: A summary of our results and comparisons with the state-of-the-art classical upper and lower bounds under [Assumption 2](#Thmassumption2). In the last line, $\zeta>0$ and $\zeta=\Omega(1/\log(d))$ (for instance, this is satisfied for any constant $\zeta>0$).**
| Noise Strength | Classical Bounds | Quantum Bounds | Speedup in $d$ |
| --- | --- | --- | --- |
| $\tilde{\nu}=\Omega(\epsilon)$ | Unsolvable ([Theorem 8](#Thmtheorem8)) | Unsolvable ([Theorem 8](#Thmtheorem8)) | N/A |
| $\tilde{\nu}=O(\epsilon)$, $\tilde{\nu}=\tilde{\Omega}(\epsilon/d^{0.5})$ | $\Omega(d^{\log d})$ ([Theorem 8](#Thmtheorem8)) | $\Omega(d^{\log d})$ ([Theorem 8](#Thmtheorem8)) | N/A |
| $\tilde{\nu}=\Theta(\epsilon/d^{0.5})$ | $O(d^{3}/\epsilon^{4})$ [] | $O(d^{2}/\epsilon^{3})$ ([Theorem 4](#Thmtheorem4)) | Polynomial |
| $\tilde{\nu}=O(\epsilon/d^{0.5+\zeta})$ | $O(\log^{4}d/\epsilon^{2})$ ([Corollary 1](#Thmcorollary1)) | $O(\log^{4}d/\epsilon^{2})$ ([Corollary 1](#Thmcorollary1)) | No |

#### 1.2.1 Upper bounds

##### Tiny noise: robustness of perturbed accelerated gradient descent.

We start by adding tiny noise to the oracles in quantum gradient descent algorithms. In particular, we consider the function pair $(F,f)$ satisfying [Assumption 1](#Thmassumption1) and assume that one can access the function values of the noisy evaluation function $f$. We remark that $f$ may even be non-differentiable or non-smooth. In addition, the noise between $f$ and the target function $F$ might introduce additional SOSPs. Nevertheless, recent work [] indicates that the performance of accelerated gradient descent algorithm (PAGD) [, ] persists when the gradients are inexact. We rigorously prove that the perturbed accelerated gradient descent algorithm with accelerated negative curvature [] equipped with Jordan’s algorithm for quantum gradient estimation [] is robust to the tiny noise on zeroth-order oracles. We formulate our first main result as follow:

###### Theorem 1 (Informal) .

Given a target function $F$ and a noisy function $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu=\Omega(\epsilon^{10}/d^{5})$, there exists a quantum algorithm that finds an $\epsilon$-SOSP of $F$ with high probability using $\tilde{O}(\log d/\epsilon^{1.75})$ queries to the noisy zeroth-order oracle $U_{f}$.

We leave the formal version of [Theorem 1](#Thmtheorem1), the corresponding algorithm, and the proof to [Section 2.1](#S2.SS1). [Theorem 1](#Thmtheorem1) demonstrates that if the noise is small enough, the impact on PAGD algorithm will not lead to an increase on the query complexity. If $\nu=\Omega(\operatorname{poly}(\epsilon,1/d))$, we further demonstrate that this robustness only exists for quantum algorithms by proving a polynomial lower bound in [Theorem 7](#Thmtheorem7) for any classical algorithm.

###### Theorem 1 (Informal) .

##### Small noise: robustness of quantum gradient estimation.

When the strength of noise increases, the negative curvature estimation in standard PAGD will fail. In this case, we show the robustness of the gradient descent algorithm with quantum gradient estimation against the noise. We consider the function pair $(F,f)$ satisfying [Assumption 1](#Thmassumption1) when we can access noisy function $f$. Refs. [, ] conveyed the conceptual message that perturbed gradient descent (PGD) [] algorithm with Jordan’s gradient estimation [] possesses a certain degree of robustness to noise. In this work, we formalize this intuition and obtain the following result:

###### Theorem 2 (Informal) .

Given a target function $F$ and a noisy function $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu\leq\tilde{O}(\epsilon^{6}/d^{4})$, there exists a quantum algorithm that finds an $\epsilon$-SOSP of $F$ with high probability using $\tilde{O}(\log^{4}d/\epsilon^{2})$ queries to the noisy zeroth-order oracle $U_{f}$.

The formal version of [Theorem 2](#Thmtheorem2), the corresponding algorithms, and the proof are given in [Section 2.2](#S2.SS2). [Theorem 2](#Thmtheorem2) demonstrates if the noise on the zeroth-order oracle is below a certain threshold, a quantum algorithm can find an $\epsilon$-SOSP of $F$ within a number of queries that is poly-logarithmic in terms of the dimension $d$. Similar to [Theorem 1](#Thmtheorem1), this robustness only exists in quantum algorithms and provide an exponential quantum speedup in the query complexity compared to the classical counterpart.

We further extend [Theorem 2](#Thmtheorem2) to function pair $(F,f)$ satisfying [Assumption 2](#Thmassumption2). We prove in [Corollary 1](#Thmcorollary1) that the classical PGD iteration is robust against the noise of $\tilde{\nu}\leq O(\epsilon/d^{0.5+\zeta})$ on the first-order gradient information, where $\zeta=\Omega(1/\log(d))$.

###### Theorem 2 (Informal) .

##### Intermediate noise: speedup from quantum mean estimation.

When the strength of noise keeps increasing, the robustness of Jordan’s algorithm will also fail to handle the gap between the noisy function $f$ and the target function $F$. To address this issue, we develop a quantum algorithm based on the Gaussian smoothing of $f$ inspired by Ref. []. We consider function pairs $(F,f)$ satisfying [Assumption 1](#Thmassumption1). We sample the value $\mathbf{z}[f(\mathbf{x}+\mathbf{z})-f(\mathbf{x})]/\sigma^{2}$, where $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$ is chosen from Gaussian distribution with parameter $\sigma^{2}$ []. We then apply quantum mean estimation to approximate the gradient from the samples of stochastic gradients. The performance of the algorithm is given by the following theorem:

###### Theorem 3 (informal) .

Given a target function $F$ and a noisy function $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu\leq O(\epsilon^{1.5}/d)$, there exists a quantum algorithm that finds an $\epsilon$-SOSP of $F$ with high probability taking $\tilde{O}(d^{2.5}/\epsilon^{3.5})$ queries to the noisy zeroth-order oracle $U_{f}$.

[Theorem 3](#Thmtheorem3) indicates that the quantum algorithm can find an $\epsilon$-SOSP of $F$ using polynomial number of queries to $f$ with bounded strength of noise $\nu\leq O(\epsilon^{1.5}/d)$. Recall that the state-of-art classical algorithm [] solves this problem with the same noise strength $\nu\leq O(\epsilon^{1.5}/d)$ using $O(d^{4}/\epsilon^{5})$ queries, our algorithm provides a polynomial improvement compared to the best known classical result in terms of both the dimension $d$ and the precision $\epsilon$.

In [Section 3.2](#S3.SS2), we consider the problem of finding an $\epsilon$-SOSP of functions $F$ taking queries to the quantum gradient oracle in ([8](#S1.E8)). We use $\nabla f(\mathbf{x}+\mathbf{z})-\nabla f(\mathbf{x})$ as a stochastic gradient estimation, where $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$ is chosen from Gaussian distribution with parameter $\sigma^{2}$. Similar to the zeroth-order scenario, we implement quantum mean estimation and
derive the following algorithmic upper bound.

###### Theorem 4 (Informal) .

Given a target function $F$ and the gradient information of a noisy function $f$ satisfying [Assumption 2](#Thmassumption2) with $\tilde{\nu}\leq O(\epsilon/d^{0.5})$, there exists a quantum algorithm that finds an $\epsilon$-SOSP of $F$ with high probability using $\tilde{O}(d^{2}/\epsilon^{3})$ queries to the noisy first-order gradient oracle $U_{\mathbf{g}}$.

The tolerance on $\tilde{\nu}$ and the query complexity is larger compared to [Theorem 3](#Thmtheorem3), where we access a zeroth-order oracle. The best-known classical algorithm finding an $\epsilon$-SOSP under [Assumption 2](#Thmassumption2) requires $O(d^{3}/\epsilon^{4})$ queries. Hence, this quantum algorithm also provides a polynomial reduction on the sample complexity compared to the classical result.

###### Theorem 3 (informal) .

###### Theorem 4 (Informal) .

#### 1.2.2 Lower bounds

##### Large noise: quantum query complexity lower bound in d 𝑑 d .

In this work, we also provide lower bounds concerning $d$ on the query complexity required for any classical and quantum algorithms under [Assumption 1](#Thmassumption1) and [Assumption 2](#Thmassumption2). In particular, we construct a hard instance inspired by Ref. [] (as shown in [Figure 1](#S4.F1) (a)): we define a target function $F$ in a hypercube and use the hypercube to fill the entire space $\mathbb{R}^{d}$. By adding noise to the zeroth- or first-order oracle $f$, we can erase the information of $F$ such that a limited number of classical or quantum queries cannot find any $\epsilon$-SOSPs with high probability.

For a function pair $(F,f)$ satisfying [Assumption 1](#Thmassumption1), our first result in this part is the following quasi-polynomial lower bound.

###### Theorem 5 (Informal) .

We can find functions $F$ and $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\epsilon^{1.5}/d)$ such that any quantum algorithm requires at least $\Omega(d^{\log d})$ queries to $U_{f}$ to find any $\epsilon$-SOSP of $F$ with high probability.

The detailed proof for [Theorem 5](#Thmtheorem5) is a bit technically involved and is left to [Section 4.1](#S4.SS1). Here, we provide the intuition for the proof. To prove this lower bound, we define a function $F$ in a hyperball $\mathbb{B}(\mathbf{0},r)$ and embed the hyperball into a hypercube, with which we can cover the whole space. Next, we introduce noise to create $f$ with a non-informative area around $\mathbf{0}$ (in the sense that any query to this area will obtain no information about any SOSPs of the target function $F$). Then, we transfer this problem into an unstructured search problem. The final lower bound for nonconvex optimization is obtained by applying the quantum lower bound for unstructured search. We mention that the $\epsilon$ and the $d$ dependence for $\nu$ in [Theorem 5](#Thmtheorem5) are tight up to logarithmic factors. The classical version of [Theorem 5](#Thmtheorem5) is proved in Ref. []. The parallelism in quantum algorithms possesses the potential to query different points in superposition. However, [Theorem 5](#Thmtheorem5) demonstrates that the same query complexity lower bound holds even for quantum algorithms.

If the noise $\nu$ keeps increasing, we can further prove the following lower bound in [Section 4.2](#S4.SS2) that prevents any quantum algorithm from finding any $\epsilon$-SOSPs of target function $F$:

###### Theorem 6 (Informal) .

For any quantum algorithm, there exists a pair of functions $(F,f)$ satisfying [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\epsilon^{1.5})$ such that it will fail, with large probability, to find any $\epsilon$-SOSP of $F$ given access to $f$.

Despite the quantum lower bound, we also propose a classical lower bound concerning nonconvex optimization using zeroth-order oracle with noise strength $\nu=O(1/\operatorname{poly}(d))$.

###### Theorem 7 .

For any $\epsilon\leq\epsilon_{0}<1$, where $\epsilon_{0}$ is some constant, there exists a function pair $(F,f)$ satisfying [Assumption 1](#Thmassumption1) with $\nu=\Omega(1/\operatorname{poly}(d))$, such that any classical algorithm that outputs an $\epsilon$-SOSP of $F$ with high probability requires at least $\Omega(d/\log d)$ classical queries to the noisy function $f$.

We prove [Theorem 7](#Thmtheorem7) using an information-theoretic argument inspired by Ref. []. [Theorem 1](#Thmtheorem1), [Theorem 2](#Thmtheorem2), and [Theorem 7](#Thmtheorem7) establish the exponential separation between classical and quantum query complexities required for nonconvex optimization using oracles with noise $\nu=\tilde{\Omega}(\operatorname{poly}(\epsilon,1/d))$. This separation originates from the Jordan’s gradient estimation algorithm []. Classically, querying the evaluation oracle can only provide information at one point. Quantumly, however, one can take the superposition on different points and query the quantum evaluation oracle in parallel [, ].

Moreover, we extend the above lower bound to function pairs $(F,f)$ satisfying [Assumption 2](#Thmassumption2) in [Section 4.4](#S4.SS4). If the noise increases by even a factor that is logarithmic in $d$ from $\tilde{\Theta}(\epsilon/d^{0.5})$, we can prove an exponential lower bound for any classical or quantum algorithm through a similar construction of hard instance used in [Theorem 5](#Thmtheorem5) (as shown in [Figure 1](#S4.F1) (b)). Moreover, if the noise increases to $\Omega(\epsilon)$, there exists a similar hard instance with [Theorem 6](#Thmtheorem6) that prevents any classical or quantum algorithm from finding any $\epsilon$-SOSP of $F$. Formally, we can extend [Theorem 5](#Thmtheorem5) and [Theorem 6](#Thmtheorem6) in the context of [Assumption 2](#Thmassumption2):

###### Theorem 8 (Informal) .

We can find functions $F$ and $f$ satisfying [Assumption 2](#Thmassumption2) with $\tilde{\nu}=\tilde{\Theta}(\epsilon/d^{0.5})$ such that any classical or quantum algorithm that finds an $\epsilon$-SOSP of $F$ with high probability requires at least $\Omega(d^{\log d})$ queries to $U_{\mathbf{g}}$. Moreover, for any classical or quantum algorithm, we can find functions $F$ and $f$ satisfying [Assumption 2](#Thmassumption2) with $\tilde{\nu}=\Theta(\epsilon)$ such that it will fail with high probability.

###### Theorem 5 (Informal) .

###### Theorem 6 (Informal) .

###### Theorem 7 .

###### Theorem 8 (Informal) .

##### Quantum query complexity lower bound in ϵ italic-ϵ \epsilon .

Finally, we establish query complexity lower bounds for classical and quantum nonconvex optimization algorithms under [Assumption 1](#Thmassumption1) or [Assumption 2](#Thmassumption2), respectively, where our results are summarized in [Table 3](#S1.T3).

**Table 3: A summary of our results on classical and quantum query complexity lower bounds in $\epsilon$ under [Assumption 1](#Thmassumption1) or [Assumption 2](#Thmassumption2), respectively. The query complexities are highlighted in terms of the dimension $d$ and the precision $\epsilon$. ($*$) As [Theorem 7](#Thmtheorem7) works for noise strength of $\tilde{\Omega}(\operatorname{poly}(\epsilon,1/d))$, this lower bound holds for both deterministic and randomized classical algorithms.**
| Input Oracle | Noise Strength | Deterministic Classical<br>Lower Bounds | Randomized Classical and<br>Quantum Lower Bounds |
| --- | --- | --- | --- |
| Zeroth-order | $\nu=0$ | N/A | N/A |
| Zeroth-order | $\nu=\Omega(\epsilon^{-16/7}/d)$ | $\Omega(d/\log d)^{*}$ ([Theorem 7](#Thmtheorem7)) | $\Omega(\epsilon^{-12/7})$ ([Theorem 9](#Thmtheorem9)) |
| First-order | $\tilde{\nu}=0$ | $\Omega(\epsilon^{-12/7})$ [] | N/A |
| First-order | $\tilde{\nu}=\Omega(\epsilon^{-8/7}/\sqrt{d})$ | $\Omega(\epsilon^{-12/7})$ [] | $\Omega(\epsilon^{-12/7})$ ([Theorem 9](#Thmtheorem9)) |

###### Theorem 9 (informal) .

There exists a function pair $F$ and $f$ satisfying either [Assumption 1](#Thmassumption1) or [Assumption 2](#Thmassumption2) with $\nu=\Omega(\epsilon^{-16/7}/d)$ or $\tilde{\nu}=\Omega(\epsilon^{-8/7}/\sqrt{d})$, respectively, and additionally $F(\mathbf{0})-\inf_{\mathbf{x}}F(\mathbf{x})\leq\Delta$ for some constant $\Delta$, such that any classical or quantum algorithm with query complexity $\Omega\big{(}\epsilon^{-12/7}\big{)}$ will fail with high probability to find an $\epsilon$-SOSP of target function $F$.

We provide the detailed proof for [Theorem 9](#Thmtheorem9) in [Section 5](#S5) using the hard instance inspired by Refs. [, ]. Previously, there have been two lower bounds concerning $\epsilon$ dependence that apply to classical algorithms for nonconvex optimization. In Ref. [], it is proved that at least $\Omega(\epsilon^{-3/2})$ queries are required in finding an $\epsilon$-SOSP of a Hessian Lipshitz function $F$ even provided both zeroth- and first-order oracles for either random or deterministic classical algorithms.
Using similar techniques, Carmon et al. [] further proved that deterministic classical algorithms using first-order noiseless oracle require $\Omega(\epsilon^{-12/7})$ queries to find an $\epsilon$-SOSP of a Hessian Lipshitz function $F$.

On the other hand, despite recent papers [, ] studying quantum lower bounds on convex optimization, quantum lower bounds on nonconvex optimization are still widely open. In this paper, we fill this conceptual gap by extending the classical deterministic lower bound [] to all classical randomized algorithms and even quantum algorithms, given that noise exists in the function evaluation. In particular, noise allows us to construct a hard instance by creating a non-informative area around $\mathbf{0}$. According to the concentration of measure phenomenon, the non-informative area will occupy an overwhelming proportion of the whole space. Although its intuition and structure are different from the hard instance in Refs. [, ] constructed via performing maximization, the hard instance we construct here exhibits a similar property that, if the number of quantum queries is below a certain threshold, in expectation the output state will barely change if we replace the quantum oracle by an oracle that only encodes “partial” information of the objective function, where the missing information is crucial for any (classical or quantum) algorithm to find an $\epsilon$-SOSP of $F$.

Moreover, we note that our lower bound result in [Theorem 9](#Thmtheorem9) can be extended to the case where the goal is merely to find an $\epsilon$-SOSP if we waive the $B$-bounded requirement on $F$, which may be of independent interest.

###### Theorem 9 (informal) .

### 1.3 Open Questions

Our paper leaves several open questions for future investigations:

- •
Can we give quantum algorithms for the task of nonconvex optimization with better performance using noisy oracles? For instance, can we obtain a quantum algorithm with better dependence on $d$ and $\epsilon$ compared to [Theorem 3](#Thmtheorem3)?
- •
Can we derive tighter lower bounds on quantum algorithms for nonconvex optimization? In particular, it is natural to investigate sublinear or poly-logarithmic quantum lower bounds in dimension $d$ on general optimization problems using either noiseless or noisy oracles.
- •
In this work, we employ a simple model on the noise in [Assumption 1](#Thmassumption1) and [Assumption 2](#Thmassumption2): only the upper bound of noise strength is considered. In general, can we demonstrate the robustness and speedups for nonconvex optimization algorithms analytically under other noise assumptions (say, more practical quantum noise models or stochastic noise models), or experimentally by numerical simulations or on real-world quantum computers?

### 1.4 Organization

The rest of the paper is organized as follows:

- •
In [Section 2](#S2), we prove the robustness for the standard gradient-based algorithms. In particular, we consider the tiny noise case and prove the robustness of PAGD equipped with quantum gradient estimation in [Section 2.1](#S2.SS1). In [Section 2.2](#S2.SS2), we consider the small noise case and prove the robustness of standard PGD equipped with quantum gradient estimation.
- •
In [Section 3](#S3), we consider the intermediate noise case and propose the stochastic gradient descent algorithm using Gaussian smoothing and quantum mean estimation, which provides a polynomial speedup compared to classical algorithms under [Section 3.1](#S3.SS1) and [Section 3.2](#S3.SS2), respectively.
- •
In [Section 4](#S4), we prove lower bounds concerning dimension $d$ for classical and quantum algorithms under different noise strengths. Specifically, in [Section 4.1](#S4.SS1) and [Section 4.2](#S4.SS2), we prove the existence of hard instances under [Assumption 1](#Thmassumption1) for any (polynomial) quantum algorithm when $\nu=\tilde{\Theta}(\epsilon^{1.5}/d)$ ($\nu=\tilde{\Theta}(\epsilon^{1.5})$). In [Section 4.3](#S4.SS3), we prove the $\Omega(d/\log d)$ classical query complexity lower bound using zeroth-order oracles with $\nu=\Omega(1/\operatorname{poly}(d))$. We prove the lower bound under [Assumption 2](#Thmassumption2) in [Section 4.4](#S4.SS4).
- •
In [Section 5](#S5), we prove lower bounds concerning the precision $\epsilon$ for both (possibly randomized) classical algorithms and quantum algorithms.
- •
In the appendices, we introduce necessary existing tools for our proofs in [Appendix A](#A1). Technical lemmas for the main text are given in [Appendix B](#A2). Additional information and extended discussions on PGD equipped with quantum simulation and quantum tunneling walk are provided in [Appendix C](#A3) and [Appendix D](#A4), respectively.

## 2 Robustness of Quantum and Classical Algorithms with Small Noise

In this section, we propose two quantum nonconvex optimization algorithms that are robust for tiny noise and small noise, respectively. These algorithms find to an $\epsilon$-SOSP of $F$ using only polylogarithmic queries to noisy empirical function $f$.

### 2.1 Robustness of Classical Perturbed Accelerated Gradient Descent with tiny noise

To begin with, we introduce the quantum perturbed accelerated gradient descent (PAGD) with accelerated negative curvature finding algorithm, which is inspired by the noiseless nonconvex optimization algorithm in Ref. []. To find an $\epsilon$-SOSP of $F$ using quantum evaluation oracle specified in ([7](#S1.E7)), an important step is to approximate the gradient at each iteration. An ingenious quantum approach initiated by Ref. [] takes a uniform mesh around the point and queries the quantum evaluation oracle (in uniform superposition) in phase using the standard phase kickback technique [, ]. Then by the Taylor expansion, we have

$$ $\displaystyle\sum_{\mathbf{x}}\exp(if(\mathbf{x}))\mathbf{x}\approx\sum_{\mathbf{x}}\bigotimes_{k=1}^{d}\exp(i\frac{\partial f}{\partial\mathbf{x}_{k}}\mathbf{x}_{k})\mathbf{x}_{k}.$ (9) $$

The algorithm finally recovers all the partial derivatives by applying a quantum Fourier transformation (QFT). We refer to Ref. [] for a precise version of Jordan’s gradient estimation algorithm with the following performance guarantee:

###### Lemma 1 (Lemma 2.2, Ref. [ 19 ] ) .

Given a target function $F$ and its noisy evaluation $f$ satisfying [Assumption 1](#Thmassumption1) with noisy rate $\nu$, there exists a quantum algorithm that uses one query to the noisy oracle defined in ([7](#S1.E7)) and outputs a vector $\tilde{\nabla}F(\mathbf{x})$ such that

$$ $\displaystyle\Pr\left[\norm{\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})}\geq 400\omega d\sqrt{\nu\ell}\right]\leq\min\left\{\frac{d}{\omega-1},1\right\},\qquad\forall\omega>1.$ (10) $$

This lemma indicates that with probability at least $1-\delta$, one can use one query to the noisy zeroth-oracle and obtain a vector $\tilde{\nabla}F(\mathbf{x})$ such that

$$ $\displaystyle\norm{\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})}\leq O(d^{2}\sqrt{\nu\ell}/\delta).$ (11) $$

Now, we are ready to introduce our first algorithm as shown in [Algorithm 1](#alg1). This algorithm replaces the gradient queries in Perturbed Accelerated Gradient Descent  [, ] with Jordan’s gradient estimation in [Lemma 1](#Thmlemma1). The negative curvature exploitation (NCE) subroutine as shown in [Algorithm 2](#alg2) is applied if the following condition holds.

$$ $\displaystyle f(\mathbf{x}_{t})\leq f(\mathbf{y}_{t})+\expectationvalue{\tilde{\nabla}F(\mathbf{y}_{t}),\mathbf{x}_{t}-\mathbf{y}_{t}}-\frac{\gamma}{2}\norm{\mathbf{x}_{t}-\mathbf{y}_{t}}^{2}.$ (12) $$

The intuition for NCE ([Algorithm 2](#alg2)) will be discussed later.

We prove that [Algorithm 1](#alg1) has the following performance guarantee:

###### Theorem 10 (Formal version of Theorem 1 ) .

Consider a target function $F$ and its noisy evaluation $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu\leq\tilde{O}(\delta^{2}\epsilon^{10}/d^{5})$. [Algorithm 1](#alg1) can find an $\epsilon$-SOSP of $F$ satisfying Eq. ([4](#S1.E4)) with probability at least $1-\delta$, using

$$ $\displaystyle\tilde{O}\left(\frac{\ell B}{\epsilon^{1.75}}\cdot\log d\right)$ (13) $$

queries to $U_{f}$ defined in ([7](#S1.E7)), under the following parameter choices:

$$ $\displaystyle\eta=\frac{1}{4\ell},\quad\theta=\frac{1}{4\sqrt{\kappa}},\quad\gamma=\frac{\theta^{2}}{\eta},\quad s=\frac{\gamma}{4\rho},\quad\delta_{0}=\frac{\delta\epsilon^{1.75}}{c_{\delta}\ell B}\cdot\log d,$ (14) $\displaystyle r=\frac{\delta_{0}\epsilon}{c_{r}}\sqrt{\frac{\pi}{\rho d}},\quad\mathscr{T}=c_{r}\sqrt{\kappa}\log\left(\frac{\ell\sqrt{d}}{\delta_{0}\sqrt{\rho\epsilon}}\right),\quad\mathscr{F}=\sqrt{\frac{\epsilon^{3}}{\rho}}c^{-7},$ (15) $$

where $c$, $c_{r}$, and $c_{\delta}$ are some large enough constants, and $\kappa=\ell/\sqrt{\rho\epsilon}$.

Figure: Algorithm 1 Perturbed Accelerated Gradient Descent with Accelerated Negative Curvature Finding and Quantum Gradient Computation

Figure: Algorithm 2 Negative Curvature Exploitation (NCE) $(\mathbf{x}_{t},\mathbf{v}_{t},s)$

For simplicity, we denote the error of Jordan’s gradient estimation as $\hat{\nu}$. To solve the problem of monotonic decrease for function value in momentum-based nonconvex optimization problems, we consider the Hamiltonian of the function [] in our proof, which is defined as

$$ $\displaystyle E_{t}=F(\mathbf{x}_{t})+\frac{1}{2\eta}\norm{\mathbf{v}_{t}}^{2}.$ (16) $$

The Hamiltonian composes a potential energy term and a kinetic energy term. It monotonically decreases in the continuous-time scenario. To prove [Theorem 10](#Thmtheorem10), we consider the dynamics of [Algorithm 1](#alg1) in the two different cases depending on whether ([12](#S2.E12)) holds. If it does not hold, the following lemma holds by using Lemma 4 of Ref. [] and replacing the zeroth-order queries to $F(\mathbf{x}_{t})$ and $F(\mathbf{y}_{t})$ with the noisy queries $f(\mathbf{x}_{t})$ and $f(\mathbf{y}_{t})$.

###### Lemma 2 (Adaptive version of Lemma 3, Ref. [ 2 ] ) .

We consider $F(\cdot)$ is $\ell$-smooth and $\rho$-Hessian Lipschitz. Assume one can access the zeroth-order oracle with noise $\nu$ and the first-order oracle with noise $\hat{\nu}$. Set the learning rate $\eta\leq 1/4\ell$, $\theta\in[2\eta\gamma,1/2]$. For each iteration $t$ where ([12](#S2.E12)) does not hold, running [Algorithm 1](#alg1) will decrease the Hamiltonian defined in ([16](#S2.E16)) by

$$ $\displaystyle E_{t+1}\leq E_{t}-\frac{\theta}{2\eta}\norm{\mathbf{v}_{t}}^{2}-\frac{\eta}{4}\norm{\nabla f(\mathbf{y}_{t})}^{2}+O(\eta\hat{\nu}^{2})+O(\nu).$ (17) $$

On the other hand, if ([12](#S2.E12)) holds, the function has an approximate large negative curvature between $\mathbf{y}_{t}$ and $\mathbf{x}_{t}$. The accelerated gradient step might not decrease the value for the Hamiltonian. We thus call the negative curvature exploitation subroutine ([Algorithm 2](#alg2)) to further decrease the Hamiltonian. In particular, when choosing large enough constant $c_{r}$, the following lemme holds by replacing the zeroth-order query to $F(\mathbf{x}_{t})$ and $F(\mathbf{y}_{t})$ with the noisy query $f(\mathbf{x}_{t})$ and $f(\mathbf{y}_{t})$ and noise term $O(\nu)$, respectively, in Lemma 4 of Ref. [].

###### Lemma 3 (Adapted version of Lemma 4, Ref. [ 2 ] ) .

Assume that $F(\cdot)$ is $\ell$-smooth, $\rho$-Hessian Lipschitz, and we are given the zeroth-order oracle with noise strength $\nu$ and the first-order oracle with noise strength $\hat{\nu}$. Set the learning rate $\eta\leq 1/4\ell$, $\theta\in[2\eta\gamma,1/2]$. For each iteration $t$ where ([12](#S2.E12)) holds, running [Algorithm 1](#alg1) wiil decrease the Hamiltonian defined in ([16](#S2.E16)) by

$$ $\displaystyle E_{t+1}\leq E_{t}-\min\left\{\frac{s^{2}}{2\eta},\frac{1}{2}\gamma s^{2}-\rho s^{3}-O\left(\frac{\hat{\nu}^{2}}{\gamma}\right)\right\}+O(\nu).$ (18) $$

We set an additional parameter $\mathscr{T}^{\prime}=\Theta(\sqrt{\kappa})$. Based on [Lemma 2](#Thmlemma2) and [Lemma 3](#Thmlemma3), and proper choices of $\hat{\nu}$ and $\nu$, Lemma 5 of Ref. [] carries over as the below lemma when the norm of the estimated gradient is large enough, i.e. $\big{\|}\tilde{\nabla}F(\mathbf{x}_{t})\big{\|}\geq 3\epsilon/4$.

###### Lemma 4 (Adaptive version of Lemma 5, Ref. [ 2 ] ) .

If $\big{\|}\tilde{\nabla}F(\mathbf{x}_{t})\big{\|}\geq 3\epsilon/4$ and the noise strengths are bounded by $\nu,\hat{\nu}\leq O(\epsilon^{1.25})$ for all $\tau\in[0,\mathscr{T}^{\prime}]$, [Algorithm 1](#alg1) can decrease the Hamiltonian by $E_{\mathscr{T}^{\prime}}-E_{0}\leq-\mathscr{F}$ using

$$ $\displaystyle\mathscr{T}^{\prime}=\sqrt{\kappa}\chi c$ (19) $$

iterations in [Algorithm 1](#alg1), where $\chi=\max\{1,\log(d\ell B/\rho\epsilon\delta_{0})\}$, and $c$ is a large enough constant given in [Theorem 10](#Thmtheorem10)

On the other hand, when the estimated gradient is small, we obtain the following adaptive version of Lemma 7 of Ref. [].

###### Lemma 5 (Adaptive version of Lemma 7, Ref. [ 2 ] ) .

Suppose $\big{\|}\tilde{\nabla}F(\mathbf{x}_{t})\big{\|}\leq 3\epsilon/4$ and the noise strengths are bounded by $\nu,\hat{\nu}\leq O(\epsilon^{3.25}/d^{0.5})$, $\lambda_{\min}(\nabla F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$. For any $0\leq\delta_{0}\leq 1$, we set the parameters as [Theorem 1](#Thmtheorem1). Suppose no perturbation is added in the iterations $[t-\mathscr{T},t]$. By running [Algorithm 1](#alg1) for $\mathscr{T}$ iterations, we have

$$ $\displaystyle\hat{\mathbf{e}}^{\top}\nabla^{2}F(\mathbf{x}_{t})\hat{\mathbf{e}}\leq-\frac{\sqrt{\rho\epsilon}}{4},$ (20) $$

with probability at least $1-\delta_{0}$.

Furthermore, the following lemma from Ref. [] indicates that the function value of $F$ will decrease fast along the direction of $\hat{\mathbf{e}}$.

###### Lemma 6 (Lemma 6, Ref. [ 68 ] ) .

Suppose the function $F$ is $\ell$-smooth and $\rho$-Hessian Lipschitz. For any point $\mathbf{x}_{t}$, if there exists a unit vector $\hat{\mathbf{e}}$ satisfying $\hat{\mathbf{e}}^{\top}F(\mathbf{x}_{t})\hat{\mathbf{e}}\leq-\sqrt{\rho\epsilon}/4$, we have

$$ $\displaystyle F\left(\mathbf{x}_{t}-\frac{F_{\hat{\mathbf{e}}}^{\prime}(\mathbf{x}_{t})}{4\absolutevalue{F_{\hat{\mathbf{e}}}^{\prime}(\mathbf{x}_{t})}}\cdot\sqrt{\frac{\epsilon}{\rho}}\right)\leq F(\mathbf{x}_{t})-\frac{1}{384}\sqrt{\frac{\epsilon^{3}}{\rho}},$ (21) $$

where $F_{\hat{\mathbf{e}}}^{\prime}(\mathbf{x}_{t})$ is the entry of the derivative along $\hat{\mathbf{e}}$.

Now, we are ready to prove [Theorem 10](#Thmtheorem10).

###### Proof.

We first set $\nu\leq\frac{C_{0}}{\ell}\cdot\frac{\epsilon^{10}}{d^{5}}$ for some small enough constant $C_{0}$. According to [Lemma 1](#Thmlemma1), we bound $\hat{\nu}\leq O(\epsilon^{3.25}/d^{0.5})$ with probability at least $1-\delta_{0}$. Assume [Algorithm 1](#alg1) starts at point $\mathbf{x}_{0}$ and the local minimum of $F$ has value $F^{*}$. Since $F$ is $B$-bounded, $F(\mathbf{x}_{0})-F^{*}\leq 2B$. Set the total number of iterations $T$ to be:

$$ $\displaystyle T=3\max\left\{\frac{2B\mathscr{T}^{\prime}}{\mathscr{F}},768B\mathscr{T}\cdot\sqrt{\frac{\rho}{\epsilon^{3}}}\right\}.$ (22) $$

Suppose for some iterations $\mathbf{x}_{t}$, we have $\tilde{\nabla}F(\mathbf{x}_{t})\leq 3\epsilon/4$ and $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$. The error probability of this assumption is given later. Under this assumption, the function value decreases for $\frac{1}{384}\cdot\sqrt{\frac{\epsilon^{3}}{\rho}}$ after each $\mathscr{T}^{\prime}$ iterations. The number of such iterations when [Lemma 6](#Thmlemma6) can be called is bounded by $T/3$ times, for otherwise the function value will decrease greater than $2B\geq F(\mathbf{x}_{0})-F^{*}$, which is impossible. The failure probability is composed of two parts: the failure probability of estimating the gradients in [Lemma 1](#Thmlemma1) and the failure probability of [Lemma 6](#Thmlemma6). In each iteration, the probability of failure is bounded by $2\delta_{0}$ according to the union bound. When we choose a large enough constant $\mathbf{c}_{\delta}$, the overall probability that [Algorithm 1](#alg1) fails to indicate a negative curvature is upper bounded by

$$ $\displaystyle\frac{T}{3}\cdot 2\delta_{0}\leq\frac{\delta}{2}.$ (23) $$

Excluding the iterations that [Lemma 6](#Thmlemma6) is applied, there are $2T/3$ iterations left. We consider the iterations $\mathbf{x}_{t}$ with large gradients, ${\tilde{\nabla}F(\mathbf{x}_{t})}\geq 3\epsilon/4$. According to [Lemma 4](#Thmlemma4), the function value decreases by at least $\mathscr{F}$ with probability at least $1-\delta_{0}$ in $\mathscr{T}^{\prime}$ iterations. Thus there can be at most $T/3$ steps with large gradients, for otherwise, the function value will decrease greater than $2B\geq F(\mathbf{x}_{0})-F^{*}$, which is impossible. The fail probability is bounded by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\frac{\delta}{2}.$ (24) $$

In summary, we can deduce that with probability at least $1-\delta$, there are at most $T/3$ iterations within which the neighboring $\mathscr{T}$ iterations have small gradients but large negative curvatures, and at most $T/3$ iterations with large gradients. Therefore, the rest $T/3$ iterations must be $\epsilon$-SOSPs of target function $F$. The number of queries is thus bounded by

$$ $\displaystyle T\leq\tilde{O}\left(\frac{B\ell}{\epsilon^{1.75}}\cdot\log d\right).$ (25) $$

∎

###### Lemma 1 (Lemma 2.2, Ref. [ 19 ] ) .

###### Theorem 10 (Formal version of Theorem 1 ) .

###### Lemma 2 (Adaptive version of Lemma 3, Ref. [ 2 ] ) .

###### Lemma 3 (Adapted version of Lemma 4, Ref. [ 2 ] ) .

###### Lemma 4 (Adaptive version of Lemma 5, Ref. [ 2 ] ) .

###### Lemma 5 (Adaptive version of Lemma 7, Ref. [ 2 ] ) .

###### Lemma 6 (Lemma 6, Ref. [ 68 ] ) .

###### Proof.

### 2.2 Robustness of Quantum Perturbed Gradient Descent

When the noise rate increases but is still bounded by $\nu\leq\tilde{O}(\epsilon^{6}/d^{4})$, some quantum algorithms using perturbed gradient descent (PGD) for noiseless cases are robust against such noise. We introduce the quantum PGD algorithm, which is the one of the standard methods used for noiseless nonconvex optimization [].

[Algorithm 3](#alg3) replaces the gradient queries in PGD [] by Jordan’s gradient estimations in [Lemma 1](#Thmlemma1).

Figure: Algorithm 3 Perturbed Gradient Descent with Quantum Gradient Computation

We prove that [Algorithm 3](#alg3) has the following performance guarantee:

###### Theorem 11 (Formal version of Theorem 2 ) .

Suppose we have a target function $F$ and its noisy evaluation $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu\leq\tilde{O}(\delta^{2}\epsilon^{6}/d^{4})$. [Algorithm 3](#alg3) can find an $\epsilon$-SOSP of $F$ satisfying Eq. ([4](#S1.E4)) with probability at least $1-\delta$, using

$$ $\displaystyle\tilde{O}\left(\frac{\ell B}{\epsilon^{2}}\cdot\log^{4}d\right)$ (26) $$

queries to $U_{f}$ defined in ([7](#S1.E7)), under the following parameter choices:

$$ $\displaystyle\eta=\frac{1}{\ell},\quad\delta_{0}=\frac{\delta\epsilon^{2}}{32\ell B}\chi^{-4},\quad r=\epsilon\chi^{-3}c^{-6},\quad\mathscr{T}=\frac{\chi c}{\eta\sqrt{\rho\epsilon}},\quad\mathscr{F}=\sqrt{\frac{\epsilon^{3}}{\rho}}\chi^{-3}c^{-5},$ (27) $$

where $c$ is some large enough constant and $\chi=\max\{1,\log(d\ell B/\rho\epsilon\delta_{0})\}$.

To prove [Theorem 11](#Thmtheorem11), we consider two cases where the current iteration $\mathbf{x}_{t}$ is not an $\epsilon$-SOSP of $F$. In the first case, the gradient $\norm{\nabla F(\mathbf{x}_{t})}\geq\epsilon$ is larger than $\epsilon$. In the second case, the gradient $\norm{\nabla F(\mathbf{x}_{t})}\leq\epsilon$ but the minimal eigenvalue of the Hessian matrix satisfies $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$. Intuitively, the proof of [Theorem 11](#Thmtheorem11) is composed of the performance guarantees regarding both cases. For [Algorithm 3](#alg3), it takes $\mathscr{T}=O(\log d)$ queries to $U_{f}$ to decrease the function value by $\mathscr{F}=O(1/\log^{3}d)$ [].

We first set $\nu\leq\frac{C_{0}}{\ell}\cdot(\frac{\delta\epsilon^{3}}{Bd^{2}\chi^{4}\ell})^{2}$ for some small enough constant $C_{0}$. Formally, we introduce the following lemma characterizing the performance of [Algorithm 3](#alg3) when the gradient is large:

###### Lemma 7 .

Under the setting of [Theorem 11](#Thmtheorem11), for any iteration $t$ of [Algorithm 3](#alg3) with $\norm{\nabla F(\mathbf{x}_{t})}\geq\epsilon$, we have $F(\mathbf{x}_{t+1})-F(\mathbf{x}_{t})\leq-\eta\epsilon^{2}/4$ with probability at least $1-\delta_{0}$, where $\delta_{0}$ is defined in Eq. ([27](#S2.E27)).

###### Proof.

We set $\omega=2d/\delta_{0}$ and choose $C_{0}$ small enough such that

$$ $\displaystyle\norm{\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})}\leq\frac{\epsilon}{20}$ (28) $$

with probability at least $1-\delta_{0}$ according to [Lemma 1](#Thmlemma1).

Next, we choose $c$ such that $\norm{\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})}\leq\epsilon/20$. Recall that the perturbation $\xi_{t}$ is chosen from $B_{0}(r)$, the stochastic part in each iteration $\kappa_{t}=\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})+\xi_{t}$ is bounded by $\norm{\kappa_{t}}=\epsilon/10$. According to the update rule $\mathbf{x}_{t+1}=\mathbf{x}_{t}-\eta(\nabla F(\mathbf{x}_{t})+\kappa_{t})$ of [Algorithm 3](#alg3), we have

$$ $\displaystyle F(\mathbf{x}_{t+1})$ $\displaystyle\leq F(\mathbf{x}_{t})+\expectationvalue{\nabla F(\mathbf{x}_{t}),\mathbf{x}_{t+1}-\mathbf{x}_{t}}+\frac{\ell}{2}\norm{\mathbf{x}_{t+1}-\mathbf{x}_{t}}^{2}$ $\displaystyle\leq F(\mathbf{x}_{t})-\eta\left[\norm{\nabla F(\mathbf{x}_{t})}^{2}-\norm{\nabla F(\mathbf{x}_{t})}\norm{\kappa_{t}}\right]+\frac{\eta^{2}\ell}{2}\left[\norm{\nabla F(\mathbf{x}_{t})}^{2}+2\norm{\nabla F(\mathbf{x}_{t})}\norm{\kappa_{t}}+\norm{\kappa_{t}}^{2}\right]$ $\displaystyle\leq F(\mathbf{x}_{t})-\eta\norm{\nabla F(\mathbf{x}_{t})}\left[\frac{1}{2}\norm{\nabla F(\mathbf{x}_{t})}-2\norm{\kappa_{t}}\right]+\frac{\eta}{2}\norm{\kappa_{t}^{2}}$ $\displaystyle\leq F(\mathbf{x}_{t})-\frac{\eta\epsilon^{2}}{4}.$ (29) $$

∎

In addition, we can generalize the following lemma in Ref. [].

###### Lemma 8 (Lemma 67, Ref. [ 37 ] ) .

Suppose we are given a oracle that outputs an gradient estimation $\tilde{\nabla}F(\mathbf{x}_{t})$ such that $\norm{\tilde{\nabla}F(\mathbf{x}_{t})-\nabla F(\mathbf{x}_{t})}\leq\epsilon/20$. Consider a iteration $t$ of [Algorithm 3](#alg3) with $\norm{\nabla F(\mathbf{x}_{t})}\geq\epsilon$. By using the PGD update rule $\mathbf{x}_{t+1}=\mathbf{x}_{t}-\eta(\tilde{\nabla}F(\mathbf{x}_{t})+\xi_{t})$, we have $F(\mathbf{x}_{t+1})-F(\mathbf{x}_{t})\leq-\eta\epsilon^{2}/4$ with probability at least $1-\delta_{0}$, where $\delta_{0}$ is defined in Eq. ([27](#S2.E27)).

When the gradient is small but the minimal eigenvalue of the Hessian matrix is large, i.e., the function has a large negative curvature at the current iteration, we have the following lemma from Ref. [].

###### Lemma 9 (Lemma 68, Ref. [ 37 ] ) .

Suppose we are given a oracle that outputs an gradient estimation $\tilde{\nabla}F(\mathbf{x}_{t})$ such that $\norm{\tilde{\nabla}F(\mathbf{x}_{t})-\nabla F(\mathbf{x}_{t})}\leq\epsilon/20$ and the norm of the perturbation in PGD is bounded by $\norm{\xi_{t}}\leq r$ with $r>\epsilon/20$. If $\norm{\nabla F(\mathbf{x}_{t})}\leq\epsilon$ and $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$. By using the PGD update rule $\mathbf{x}_{t+1}=\mathbf{x}_{t}-\eta(\tilde{\nabla}F(\mathbf{x}_{t})+\xi_{t})$, we have $F(\mathbf{x}_{t+\mathscr{T}})-F(\mathbf{x}_{t})\leq-\mathscr{F}$ with probability at least $1-\delta_{0}$ when running [Algorithm 3](#alg3).

Now, we are ready to prove [Theorem 11](#Thmtheorem11).

###### Proof of Theorem 11 .

Assume our [Algorithm 3](#alg3) starts at point $\mathbf{x}_{0}$ and the local minimum of $F$ has value $F^{*}$. Since $F$ is $B$-bounded, we have $F(\mathbf{x}_{0})-F^{*}\leq 2B$. Set the total number of iterations $T$ to be:

$$ $\displaystyle T=3\max\left\{\frac{8B}{\eta\epsilon^{2}},\frac{2B\mathscr{T}}{\mathscr{F}}\right\}.$ (30) $$

Assume for some iterations $\mathbf{x}_{t}$, we have $\nabla F(\mathbf{x}_{t})\leq\epsilon$ and $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$.
The error probability of this assumption is given later. Under this assumption, the function value decreases for $\mathscr{F}$ after each $\mathscr{T}$ iterations. The number of such iterations when [Lemma 9](#Thmlemma9) can be called is bounded by $T/3$ times, for otherwise the function value will decrease greater than $2B\geq F(\mathbf{x}_{0})-F^{*}$, which is impossible. The failure probability is composed of two parts: the failure probability of estimating the gradients in [Lemma 1](#Thmlemma1) and the failure probability of [Lemma 9](#Thmlemma9). In each iteration, the probability of failure is bounded by $2\delta_{0}$ according to the union bound. The overall probability that [Algorithm 3](#alg3) fails to indicate a negative curvature is upper bounded by

$$ $\displaystyle\frac{T}{3}\cdot 2\delta_{0}\leq\frac{\delta}{2}$ (31) $$

for any $\chi$.

Excluding the iterations in which [Lemma 9](#Thmlemma9) is applied, we still have $2T/3$ iterations left. We now consider the iterations $\mathbf{x}_{t}$ with large gradients ${\nabla F(\mathbf{x}_{t})}\geq\epsilon$. According to [Lemma 7](#Thmlemma7), the function value decreases by at least $\eta\epsilon^{2}/4$ with probability at least $1-\delta_{0}$ in each iteration. Thus there can be at most $T/3$ steps with large gradients, for otherwise, the function value will decrease greater than $2B\geq F(\mathbf{x}_{0})-F^{*}$, which is impossible. The fail probability is bounded by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\frac{\delta}{2}.$ (32) $$

In summary, we can deduce that with probability at least $1-\delta$, there are at most $T/3$ iterations within which the neighboring $\mathscr{T}$ iterations have small gradients but large negative curvatures, and at most $T/3$ iterations with large gradients. Therefore, the rest $T/3$ iterations must be $\epsilon$-SOSPs of target function $F$. The number of queries is thus bounded by

$$ $\displaystyle T\leq\tilde{O}\left(\frac{B\ell}{\epsilon^{2}}\cdot\log^{4}d\right).$ (33) $$

∎

The above [Theorem 11](#Thmtheorem11) indicates that our PGD method with quantum gradient computation still converges and finds an $\epsilon$-SOSP using the same number of iterations (i.e., the same number of queries), even if there exists small noise on the quantum evaluation oracles. We remark that compared to Algorithm $4$ in Ref. [], [Algorithm 3](#alg3) employs a classical perturbation uniformly chosen from the ball $\mathbb{B}(\mathbf{0},r)$. Therefore, [Algorithm 3](#alg3) requires no access to the quantum evaluation oracle without noise.

It is natural to ask if we can improve the dependence on $\log d$ in the query complexity. We answer this question with an affirmative answer in [Appendix C](#A3) under some additional assumptions. Consider if we have functions $F$ and $f$ that satisfy [Assumption 1](#Thmassumption1) with $\nu\leq O(\epsilon^{6}/d^{4})$ and we further assume that $f$ is twice differentiable with $\sup_{\mathbf{x}}\norm{\nabla f-\nabla F}\leq O(\ell/d^{2+\zeta})$ and $\sup_{\mathbf{x}}\norm{\nabla^{2}f-\nabla^{2}F}\leq O(\rho/d^{1.5+\zeta})$ for arbitrary $\zeta>0$. We propose a quantum algorithm that can find an $\epsilon$-SOSP for $F$ using $\tilde{O}(\ell B/\epsilon^{2}\cdot\log^{2}d)$ queries to the quantum evaluation oracle in Eq. ([7](#S1.E7)).

In addition, we can use the techniques above to prove the algorithmic upper bound for function pair $(F,f)$ satisfying [Assumption 2](#Thmassumption2) with $\tilde{\nu}\leq O(\epsilon/d^{0.5+\zeta})$ for $\zeta>0$ and $\zeta=\Omega(1/\log(d))$. We provide the following corollary corresponding to the last line in [Table 2](#S1.T2).

###### Corollary 1 .

Suppose we have a target function $F$ and a noisy function $f$ satisfying [Assumption 2](#Thmassumption2) with $\tilde{\nu}\leq O(\epsilon/d^{0.5+\zeta})$ for $\zeta>0$ and $\zeta=\Omega(1/\log(d))$. Consider the gradient descent $\mathbf{x}_{t+1}=\eta(\nabla f+\xi_{t})$ with $\xi_{t}$ uniformly chosen from ball $\mathbb{B}(\mathbf{0},r)$. This rule can output an $\epsilon$-SOSP of $F$ satisfying Eq. ([4](#S1.E4)), using

$$ $\displaystyle\tilde{O}\left(\frac{\ell B}{\epsilon^{2}}\cdot\log^{4}d\right)$ (34) $$

queries to $U_{\mathbf{g}}$ in ([8](#S1.E8)) with probability $1-\delta$, under the following parameter choices

$$ $\displaystyle\eta=\frac{1}{\ell},\quad\delta_{0}=\frac{\delta\epsilon^{2}}{4\ell B}\chi^{-4},\quad r=\epsilon\chi^{-3}c^{-6},\quad\mathscr{T}=\frac{\chi c}{\eta\sqrt{\rho\epsilon}},\quad\mathscr{F}=\sqrt{\frac{\epsilon^{3}}{\rho}}\chi^{-3}c^{-5},$ (35) $$

where $c$ is some large enough constant and $\chi=\max\{1,\log(d\ell B/\rho\epsilon\delta_{0})\}$.

###### Proof.

Without loss of generality, we set $\tilde{\nu}\leq O(\epsilon/d^{0.5+\zeta})$ and $\zeta\geq\log 20/\log(d)$ such that $\tilde{\nu}\geq\epsilon/20$. We then choose $c$ large enough such that $\norm{\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})}\leq\epsilon/20$. As the perturbation $\xi_{t}$ is chosen from $B_{0}(r)$, the stochastic part in each iteration $\kappa_{t}=\tilde{\nabla}F(\mathbf{x})-\nabla F(\mathbf{x})+\xi_{t}$ is bounded by $\norm{\kappa_{t}}=\epsilon/10$. Similar to the proof of [Theorem 11](#Thmtheorem11), we set

$$ $\displaystyle T=3\max\left\{\frac{8B}{\eta\epsilon^{2}},\frac{2B\mathscr{T}}{\mathscr{F}}\right\}.$ (36) $$

Suppose for some iterations, the function have small gradients $\nabla F(\mathbf{x}_{t})\leq\epsilon$ and large negative curvatures $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$. Under this assumption, the function value decreases for $\mathscr{F}$ after each $\mathscr{T}$ iterations according to [Lemma 9](#Thmlemma9). The number of such iterations when [Lemma 9](#Thmlemma9) can be called is bounded by $T/3$ times, for otherwise, the function value will decrease greater than $2B\geq F(\mathbf{x}_{0})-F^{*}$, which is impossible. The failure probability is bounded above by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\delta/2.$ (37) $$

Except for the iterations that [Lemma 9](#Thmlemma9) is applied, we still have $2T/3$ iterations left. We now consider the iterations $\mathbf{x}_{t}$ with large gradients, ${\nabla F(\mathbf{x}_{t})}\geq\epsilon$. According to [Lemma 8](#Thmlemma8), the function value decreases by at least $\eta\epsilon^{2}/4$ with the probability at least $1-\delta_{0}$ in each iteration. Thus there can be at most $T/3$ steps with large gradients, for otherwise, the function value will decrease greater than $2B\geq F(\mathbf{x}_{0})-F^{*}$, which is impossible. The failure probability is again bounded above by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\delta/2.$ (38) $$

Therefore, we can deduce that with probability at least $1-\delta$, there are at most $T/3$ iterations resulting in points having small gradients but large negative curvature, and at most $T/3$ iterations with large gradients. Therefore, the rest $T/3$ iterations must be $\epsilon$-SOSPs. The number of the queries is bounded by

$$ $\displaystyle T\leq\tilde{O}\left(\frac{B\ell}{\epsilon^{2}}\cdot\log^{4}d\right).$ (39) $$

∎

[Corollary 1](#Thmcorollary1) indicates that when the gradient $\mathbf{g}=\nabla f$ of the noisy function is close enough to the gradient $\nabla F$ of the target function, the PGD algorithm can converge even if the gradient $\mathbf{g}$ is noisy. As we can directly query the noisy gradient, the quantum algorithms such as quantum mean estimation [, ] or quantum gradient estimation [, ] cannot provide speedup in this case. Moreover, quantum approaches to add perturbation such as quantum simulation [] require zeroth-order information, which is unavailable under [Assumption 2](#Thmassumption2). Therefore, there is no quantum speedup compared to the classical gradient descent in the setting of [Corollary 1](#Thmcorollary1).

###### Theorem 11 (Formal version of Theorem 2 ) .

###### Lemma 7 .

###### Proof.

###### Lemma 8 (Lemma 67, Ref. [ 37 ] ) .

###### Lemma 9 (Lemma 68, Ref. [ 37 ] ) .

###### Proof of Theorem 11 .

###### Corollary 1 .

###### Proof.

## 3 Quantum Speedup Using Mean Estimation

When the noise strength further increases, it exceeds the robustness of quantum PGD. To handle this issue, we apply a Gaussian smoothing to the noisy function $f$ inspired by Ref. [], which can turn a possibly nonsmooth or even non-continuous $f$ into a function $f_{\sigma}$ with “good” properties such as smoothness and Hessian-Lipschitzness.

### 3.1 Zeroth-order Algorithm and Performance Guarantee

In this section, we introduce a quantum algorithm based on Gaussian smoothing for function pairs $(F,f)$ satisfying [Assumption 1](#Thmassumption1) with $\nu\leq O(\epsilon^{1.5}/d)$. We formally define the Gaussian smoothing for a function $f$ as follows.

###### Definition 1 .

Given a function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, we define its Gaussian smoothing $f_{\sigma}\colon\mathbb{R}^{d}\to\mathbb{R}$ as

$$ $\displaystyle f_{\sigma}\coloneqq\mathbb{E}_{\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)}[f(\mathbf{x}+\mathbf{z})],$ (40) $$

where the parameter $\sigma$ is the smoothing radius.

Given a noisy function $f$ and a target function $F$ satisfying [Assumption 1](#Thmassumption1), Gaussian smoothing transfers the (probably even non-smooth or not differentiable) noisy $f$ into a smooth function $f_{\sigma}$ that has close gradient and Hessian with $F$. Formally, $f_{\sigma}$ has the following properties according to Ref. []:

###### Lemma 10 (Lemma 13, Ref. [ 37 ] ) .

Assume the function pair $(F,f)$ satisfies [Assumption 1](#Thmassumption1), the Gaussian smoothing $f_{\sigma}$ of $f$ satisfies the following properties.

- •
$f_{\sigma}(\mathbf{x})$ is $O(\ell+\nu/\sigma^{2})$-smooth and $O(\rho+\nu/\sigma^{3})$-Hessian Lipshitz.
- •
The distance between the gradient and the Hessian of $f_{\sigma}$ and $F$ at any $\mathbf{x}$ is bounded by $\norm{\nabla f_{\sigma}(\mathbf{x})-\nabla F(\mathbf{x})}\leq O(\rho d\sigma^{2}+\nu/\sigma)$ and $\norm{\nabla^{2}f_{\sigma}(\mathbf{x})-\nabla^{2}F(\mathbf{x})}\leq O(\rho\sqrt{d}\sigma+\nu/\sigma^{2})$.

The first part of [Lemma 10](#Thmlemma10) demonstrates that the Gaussian smoothing $f_{\sigma}$ is a smooth and Hessian Lipschitz function. Thus we can perform standard gradient descent on $f_{\sigma}$ with a polynomial convergence rate. The second part of [Lemma 10](#Thmlemma10) indicates that the gradients and Hessians of $f_{\sigma}$ are similar to those of the target function $F$ up to a term related to the noise rate $\nu$ and the smoothing radius $\sigma$. As the noise rate $\nu$ increases and the noisy function $f$ deviates further from the target function $F$, we have to choose a larger parameter $\sigma$ to bound the terms $\nu/\sigma$, $\nu/\sigma^{2}$, and $\nu/\sigma^{3}$. However, choosing a larger smoothing radius $\sigma$ will increase the term $\rho d\sigma^{2}$ and $\rho\sqrt{d}\sigma$, which erases the information about local geometry of $F$. Hence, the choice of $\sigma$ must balance between the two terms in the bounds in [Lemma 10](#Thmlemma10).

Suppose we have an $\tilde{\epsilon}$-SOSP $\mathbf{x}_{\text{SOSP}}$ of the Gaussian smoothing $f_{\sigma}$. One have to guarantee that an $\tilde{\epsilon}$-SOSP of the Gaussian smoothing $f_{\sigma}$ is also an $\epsilon$-SOSP of $F$. We now search for the value of $\sigma$ and $\tilde{\epsilon}$ such that $\nu$ is maximized. According to [Lemma 10](#Thmlemma10), we can bound the gradient and the minimal eigenvalue of Hessian for $F(\mathbf{x}_{\text{SOSP}})$ by the following inequalities.

$$ $\displaystyle\norm{\nabla F(\mathbf{x}_{\text{SOSP}})}$ $\displaystyle\leq\rho d\sigma^{2}+\frac{\nu}{\sigma}+\tilde{\epsilon},$ (41) $$

whereas

$$ $\displaystyle\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{\text{SOSP}}))$ $\displaystyle\geq\lambda_{\min}(\nabla^{2}f_{\sigma}(\mathbf{x}_{\text{SOSP}}))+\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{\text{SOSP}})-\nabla^{2}f_{\sigma}(\mathbf{x}_{\text{SOSP}}))$ $\displaystyle\geq-\sqrt{\left(\rho+\frac{\nu}{\sigma^{3}}\right)\tilde{\epsilon}}-\norm{\nabla^{2}f_{\sigma}(\mathbf{x}_{\text{SOSP}})-\nabla^{2}F(\mathbf{x}_{\text{SOSP}})}$ $\displaystyle\geq-\sqrt{\left(\rho+\frac{\nu}{\sigma^{3}}\right)\tilde{\epsilon}}-\left(\rho\sqrt{d}\sigma+\frac{\nu}{\sigma^{2}}\right).$ (42) $$

Hence, to guarantee that an $\tilde{\epsilon}$-SOSP of $f_{\sigma}$ is an $\epsilon$-SOSP of $F$, we only need the following set of inequalities to be satisfied(up to constant factors).

$$ $\displaystyle\rho\sqrt{d}\sigma+\frac{\nu}{\sigma^{2}}$ $\displaystyle\leq O(\sqrt{\rho\epsilon}),$ (43) $\displaystyle\rho d\sigma^{2}+\frac{\nu}{\sigma}$ $\displaystyle\leq O(\epsilon),$ (44) $\displaystyle\left(\rho+\frac{\nu}{\sigma^{3}}\right)\tilde{\epsilon}$ $\displaystyle\leq O(\rho\epsilon).$ (45) $$

From ([43](#S3.E43)) and ([44](#S3.E44)), we have

$$ $\displaystyle\sigma$ $\displaystyle\leq O\left(\sqrt{\frac{\epsilon}{\rho d}}\right),$ (46) $\displaystyle\nu$ $\displaystyle\leq\sqrt{\rho\epsilon}\sigma^{2}=O\left(\sqrt{\frac{\epsilon^{3}}{\rho}}\cdot\frac{1}{d}\right),$ (47) $\displaystyle\tilde{\epsilon}$ $\displaystyle\leq\frac{\rho\epsilon}{\left(\rho+\frac{\nu}{\sigma^{3}}\right)}=O\left(\frac{\epsilon}{\sqrt{d}}\right).$ (48) $$

The above results indicate that we can guarantee that an $O(\epsilon/\sqrt{d})$-SOSP for $f_{\sigma}$ is an $\epsilon$-SOSP of the target function $F$.

The next step is to find an $O(\epsilon/\sqrt{d})$-SOSP of $f_{\sigma}$ using queries to the noisy oracle in ([7](#S1.E7)). Through Gaussian smoothing, we convert the function evaluations of $f$ into stochastic gradients of $f_{\sigma}$. According to Ref. [] the gradients of $f_{\sigma}$ can be calculated as

$$ $\displaystyle\nabla f_{\sigma}=\frac{1}{\sigma^{2}}\mathbb{E}_{\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)}[\mathbf{z}(f(\mathbf{x}+\mathbf{z})-(\mathbf{x}))].$ (49) $$

One can thus compute the gradient for $f_{\sigma}$ by querying the function value of $f$. However, the gradient is unbiasedly computed through averaging over the continuous Gaussian distribution. To approximate the gradient, we employ the zeroth-order quantum oracle in ([7](#S1.E7)) to sample the stochastic gradient estimation $\mathbf{z}[f(\mathbf{x}+\mathbf{z})-f(\mathbf{x})]/\sigma^{2}$, where $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$. The stochastic gradient has the following properties.

###### Lemma 11 (Lemma 14, Ref. [ 37 ] ) .

We denote $\mathbf{g}(\mathbf{x};\mathbf{z})=\mathbf{z}[f(\mathbf{x}+\mathbf{z})-f(\mathbf{x})]/\sigma^{2}$, where $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$. The following inequalities hold:

$$ $\displaystyle\mathbb{E}_{\mathbf{z}}\mathbf{g}(\mathbf{x};\mathbf{z})=\nabla f_{\sigma}(\mathbf{x}),$ (50) $\displaystyle\Pr\left[\norm{\mathbf{g}(\mathbf{x};\mathbf{z})-\nabla f_{\sigma}(\mathbf{x})}\geq t\right]\leq\exp(-Bt^{2}/\sigma),\qquad\forall t>0.$ (51) $$

The second inequality demonstrates that $\mathbf{g}(\mathbf{x};\mathbf{z})$ is a sub-Gaussian random variable with a tail $B/\sigma$.

[Lemma 11](#Thmlemma11) guarantees that by sampling a large mini-batch and evaluating the mean of the stochastic gradients, the value converges to the gradient $\nabla f_{\sigma}(\mathbf{x})$ of the Gaussian smoothing $f_{\sigma}(\mathbf{x})$. Classically, the batch size required for the sampling can be obtained by the Chernoff bound (say, e.g. Ref. []).

###### Lemma 12 .

Given a fixed point $\mathbf{x}$ and the mini-batch size $m$, for any $\delta>0$, we have:

$$ $\displaystyle\norm{\nabla f(\mathbf{x})-\frac{1}{m}\sum_{i=1}^{m}\mathbf{g}(\mathbf{x};\mathbf{z}^{(i)})}\leq\sqrt{\frac{2\sigma_{0}^{2}d}{m}\log(\frac{d}{\delta})}$ (52) $$

with probability at least $1-\delta$, where $\sigma_{0}=B/\sigma$ is the standard deviation of the stochastic gradient.

[Lemma 12](#Thmlemma12) indicates that it is sufficient to choose a mini-batch of size

$$ $\displaystyle m\geq\frac{2\sigma_{0}^{2}d}{\epsilon^{2}}\log(\frac{d}{\delta}),$ (53) $$

where $\sigma_{0}=B/\sigma$, to estimate the gradient $\nabla f_{\sigma}(\mathbf{x})$ within $\epsilon$ under Euclidean norm with probability at least $1-\delta$. In addition, this bound is optimal in any classical algorithms [], or equivalently, any classical multivariate mean estimator with batch size less than this quantity will fail on a certain stochastic gradient function $\mathbf{g}(\mathbf{x};\mathbf{z})$.

Quantumly, the well-known amplitude estimation algorithm [] provides a smaller error rate when estimating the mean of Bernoulli random variables. For the multivariate mean estimation problem of a random vector, quantum algorithms can also provide a speedup under certain circumstances. In particular, we consider the mean estimation task of estimating $\mathbf{g}(\mathbf{x};\mathbf{z})$ in [Lemma 11](#Thmlemma11) given a binary oracle defined as follows.

###### Definition 2 .

Consider the random variable $\mathbf{g}(\mathbf{x};\mathbf{z})\in\mathbb{R}^{d}$ with $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$. Let $\mathcal{H}_{\mathbf{z}}$ and $\mathcal{H}_{\mathbf{g},\mathbf{x}}$ be two Hilbert spaces with basis states $\{\ket{\mathbf{z}}\}_{\mathbf{z}}$ and $\{\mathbf{g}(\mathbf{x};\mathbf{z})\}_{\mathbf{z}}$, which contains quantum state encoding vectors $\mathbf{z}$ and $\mathbf{g}(\mathbf{x};\mathbf{z})$, respectively. The binary oracle $B_{\mathbf{z}}\colon\mathcal{H}_{\mathbf{z}}\otimes\mathcal{H}_{\mathbf{g},\mathbf{x}}\to\mathcal{H}_{\mathbf{z}}\otimes\mathcal{H}_{\mathbf{g},\mathbf{x}}$ is defined as

$$ $\displaystyle B_{\mathbf{z}}:\ket{\mathbf{z}}\ket{\mathbf{0}}\to\ket{\mathbf{z}}\ket{\mathbf{g}(\mathbf{x};\mathbf{z})},\qquad\forall\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I),$ (54) $$

where we assume $\mathbf{0}\in\{\mathbf{g}(\mathbf{x};\mathbf{z})\}_{\mathbf{z}}$.

In practice, the above binary oracle
can be constructed by employing two quantum evaluation oracles in ([7](#S1.E7)). Using such binary oracle, Ref. [] provides the following performance guarantee.

###### Lemma 13 (Theorem 3.5, Ref. [ 23 ] ) .

Suppose $\mathbf{g}$ is a $d$-dimensional random vector with mean $\mu$ and covariance matrix $\Sigma$ such that $\operatorname{Tr}(\Sigma)=\sigma_{0}^{2}$. Given two real values $\delta\in(0,1)$ and $m\geq\log(d/\delta)$, there exists a quantum algorithm that outputs a mean estimation $\tilde{\mu}$ such that

$$ $\displaystyle\norm{\tilde{\mu}-\mu}\leq\begin{cases}O\left(\sqrt{\frac{\sigma_{0}^{2}}{m}}\right),&n\leq d,\\ O\left(\frac{\sqrt{d\sigma_{0}^{2}}\log(\frac{d}{\delta})}{m}\right),\qquad&n>d,\end{cases}$ (55) $$

with probability at least $1-\delta$. Such an algorithm requires $\tilde{O}(m)$ queries to the binary oracle.

[Lemma 13](#Thmlemma13) indicates that it only requires

$$ $\displaystyle m\geq O\left(\frac{\sqrt{d}\sigma_{0}}{\epsilon}\log(\frac{d}{\delta})\right)$ (56) $$

samples to estimate the gradient $\nabla f_{\sigma}(\mathbf{x})$ within error $\epsilon$ with high probability. Compared with the classical mini-batch size in [Lemma 12](#Thmlemma12), quantum mean estimation provides a quadratic reduction when the classical mini-batch size is $\Omega(d)$. It is worthwhile to mention that the error scaling in [Lemma 13](#Thmlemma13) is near-optimal up to logarithmic factors [].

We consider using the PGD with stochastic gradient estimation to find an $\epsilon$-SOSP of the target function $F$ (also an $O(\epsilon/\sqrt{d})$-SOSP of $f_{\sigma}$) using noisy function $f$ in ([7](#S1.E7)). The detailed algorithm is given in [Algorithm 4](#alg4).

Figure: Algorithm 4 Perturbed Stochastic Gradient Descent with Quantum Mean Estimation

We now prove the performance guarantee for [Algorithm 4](#alg4), which is the formal version of [Theorem 3](#Thmtheorem3).

###### Theorem 12 (Formal version of Theorem 3 ) .

Suppose we have a target function $F$ and its noisy evaluation $f$ satisfying [Assumption 1](#Thmassumption1) with $\nu\leq O(\sqrt{\epsilon^{3}/\rho}\cdot(1/d))$. With probability at least $1-\delta$, [Algorithm 4](#alg4) finds an $\epsilon$-SOSP of $F$ satisfying ([4](#S1.E4)), using

$$ $\displaystyle\tilde{O}\left(\frac{d^{2.5}}{\epsilon^{3.5}}\cdot\operatorname{poly}(\Delta_{f},\ell,\rho)\right)$ (57) $$

queries to $U_{f}$ in ([7](#S1.E7)), under the following parameter choices:

$$ $\displaystyle\eta=\frac{1}{\ell^{\prime}},\quad\delta_{0}=\frac{\delta\epsilon^{\prime 2}}{16\ell^{\prime}\Delta_{f}}\chi^{-4},\quad r=\epsilon^{\prime}\chi^{-3}c^{-6},\quad\mathscr{T}=\frac{\chi c}{\eta\sqrt{\rho^{\prime}\epsilon^{\prime}}},\quad\mathscr{F}=\sqrt{\frac{\epsilon^{\prime 3}}{\rho^{\prime}}}\chi^{-3}c^{-5},$ (58) $$

where $c$ is some large enough constant, $\Delta_{f}=f_{\sigma}(\mathbf{x}_{0})-f_{\sigma}(\mathbf{x}^{*})$ is the value between the initial point $\mathbf{x}_{0}$ and the global minima point $\mathbf{x}^{*}$, $\chi=\max\{1,\log(d\ell^{\prime}\Delta_{f}/\rho^{\prime}\epsilon^{\prime}\delta_{0})\}$, $\ell^{\prime}=O(\ell+\sqrt{\epsilon/\rho})$, and $\rho^{\prime}=O(\rho)$ are the smoothness and Hessian-Lipschitz parameters for $f_{\sigma}$, and $\epsilon^{\prime}=O(\epsilon/\sqrt{d})$ such that an $\epsilon^{\prime}$-SOSP of $f_{\sigma}$ is an $\epsilon$-SOSP of $F$.

###### Proof.

Notice that an $\epsilon$-SOSP of target function $F$ is an $O(\epsilon/\sqrt{d})$-SOSP of function $f_{\sigma}$, we only need to prove that [Algorithm 4](#alg4) converges to a $O(\epsilon/\sqrt{d})$-SOSP of $f_{\sigma}$ using $\tilde{O}(\ell Bd^{2.5}/\epsilon^{3.5})$ queries.

In each iteration, [Algorithm 4](#alg4) estimates the gradient $\nabla f_{\sigma}(\mathbf{x}_{t})$ using quantum mean estimation with $O(m)$ queries to the quantum evaluation oracle. According to [Lemma 11](#Thmlemma11), the stochastic gradient $\mathbf{g}(\mathbf{x}_{t};\mathbf{z}^{(i)})$ for $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$ is a random vector with mean $\nabla f_{\sigma}(\mathbf{x}_{t})$ and variance $\sigma_{0}^{2}=B^{2}/\sigma^{2}$. As we choose $\sigma=\sqrt{\epsilon/\rho d}$, we require

$$ $\displaystyle m$ $\displaystyle\geq O\left(\frac{\sqrt{d}(B/\sigma)}{\epsilon/\sqrt{d}}\log(\frac{d}{\delta_{0}})\right)$ (59) $\displaystyle=\tilde{O}(B\sqrt{\rho}\cdot\sqrt{\frac{d^{3}}{\epsilon^{3}}})$ (60) $$

queries to bound the error $\norm{\tilde{\nabla}f_{\sigma}(\mathbf{x}_{t})-\nabla f_{\sigma}(\mathbf{x}_{t})}\leq\epsilon^{\prime}/20\leq O(\epsilon/\sqrt{d}\cdot(1/20))$ with probability at least $1-\delta_{0}$ according to [Lemma 13](#Thmlemma13).

Next, [Algorithm 4](#alg4) employs the estimations of the gradient and the PGD to find an $\epsilon^{\prime}$-SOSP of $f_{\sigma}$. Recall that we choose $\sigma=O(\sqrt{\epsilon/\rho d})$ and $\nu=O(\sqrt{\epsilon^{3}/\rho}\cdot(1/d))$, $f_{\sigma}$ is thus $\ell^{\prime}$-smooth and $\rho^{\prime}$-Hessian Lipschitz, where

$$ $\displaystyle\ell^{\prime}$ $\displaystyle=O\left(\ell+\frac{\nu}{\sigma^{2}}\right)=O\left(\ell+\sqrt{\frac{\epsilon}{\rho}}\right),$ (61) $\displaystyle\rho^{\prime}$ $\displaystyle=O\left(\rho+\frac{\nu}{\sigma^{3}}\right)=O(\rho).$ (62) $$

We consider the number of queries required to find an $\epsilon^{\prime}$-SOSP of $f_{\sigma}$. We set the total iteration number to be:

$$ $\displaystyle T=3\max\left\{\frac{4\Delta_{f}}{\eta\epsilon^{\prime 2}},\frac{\Delta_{f}\mathscr{T}}{\mathscr{F}}\right\}.$ (63) $$

Similar to the proof in the previous section, we consider the two cases when a $\mathbf{x}_{t}$ is not local minima. Suppose for some iterations $\mathbf{x}_{t}$, we have $\nabla f_{\sigma}(\mathbf{x}_{t})\leq\epsilon^{\prime}$ and $\lambda_{\min}(\nabla^{2}f(\mathbf{x}_{t}))\leq-\sqrt{\rho^{\prime}\epsilon^{\prime}}$. The error probability of this assumption is given later. Under this assumption, the function value decreases for $\mathscr{F}$ after each $\mathscr{T}$ iterations according to [Lemma 9](#Thmlemma9). Therefore, the number of such iterations when [Lemma 9](#Thmlemma9) can be called is bounded by $T/3$ times,
for otherwise the function value will decrease greater than $\Delta_{f}=f_{\sigma}(\mathbf{x}_{0})-f_{\sigma}(\mathbf{x}^{*})$, which is impossible. The failure probability is composed of two parts: the failure probability for estimating the gradient in [Lemma 1](#Thmlemma1) and the failure probability for [Lemma 9](#Thmlemma9). In each iteration, the probability of failure is bounded by $2\delta_{0}$ according to the union bound. The overall probability that [Algorithm 3](#alg3) fails to indicate a negative curvature is upper bounded by

$$ $\displaystyle\frac{T}{3}\cdot 2\delta_{0}\leq\frac{\delta}{2}$ (64) $$

for any $\chi$.

Excluding the iterations that [Lemma 9](#Thmlemma9) is applied, we still have $2T/3$ iterations left. We now consider the iterations $\mathbf{x}_{t}$ with large gradients ${\nabla f_{\sigma}(\mathbf{x}_{t})}\geq\epsilon^{\prime}$. According to [Lemma 8](#Thmlemma8), the function value decreases by at least $\eta\epsilon^{\prime 2}/4$ with a probability of at least $1-\delta_{0}$ in each iteration. Thus there can be at most $T/3$ steps with large gradients, for otherwise, the function value will decrease greater than $\Delta_{f}$, which is impossible. The failure probability is bounded again by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\frac{\delta}{2}.$ (65) $$

In summary, with probability at least $1-\delta$, there are at most $T/3$ iterations within which the neighboring $\mathscr{T}$ iterations have small gradients but large negative curvatures, and at most $T/3$ iterations with large gradients. Therefore, the rest $T/3$ iterations must be $\epsilon$-SOSPs. The number of the queries is thus bounded by

$$ $\displaystyle T\leq\tilde{O}\left(\frac{\Delta_{f}\ell^{\prime}}{\epsilon^{\prime 2}}\cdot\chi^{4}\cdot m\right)=\tilde{O}\left(\frac{d^{2.5}}{\epsilon^{3.5}}\cdot\operatorname{poly}(\Delta_{f},\ell,\rho)\right).$ (66) $$

∎

[Theorem 12](#Thmtheorem12) provides a quantum upper bound $O(d^{2.5}/\epsilon^{3.5})$ in finding $\epsilon$-SOSPs of $F$ using noisy oracle $f$ at $\nu\leq O(\sqrt{\epsilon^{3}/\rho}\cdot 1/d)$ while the classical upper bound requires $O(d^{4}/\epsilon^{5})$ queries []. The essence of the speedup lies in the quadratic reduction provided by the quantum mean estimation in the mini-batch size $m$.

###### Definition 1 .

###### Lemma 10 (Lemma 13, Ref. [ 37 ] ) .

###### Lemma 11 (Lemma 14, Ref. [ 37 ] ) .

###### Lemma 12 .

###### Definition 2 .

###### Lemma 13 (Theorem 3.5, Ref. [ 23 ] ) .

###### Theorem 12 (Formal version of Theorem 3 ) .

###### Proof.

### 3.2 First-order Algorithm and Performance Guarantee

Consider a pair of functions $(F,f)$ satisfying [Assumption 2](#Thmassumption2) with a relatively large noise strength such that [Corollary 1](#Thmcorollary1) fails to apply. Recall that in the previous subsection we have implemented a Gaussian smoothing for the noisy zeroth-oracle defined in [Definition 1](#Thmdefinition1). Now, we introduce the Gaussian smoothing of the noisy gradient, which is defined as:

$$ $\displaystyle\nabla f_{\sigma}(\mathbf{x})\coloneqq\mathbb{E}_{\mathbf{z}}\big{[}\nabla f(\mathbf{x}+\mathbf{z})\big{]},\quad\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I).$ (67) $$

After permutating the expectation operator and the gradient operator, we obtain

$$ $\displaystyle\nabla f_{\sigma}(\mathbf{x})=\nabla\cdot\big{(}\mathbb{E}_{\mathbf{z}}[f(\mathbf{x}+\mathbf{z})]\big{)},$ (68) $$

which indicates that $f_{\sigma}(\mathbf{x})$ is a Gaussian smoothing of $f$. Similar to [Lemma 10](#Thmlemma10), we deduce the following property of $\nabla f_{\sigma}(\mathbf{x})$, which originally appeared in Ref. [].

###### Lemma 14 (Lemma 48, Ref. [ 37 ] ) .

Assume the function pair $(F,f)$ satisfies [Assumption 2](#Thmassumption2). The Gaussian smoothing $\nabla f_{\sigma}$ of the noisy gradient $\mathbf{g}=\nabla f$ satisfies:

- •
$f_{\sigma}(\mathbf{x})$ is $O(\ell+\tilde{\nu}/\sigma)$-smooth and $O(\rho+\tilde{\nu}/\sigma^{2})$-Hessian Lipschitz.
- •
The distances between the gradients and the Hessians of $f_{\sigma}$ and $F$ are bounded. In particular, we have $\norm{\nabla f_{\sigma}(\mathbf{x})-\nabla F(\mathbf{x})}\leq O(\rho d\sigma^{2}+\tilde{\nu})$ and $\norm{\nabla^{2}f_{\sigma}(\mathbf{x})-\nabla^{2}F(\mathbf{x})}\leq O(\rho\sqrt{d}\sigma+\tilde{\nu}/\sigma)$, respectively.

We can bound the deviation of $\nabla f_{\sigma}$ from $\nabla F$ and maintain the information about the local geometry of $F$, as well as guaranteeing that any $\tilde{\epsilon}$-SOSP $\mathbf{x}_{\text{SOSP}}$ of $f_{\sigma}$ is also an $\epsilon$-SOSP of $F$, by choosing a suitable Gaussian smoothing parameter $\sigma$. We optimize $F$ through the Gaussian smooth $f_{\sigma}$. According to [Lemma 14](#Thmlemma14), the gradients and the eigenvalues of Hessians of $F$ are bounded by:

$$ $\displaystyle\norm{\nabla F(\mathbf{x}_{\text{SOSP}})}\leq\rho d\sigma^{2}+\tilde{\nu}+\tilde{\epsilon},$ (69) $$

whereas

$$ $\displaystyle\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{\text{SOSP}}))$ $\displaystyle\geq\lambda_{\min}(\nabla^{2}f_{\sigma}(\mathbf{x}_{\text{SOSP}}))+\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{\text{SOSP}})-\nabla^{2}f_{\sigma}(\mathbf{x}_{\text{SOSP}}))$ $\displaystyle\geq-\sqrt{\left(\rho+\frac{\tilde{\nu}}{\sigma^{2}}\right)\tilde{\epsilon}}-\norm{\nabla^{2}f_{\sigma}(\mathbf{x}_{\text{SOSP}})-\nabla^{2}F(\mathbf{x}_{\text{SOSP}})}$ $\displaystyle\geq-\sqrt{\left(\rho+\frac{\tilde{\nu}}{\sigma^{2}}\right)\tilde{\epsilon}}-\left(\rho\sqrt{d}\sigma+\frac{\tilde{\nu}}{\sigma}\right).$ (70) $$

To guarantee that any $\tilde{\epsilon}$-SOSP of $f_{\sigma}$ is an $\epsilon$-SOSP of $F$, we only need the following set of inequalities to be satisfied (up to constant factors).

$$ $\displaystyle\rho\sqrt{d}\sigma+\frac{\tilde{\nu}}{\sigma}$ $\displaystyle\leq O(\sqrt{\rho\epsilon}),$ (71) $\displaystyle\rho d\sigma^{2}+\tilde{\nu}$ $\displaystyle\leq O(\epsilon),$ (72) $\displaystyle\left(\rho+\frac{\tilde{\nu}}{\sigma^{2}}\right)\tilde{\epsilon}$ $\displaystyle\leq O(\rho\epsilon).$ (73) $$

From ([71](#S3.E71)) and ([72](#S3.E72)), we can deduce that

$$ $\displaystyle\sigma$ $\displaystyle\leq O\left(\sqrt{\frac{\epsilon}{\rho d}}\right),$ (74) $\displaystyle\tilde{\nu}$ $\displaystyle\leq\sqrt{\rho\epsilon}\sigma=O\left(\frac{\epsilon}{\sqrt{d}}\right),$ (75) $\displaystyle\tilde{\epsilon}$ $\displaystyle\leq\frac{\rho\epsilon}{\left(\rho+\frac{\tilde{\nu}}{\sigma^{2}}\right)}=O\left(\frac{\epsilon}{\sqrt{d}}\right).$ (76) $$

Hence, an $O(\epsilon/\sqrt{d})$-SOSP of the Gaussian smoothing $f_{\sigma}$ is an $\epsilon$-SOSP of the target function $F$. Similar to [Assumption 1](#Thmassumption1), we now have to find an $O(\epsilon/\sqrt{d})$-SOSP for the Gaussian smoothing $f_{\sigma}$ through queries to first-order noisy oracle $\nabla f(\mathbf{x})$. To approximate the gradient $\nabla f_{\sigma}$, we sample from the stochastic gradient estimation $\mathbf{g}_{\sigma}(\mathbf{x};\mathbf{z})=\nabla f(\mathbf{x}+\mathbf{z})$, where $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$. As shown in Ref. [], the stochastic gradient has the following properties, which is similar to [Lemma 11](#Thmlemma11).

###### Lemma 15 (Lemma 53, Ref. [ 37 ] ) .

We denote $\mathbf{g}_{\sigma}(\mathbf{x};\mathbf{z})=\nabla f(\mathbf{x}+\mathbf{z})$ for a sample from the noisy oracle, where $\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}I)$. The following inequalities hold:

$$ $\displaystyle\mathbb{E}_{\mathbf{z}}[\mathbf{g}_{\sigma}(\mathbf{x};\mathbf{z})]=\nabla f_{\sigma}(\mathbf{x}),$ (77) $\displaystyle\Pr\left[\norm{\mathbf{g}_{\sigma}(\mathbf{x};\mathbf{z})-\nabla f_{\sigma}(\mathbf{x})}\geq t\right]\leq\exp(-Lt^{2}),\qquad\forall t>0.$ (78) $$

The second inequality indicates that $\mathbf{g}_{\sigma}(\mathbf{x};\mathbf{z})$ is a sub-Gaussian random variable with a tail $L$ (Recall that $L$ is the smoothness parameter of $f$ in [Assumption 2](#Thmassumption2)).

By a similar reduction to [Lemma 12](#Thmlemma12), we can deduce that the optimal sampling strategy requires

$$ $\displaystyle m\geq O\left(\frac{\sigma_{0}^{2}d}{\epsilon^{2}}\log(\frac{d}{\delta})\right)$ (79) $$

queries to approximate $\nabla f_{\sigma}(\mathbf{x})$ with accuracy $\epsilon$, where $\sigma_{0}=L$ according to [Lemma 15](#Thmlemma15). Quantumly, we can employ [Lemma 13](#Thmlemma13) and use only

$$ $\displaystyle m\geq O\left(\frac{\sqrt{d}\sigma_{0}}{\epsilon}\log(\frac{d}{\delta})\right)$ (80) $$

queries if given access to a quantum binary oracle defined in Eq. ([54](#S3.E54)), which can be constructed by one query to the first-order oracle defined in Eq. ([8](#S1.E8)). We propose a first-order version of PGD with stochastic gradient queries to the smoothed function $f_{\sigma}$ and quantum mean estimation in [Algorithm 5](#alg5).

Figure: Algorithm 5 First-order Perturbed Stochastic Gradient Descent with Quantum Mean Estimation.

The goal of [Algorithm 5](#alg5) is to find an $O(\epsilon/\sqrt{d})$-SOSP of the Gaussian smoothing $f_{\sigma}$. The number of queries required can be bounded by the following theorem, which is the formal version of [Theorem 4](#Thmtheorem4).

###### Theorem 13 (Formal version of Theorem 4 ) .

Suppose we have a target function $F$ and its noisy evaluation $f$ satisfying [Assumption 2](#Thmassumption2) with $\tilde{\nu}\leq O(\epsilon/\sqrt{d})$. With probability at least $1-\delta$, [Algorithm 5](#alg5) finds an $\epsilon$-SOSP of $F$ satisfying ([4](#S1.E4)), using

$$ $\displaystyle\tilde{O}\left(\frac{d^{2}}{\epsilon^{3}}\cdot\operatorname{poly}(\Delta_{f},\ell,\rho)\right)$ (81) $$

queries to $U_{\mathbf{g}}$ defined in Eq. ([8](#S1.E8)), under the following choices of parameters:

$$ $\displaystyle\eta=\frac{1}{\ell^{\prime}},\quad\delta_{0}=\frac{\delta\epsilon^{\prime 2}}{4\ell^{\prime}\Delta_{f}}\chi^{-4},\quad r=\epsilon^{\prime}\chi^{-3}c^{-6},\quad\mathscr{T}=\frac{\chi c}{\eta\sqrt{\rho^{\prime}\epsilon^{\prime}}},\quad\mathscr{F}=\sqrt{\frac{\epsilon^{\prime 3}}{\rho^{\prime}}}\chi^{-3}c^{-5},$ (82) $$

where $c$ is some large enough constant, $\Delta_{f}=f_{\sigma}(\mathbf{x}_{0})-f_{\sigma}(\mathbf{x}^{*})$ is the gap between the initial point $\mathbf{x}_{0}$ and the global minimum $\mathbf{x}^{*}$, and $\chi=\max\{1,\log(d\ell^{\prime}\Delta_{f}/\rho^{\prime}\epsilon^{\prime}\delta_{0})\}$. Here, $\ell^{\prime}$, $\rho^{\prime}$, and $\epsilon^{\prime}$ have the same definition as in [Theorem 12](#Thmtheorem12).

Similar to [Theorem 12](#Thmtheorem12), [Theorem 13](#Thmtheorem13) presents a polynomial reduction in the query complexity of oracles using quantum mean estimation. In particular, [Algorithm 5](#alg5) requires only $\tilde{O}(d^{2}/\epsilon^{3})$ queries to the first-order gradient oracles while its classical counterpart [] requires $\tilde{O}(d^{3}/\epsilon^{4})$.

###### Proof of Theorem 13 .

Since an $\epsilon$-SOSP of the target function $F$ is an $O(\epsilon/\sqrt{d})$-SOSP of function $f_{\sigma}$, we only need to prove that [Algorithm 5](#alg5) converges to an $O(\epsilon/\sqrt{d})$-SOSP of $f_{\sigma}$ using $\tilde{O}(d^{2}/\epsilon^{3})$ queries.

In each iteration, [Algorithm 5](#alg5) estimates the gradient $\nabla f_{\sigma}(\mathbf{x}_{t})$ via quantum mean estimation while using $O(m)$ queries to the quantum evaluation oracle in each mini-batch. According to Eq. ([80](#S3.E80)), we require the mini-batch size

$$ $\displaystyle m\geq O\left(\frac{\sqrt{d}L}{\epsilon/\sqrt{d}}\log(\frac{d}{\delta_{0}})\right)=\tilde{O}\left(\frac{d}{\epsilon}\right)$ (83) $$

to bound the error $\norm{\tilde{\nabla}f_{\sigma}(\mathbf{x}_{t})-\nabla f_{\sigma}(\mathbf{x}_{t})}\leq\epsilon^{\prime}/20\leq O(\epsilon/\sqrt{d}\cdot(1/20))$ with probability at least $1-\delta_{0}$.

Next, we consider the number of queries required to find an $\epsilon^{\prime}$-SOSP of $f_{\sigma}$. We set the total iteration number to be

$$ $\displaystyle T=3\max\left\{\frac{4\Delta_{f}}{\eta\epsilon^{\prime 2}},\frac{\Delta_{f}\mathscr{T}}{\mathscr{F}}\right\}.$ (84) $$

We repeat the procedure in the proof of [Theorem 12](#Thmtheorem12). Suppose for some iterations, the function has small gradients $\nabla f_{\sigma}(\mathbf{x}_{t})\leq\epsilon^{\prime}$ and large negative curvatures $\lambda_{\min}(\nabla^{2}f_{\sigma}(\mathbf{x}_{t}))\leq-\sqrt{\rho^{\prime}\epsilon^{\prime}}$. Under this assumption, the function value will decrease for $\mathscr{F}$ after each $\mathscr{T}$ iterations according to [Lemma 9](#Thmlemma9). Therefore, the number of such iterations is bounded by $T/3$, for otherwise the function value will decrease greater than $\Delta_{f}=f_{\sigma}(\mathbf{x}_{0})-f_{\sigma}(\mathbf{x}^{*})$, which is impossible. The failure probability of the above argument is bounded by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\delta/2.$ (85) $$

Except for the iterations where [Lemma 9](#Thmlemma9) is applied, we still have $2T/3$ iterations left. We now consider the iterations $\mathbf{x}_{t}$ with large gradients, i.e., ${\nabla f_{\sigma}(\mathbf{x}_{t})}\geq\epsilon^{\prime}$. According to [Lemma 8](#Thmlemma8), the function value decreases by at least $\eta\epsilon^{2}/4$ with a probability of at least $1-\delta_{0}$. Therefore, there can be at most $T/3$ steps with large gradients, for otherwise, the function value will decrease greater than $\Delta_{f}$, which is impossible. The failure probability of the above argument is again bounded by

$$ $\displaystyle\frac{T}{3}\cdot\delta_{0}\leq\delta/2.$ (86) $$

Therefore, we can deduce that with probability at least $1-\delta$, there are at most $T/3$ iterations within which the neighboring $\mathscr{T}$ iterations have small gradients but large negative curvatures, and at most $T/3$ iterations with large gradients. Hence, the rest $T/3$ iterations must be $\epsilon$-SOSPs. The number of queries can be bounded by

$$ $\displaystyle T\leq\tilde{O}\left(\frac{\Delta_{f}\ell}{\epsilon^{\prime 2}}\cdot\chi^{4}\cdot m\right)=\tilde{O}\left(\frac{d^{2}}{\epsilon^{3}}\cdot\operatorname{poly}(\Delta_{f},\ell,\rho)\right).$ (87) $$

∎

###### Lemma 14 (Lemma 48, Ref. [ 37 ] ) .

###### Lemma 15 (Lemma 53, Ref. [ 37 ] ) .

###### Theorem 13 (Formal version of Theorem 4 ) .

###### Proof of Theorem 13 .

## 4 Classical and Quantum Lower Bounds in d 𝑑 d

In this section, we prove the query complexity lower bounds in the dimension $d$ of the input. Intuitively, the lower bound is obtained by constructing a hard instance and calculating its worst-case query complexity.

### 4.1 Quasi-polynomial Lower Bound for Quantum Zeroth-order Methods

Figure: Figure 1: (a) The Sketch of the hard instance function for [Theorem 5](#Thmtheorem5). The left figure illustrates the construction in the domain and the right figure shows a two-dimensional example. (b) The construction of the hard instance function for [Theorem 8](#Thmtheorem8).
Refer to caption: /html/2212.02548/assets/x1.png

The constructions of our hard instances (as shown in [Figure 1](#S4.F1) (a)) are inspired by the idea that originally appeared in Ref. []. We first consider a “scale free” version of function pair $(F,f)$, where we assume $\rho=1$ and $\epsilon=1$. Denote $\sin\mathbf{x}:=(\sin(x_{1}),...,\sin(x_{d}))$ and $\mathbb{I}(A)$ as the indicator function that has value $1$ when $A$ is true and 0 0 otherwise. We set the constant $\mu=300$ and define the target function as

$$ $\displaystyle F(\mathbf{x}):=h(\sin\mathbf{x})+\norm{\sin\mathbf{x}}^{2},$ (88) $$

where $h(\mathbf{x}):=h_{1}(\mathbf{v}^{\top}\mathbf{x})\cdot h_{2}\left(\sqrt{\norm{\mathbf{x}}^{2}-(\mathbf{v}^{\top}\mathbf{x})^{2}}\right)$, and

$$ $\displaystyle h_{1}(x)=g_{1}(\mu x),\quad g_{1}(x)$ $\displaystyle=(-16\absolutevalue{x}^{5}+48x^{4}-48\absolutevalue{x}^{3}+16x^{2})\cdot\mathbb{I}\{\absolutevalue{x}<1\},$ (89) $\displaystyle h_{2}(x)=g_{2}(\mu x),\quad g_{2}(x)$ $\displaystyle=(3x^{4}+8\absolutevalue{x}^{3}+6x^{2}-1)\cdot\mathbb{I}\{\absolutevalue{x}<1\}.$ (90) $$

Here, the vector $\mathbf{v}$ is uniformly chosen from the $d$-dimensional unit sphere. In addition, we can split the domain into different regions upon which analysis and constructions are made separately:

- •
“ball” $\mathbb{B}(0,3/\mu)=\{\mathbf{x}\in\mathbb{R}^{d}:\norm{x}\leq 3/\mu\}$ is the $d$-dimensional hyperball with radius $3/\mu$.
- •
“band” $S_{\mathbf{v}}=\{\mathbf{x}\in\mathbb{B}(0,3/\mu):\expectationvalue{\sin\mathbf{x},\mathbf{v}}\leq\log d/\sqrt{d}\}$.

We provide the landscape of $F$ and the region division in [Figure 1](#S4.F1) (a). The above construction happens within a hyperball and we cannot fill the entire space $\mathbb{R}^{d}$ with hyperballs. Therefore, we embed this hyperball into a hypercube and add two regions.

- •
“hypercube” $H=[-\pi/2,\pi/2]^{d}$ is the $d$-dimensional hypercube with length $\pi$.
- •
“padding” $S_{2}=H-\mathbb{B}(0,3/\mu)$.

With the above construction, we can fill the space $\mathbb{R}^{d}$ using these hypercubes. Meanwhile, the noisy function $f$ is defined as

$$ $\displaystyle f(\mathbf{x})=\begin{cases}\|\sin\mathbf{x}\|^{2},\quad\mathbf{x}\in S_{\mathbf{v}},\\ F(\mathbf{x}),\quad\mathbf{x}\notin S_{\mathbf{v}}.\end{cases}$ (91) $$

The “band” region $S_{\mathbf{v}}$ is known as the non-informative region as any query to $f$ in this area will obtain no information regarding $\mathbf{v}$. Intuitively, the metric of the non-informative area approaches $1$ as $d$ increases according to the measure of concentration. It is hard for any algorithm (both classical and quantum) to find a point out of this region. In particular, the probability of classically querying a point on $S_{\mathbf{v}}$ is bounded below by

$$ $\displaystyle\frac{\text{Area}(S_{\mathbf{v}})}{\text{Area}(\mathbb{B}(0,3/\mu))}\geq 1-O(d^{-\log d})$ (92) $$

according to [Lemma 29](#Thmlemma29) in [Appendix A](#A1).The following properties hold for function pair according to Ref. [].

###### Lemma 16 (Lemma 33, Ref. [ 37 ] ) .

The function pair $(F,f)$ defined in ([88](#S4.E88)) and ([91](#S4.E91)) above satisfies:

- •
The value of $f$ in the non-informative region $S_{\mathbf{v}}$ is independent of $\mathbf{v}$.
- •
$\sup_{x\in S_{\mathbf{v}}}\norm{f-F}_{\infty}\leq\tilde{O}(1/d)$.
- •
$F$ has no $\epsilon$-SOSP in the non-informative region $S_{\mathbf{v}}$.
- •
$F$ is $O(d)$-bounded, $O(1)$-Hessian Lipschitz, and $O(1)$-gradient Lipschitz.

The hard instance in the above [Lemma 16](#Thmlemma16) has realized the $\tilde{O}(1/d)$ factor for the noise bound in [Theorem 5](#Thmtheorem5) and introduced the non-informative area. The next step is to scale the hard instance to reach the lower bound with
correct dependencies on $\rho$ and $\epsilon$. Given $\epsilon>0$ and $\rho>0$, we define the scaling functions

$$ $\displaystyle\tilde{F}(\mathbf{x})$ $\displaystyle\coloneqq\epsilon rF\left(\frac{\mathbf{x}}{r}\right),$ (93) $\displaystyle\tilde{f}(\mathbf{x})$ $\displaystyle\coloneqq\epsilon rf\left(\frac{\mathbf{x}}{r}\right),$ (94) $$

where $r=\sqrt{\epsilon/\rho}$, and the functions $F,f$ are defined in ([88](#S4.E88)) and ([91](#S4.E91)), respectively. The scaled regions corresponding to $\tilde{F}$ and $\tilde{f}$ are:

- •
“ball” $\mathbb{B}(0,3r/\mu)=\{\mathbf{x}\in\mathbb{R}^{d}:\norm{x}\leq 3/\mu\}$ is the $d$-dimensional hyperball with radius $3r/\mu$.
- •
“band” $\tilde{S}_{\mathbf{v}}=\{\mathbf{x}\in\mathbb{B}(0,3r/\mu):\expectationvalue{\sin(\mathbf{x}/r),\mathbf{v}}\leq\log d/\sqrt{d}\}$.

According to [Lemma 16](#Thmlemma16), the function pair $(\tilde{F},\tilde{f})$ satisfies [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\sqrt{\epsilon^{3}/\rho}\cdot 1/d)$, upon which we prove our quantum lower bound for finding an $\epsilon$-SOSP of the target function $\tilde{F}$ in ([93](#S4.E93)) taking queries to the noisy function $\tilde{f}$ in ([94](#S4.E94)). Formally, we provide the following theorem.

###### Theorem 14 (Formal version of Theorem 5 ) .

For any $B>0,\ell>0,\rho>0$, there exists an $\epsilon_{0}=\Theta(\min\{\ell^{2}/\rho,(B^{2}\rho/d^{2})^{1/3}\})$ such that for any $\epsilon\in(0,\epsilon_{0}]$, the function pair $(\tilde{F},\tilde{f})$ defined in ([93](#S4.E93)) and ([94](#S4.E94)) satisfies [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\sqrt{\epsilon^{3}/\rho}\cdot 1/d)$, and any quantum algorithm that only queries a quasi-polynomial $O(d^{\log(d)})$ times to the zeroth-order quantum oracle $U_{\tilde{f}}$ will fail with high probability to find an $\epsilon$-SOSP of $\tilde{F}$.

To prove [Theorem 14](#Thmtheorem14), we introduce some lemmas to construct a reduction of the problem. In particular, our goal is to transform the quantum lower bound on the unstructured search problem [, ] into a lower bound for the problem of finding an $\epsilon$-SOSP of $\tilde{F}$ considered in [Theorem 14](#Thmtheorem14). We discretize the problem via the following results on distributing exponentially many points on $\mathbb{S}^{d-1}$ in a uniform way such that the distances between each pair of points are at least $\delta$.

###### Lemma 17 (Lemma D.1, Ref. [ 43 ] ) .

For any constant $\delta\in\big{(}0,\frac{\log d}{2\sqrt{d}}\big{)}$, there exists a set $\Gamma=\{\mathbf{y}_{1},\mathbf{y}_{2},\ldots,\mathbf{y}_{N}\}$ of $N$ unit vectors in $\mathbb{R}^{d}$ such that

- •
$\forall\mathbf{y}_{i}\neq\mathbf{y}_{j}\in\Gamma$, $\|\mathbf{y}_{i}-\mathbf{y}_{j}\|\geq\delta$;
- •
$\forall\mathbf{z}\in\mathbb{S}^{d-1}$, there exists an $\mathbf{y}_{i}\in\Gamma$ such that $\|\mathbf{z}-\mathbf{y}_{i}\|\leq\delta$;
- •
$N\geq\big{(}\frac{1}{2\delta}+\frac{1}{2}\big{)}^{d}-\big{(}\frac{1}{2\delta}-\frac{1}{2}\big{)}^{d}$.

Inspired by Ref. [], we consider the following unstructured search problem which can be reduced to finding an $\epsilon$-SOSP of $\tilde{F}$ with polynomial overhead.

###### Problem 1 .

Consider a set $\Gamma$ of $N$ unit vectors in $\mathbb{R}^{d}$ satisfying [Lemma 17](#Thmlemma17), for an unknown unit vector $\mathbf{v}\in\Gamma$, we define $q\colon\Gamma\to\mathbb{R}^{d}$ as follows:

$$ $\displaystyle q(\mathbf{x})\coloneqq\begin{cases}\mathbf{v},\quad\langle\sin\mathbf{x},\mathbf{v}\rangle>\frac{\log d}{2\sqrt{d}},\\ \mathbf{0},\quad\text{otherwise}.\end{cases}$ (95) $$

The goal is to find $\mathbf{v}$ only with access to values of $q$.

We now present the reduction from [Problem 1](#Thmproblem1) to the problem of finding an $\epsilon$-SOSP of $\tilde{F}$ under the setting of [Theorem 14](#Thmtheorem14). To make the reduction more straightforward, we additionally introduce an intermediate function $\hat{q}(\mathbf{x})\colon\mathbb{B}(\mathbf{0},3/\mu)\to\mathbb{R}$ between $q$ and $f$. In particular, for any $\mathbf{x}\in\mathbb{B}(\mathbf{0},3/\mu)$, we use $\hat{\mathbf{y}}(\mathbf{x})$ to denote the vector $\mathbf{y}_{i}$ in $\Gamma$ such that the distance $\|\mathbf{x}/\|\mathbf{x}\|-\mathbf{y}_{i}\|$ is minimized. If more than one of such vectors exists, we choose the one with the smallest lower index. We define $\hat{q}(\mathbf{x})$ as

$$ $\displaystyle\hat{q}(\mathbf{x})\coloneqq\begin{cases}\|\sin\mathbf{x}\|^{2},\quad q(\hat{\mathbf{y}}(\mathbf{x}))=\mathbf{0},\\ F(\mathbf{x}),\quad\text{otherwise}.\end{cases}$ (96) $$

Similar to $f$, $\hat{q}$ also has a large “non-informative” region $\hat{S}_{\mathbf{v}}$ where the function value equals $\norm{\sin\mathbf{x}}^{2}$ and reveals no information about $\mathbf{v}$. Quantitatively, we can observe that $\hat{S}_{\mathbf{v}}=\{\mathbf{y}\in\mathbb{B}(\mathbf{0},3/\mu):g(\hat{\mathbf{y}}(\mathbf{x}))=\mathbf{0}\}$, and $\hat{q}$ has the following properties.

###### Lemma 18 .

The function $\hat{q}(\mathbf{x})$ defined in ([96](#S4.E96)) has the following properties:

- •
One query to $\hat{q}$ can be implemented using one query to $q$.
- •
Its non-informative region $\hat{S}_{\mathbf{v}}=\{\mathbf{y}\in\mathbb{B}(\mathbf{0},3/\mu):q(\hat{\mathbf{y}}(\mathbf{x}))=\mathbf{0}\}$ is a subset of $S_{\mathbf{v}}$, which is the non-informative region of $f$ defined in ([91](#S4.E91)).
- •
For any $\mathbf{x}\in\mathbb{B}(\mathbf{0},3/\mu)-S_{\mathbf{v}}$, we have $\hat{q}(\mathbf{x})=f(\mathbf{x})$.

###### Proof.

For the first property, one can observe that for any $\mathbf{x}\in\mathbb{B}(\mathbf{0},3/\mu)$, $\hat{q}(\mathbf{x})$ can be expressed as

$$ $\displaystyle\hat{q}(\mathbf{x})$ $\displaystyle=\norm{\sin\mathbf{x}}^{2}+h(\sin\mathbf{x})$ (97) $\displaystyle=\norm{\sin\mathbf{x}}^{2}+h_{1}(\langle q(\hat{\mathbf{y}}(\mathbf{x})),\mathbf{x}\rangle)\cdot h_{2}\big{(}\sqrt{\norm{\mathbf{x}}^{2}-\langle q(\hat{\mathbf{y}}(\mathbf{x})),\mathbf{x}\rangle^{2}}\big{)},$ (98) $$

which can be implemented using one query to $q(\mathbf{x})$.

For the second property, $\forall\mathbf{x}\in\hat{S}_{\mathbf{v}}$, the corresponding $\hat{\mathbf{y}}(\mathbf{x})$ satisfies $\langle\hat{\mathbf{y}}(\mathbf{x}),\mathbf{v}\rangle\leq\frac{\log d}{2\sqrt{d}}$. Since $\|\mathbf{x}/\|\mathbf{x}\|-\hat{y}(\mathbf{x})\|\leq\delta=\frac{\log d}{2\sqrt{d}}$ by [Lemma 17](#Thmlemma17), we deduce that $\langle\mathbf{x},\mathbf{v}\rangle\leq\langle\mathbf{x}/\|\mathbf{x}\|,\mathbf{v}\rangle\leq\log d/\sqrt{d}$, indicating $\mathbf{x}\in S_{\mathbf{v}}$.

The third property can be directly obtained from the second property.
∎

Next, we present the reduction from [Problem 1](#Thmproblem1) to the problem of finding an $\epsilon$-SOSP of $F$ under the setting of [Theorem 14](#Thmtheorem14) through the following lemma.

###### Lemma 19 .

Under the setting of [Theorem 14](#Thmtheorem14), with polynomial overhead [Problem 1](#Thmproblem1) can be reduced to the problem of finding an $\epsilon$-SOSP of $F$ defined in ([88](#S4.E88)) for any $\epsilon\in(0,\epsilon_{0}]$, using access to values of $f$ defined in ([91](#S4.E91)).

###### Proof.

Since one query to $\hat{q}$ can be implemented using one query to $q$ by [Lemma 18](#Thmlemma18), [Problem 1](#Thmproblem1) can be reduced to the problem of finding an $\mathbf{x}\in\mathbb{B}(0,3/\mu)$ satisfying $\hat{q}(\mathbf{x})\neq\norm{\sin\mathbf{x}}^{2}$, or equivalently, $\mathbf{x}\in\mathbb{B}(0,3/\mu)-\hat{S}_{\mathbf{v}}$, with only access to values of $\hat{q}$.

By [Lemma 18](#Thmlemma18), any $\epsilon$-SOSP of $F$, denoted $\mathbf{x}^{F}_{\text{SOSP}}$, satisfies

$$ $\displaystyle\mathbf{x}^{F}_{\text{SOSP}}\in\mathbb{B}(0,3/\mu)-S_{\mathbf{v}}\subseteq\mathbb{B}(0,3/\mu)-\hat{S}_{\mathbf{v}}.$ (99) $$

Therefore, we have reduced [Problem 1](#Thmproblem1) to the nonconvex optimization task.
∎

We can scale the “scale-free” hard instance $(F,f)$ to the hard instance $(\tilde{F},\tilde{f})$ satisfying [Assumption 1](#Thmassumption1) using ([93](#S4.E93)) and ([94](#S4.E94)). In particular, we introduce the following lemma, which originally appeared in Ref. [].

###### Lemma 20 (Appendix C.2, Ref. [ 37 ] ) .

For any $B>0,\ell>0,\rho>0$, there exists an $\epsilon_{0}=\Theta(\min\{\ell^{2}/\rho,(B^{2}\rho/d^{2})^{1/3}\})$ such that for any $\epsilon\in(0,\epsilon_{0}]$, there exists a function pair $(\tilde{F},\tilde{f})$ satisfying the assumptions in [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\sqrt{\epsilon^{3}/\rho}\cdot(1/d))$, so that with constant overhead the problem of finding an $\epsilon$-SOSP of $F$ defined in ([88](#S4.E88)) using only access to values of $f$ defined in ([91](#S4.E91)) can be reduced to the problem of finding an $\epsilon$-SOSP of $\tilde{F}$ using only access to values of $\tilde{f}$.

Equipped with [Lemma 20](#Thmlemma20),, we prove [Theorem 14](#Thmtheorem14)

###### Proof.

According to [Lemma 19](#Thmlemma19) and [Lemma 20](#Thmlemma20), there exists a function pair $(\tilde{F},\tilde{f})$ satisfying [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\sqrt{\epsilon^{3}/\rho}\cdot(1/d))$, such that with polynomial overhead [Problem 1](#Thmproblem1) can be reduced to the problem of finding an $\epsilon$-SOSP of $\tilde{F}$ using only access to values of $\tilde{f}$.

We divide the $N$ unit vectors in $\Gamma$ into two parts.

$$ $\displaystyle\Gamma_{1}$ $\displaystyle=\{\mathbf{x}\in\Gamma\colon q(\mathbf{x})=\mathbf{v}\}$ (100) $\displaystyle\Gamma_{0}$ $\displaystyle=\{\mathbf{x}\in\Gamma\colon q(\mathbf{x})=\mathbf{0}\}.$ (101) $$

We denote the size of the two parts as $N_{1}=\absolutevalue{\Gamma_{1}}$ and $N_{0}=\absolutevalue{\Gamma_{2}}$. Our goal is to find any $\mathbf{x}$ in the set $\Gamma_{1}$. Intuitively, under limitation $\delta\to 0$ and $\delta<\frac{\log d}{2\sqrt{d}}$, we can deduce that

$$ $\displaystyle\frac{N_{1}}{N}\sim\frac{2\text{Area}(\mathbb{B}(0,3/\mu)-S_{\mathbf{v}})}{\text{Area}(\mathbb{B}(0,3/\mu))}=O(d^{-\log d}).$ (102) $$

We bound the deviation of $N_{1}/N$ from $2\text{Area}(\mathbb{B}(0,3/\mu)-S_{\mathbf{v}})/\text{Area}(\mathbb{B}(0,3/\mu))$ when $\delta\neq 0$. For $S_{\mathbf{v}}$, we consider $S_{\mathbf{v}}^{\prime}$ the area that is the ”band” area along $\mathbf{v}$ within $\log d/2\sqrt{d}-\delta$ from $\mathbf{0}$. The border area of $S_{\mathbf{v}}$ out of $S_{\mathbf{v}}^{\prime}$ contains ignorable $O(\exp(-d))$ directions compared to $S_{\mathbf{v}}$ when $\delta\ll 1/\sqrt{d}$.

Even if we consider the boundary above, we can still derive the upper bound for $N_{1}/N$

$$ $\displaystyle\frac{N_{1}}{N}\leq\frac{2\text{Area}(\mathbb{B}(0,3/\mu)-S_{\mathbf{v}}^{\prime})}{\text{Area}(\mathbb{B}(0,3/\mu))}=O(d^{-\log d}).$ (103) $$

The inequality comes from the fact that $\delta\ll\operatorname{poly}(1/d)$ and the boundary area can only bring exponential deviation from the expectation value $2\text{Area}(\mathbb{B}(0,3/\mu)-S_{\mathbf{v}})/\text{Area}(\mathbb{B}(0,3/\mu))$.

With the fact that $N_{1}/N\leq O(d^{-\log d})$ is quasi-polynomially small, any quantum algorithm that solves [Problem 1](#Thmproblem1) with high probability requires query complexity at least $\Omega(\sqrt{N/N_{1}})=\Omega(d^{\log d})$ [, ].
∎

###### Lemma 16 (Lemma 33, Ref. [ 37 ] ) .

###### Theorem 14 (Formal version of Theorem 5 ) .

###### Lemma 17 (Lemma D.1, Ref. [ 43 ] ) .

###### Problem 1 .

###### Lemma 18 .

###### Proof.

###### Lemma 19 .

###### Proof.

###### Lemma 20 (Appendix C.2, Ref. [ 37 ] ) .

###### Proof.

### 4.2 Information-theoretic Limitation of Quantum Zeroth-order Methods

When the noise between $F$ and $f$ keeps increasing under [Assumption 1](#Thmassumption1), it can erase the landscape of target function $F$ in the worst case. As a result, when the noise rate is larger than a certain threshold, for any quantum algorithm we can find a hard instance on which it will fail with a large probability. We consider the same target function defined in Eq. ([88](#S4.E88)) with a different noisy function $f$. We apply the scaling in ([93](#S4.E93)) and ([94](#S4.E94)) as

$$ $\displaystyle F(\mathbf{x})=h(\sin\mathbf{x})+\norm{\sin\mathbf{x}}^{2},$ (104) $\displaystyle f(\mathbf{x})=\norm{\sin\mathbf{x}}^{2},$ (105) $\displaystyle\tilde{F}(\mathbf{x})=\epsilon rF\left(\frac{\mathbf{x}}{r}\right),\qquad\tilde{f}(\mathbf{x})=\epsilon rf\left(\frac{\mathbf{x}}{r}\right).$ (106) $$

Similar to [Lemma 16](#Thmlemma16), the following properties hold for the above hard instance $(\tilde{F},\tilde{f})$.

###### Lemma 21 (Appendix D.2, Ref. [ 37 ] ) .

The function pair $(F,f)$ defined in ([106](#S4.E106)) above satisfies:

- •
The values of $\tilde{f}$ in $\mathbb{B}(0,3/\mu)$ are independent of $\mathbf{v}$.
- •
$\sup_{x\in\mathbb{B}(0,3/\mu)}\norm{\tilde{f}-\tilde{F}}_{\infty}\leq\tilde{O}(\epsilon^{1.5}/\sqrt{\rho})$.
- •
$F$ is $B$-bounded, $O(\rho)$-Hessian Lipschitz, and $O(\ell)$-gradient Lipschitz.

We derive the following result concerning the hard instance $(\tilde{F},\tilde{f})$ in Eq. ([106](#S4.E106)), which is the formal version of [Theorem 6](#Thmtheorem6).

###### Theorem 15 (Formal version of Theorem 6 ) .

For any $B>0,\ell>0,\rho>0$, any $\epsilon\in(0,\epsilon_{0}]$ for some $\epsilon_{0}=\Theta(\min\{\ell^{2}/\rho,(B^{2}\rho/d^{2})^{1/3}\})$, and any possible quantum algorithm, we can choose a function pair $(\tilde{F},\tilde{f})$ with $\mathbf{v}$ defined in ([106](#S4.E106)) satisfying [Assumption 1](#Thmassumption1) with $\nu=\tilde{\Theta}(\sqrt{\epsilon^{3}/\rho})$ such that the quantum algorithm will fail with high probability to find an $\epsilon$-SOSP of $\tilde{F}$ given only access to $U_{\tilde{f}}$.

###### Proof.

As $\tilde{f}$ is independent of $\mathbf{v}$, neither quantum nor classical query can reveal any information on $\mathbf{v}$ and the $\epsilon$-SOSP of $\tilde{F}$. Any solutions output by any algorithm will be independent of $\mathbf{v}$ with probability $1$. Therefore, the probability of success must be independent of the number of iterations, which indicates that any algorithm cannot output an $\epsilon$-SOSP with probability more than a constant. Specifically, no algorithm can do better than random guessing in $\mathbb{B}(0,3/\mu)$ within this construction.
∎

We remark that the noise bound and its underlying intuition in the quantum case is the same as the classical case []. However, [Theorem 15](#Thmtheorem15) only indicates the classical and quantum algorithms have the same worst-case lower bound for some level of noise strength, and there is still a possible quantum speedup for solving specific instances $(F,f)$. In [Appendix D](#A4), we show a concrete example in which quantum tunneling walk [] can find an $\epsilon$-SOSP of $F$ using polynomial queries and proper initial states containing information of the landscape, while any classical algorithm requires exponential queries even given access to such information.

###### Lemma 21 (Appendix D.2, Ref. [ 37 ] ) .

###### Theorem 15 (Formal version of Theorem 6 ) .

###### Proof.

### 4.3 Proof of Theorem 7

Here, we use an information-theoretic approach to prove [Theorem 7](#Thmtheorem7), which indicates that if a classical algorithm can find an $\epsilon$-SOSP of $F$ for any function pair $(F,f)$ satisfying [Assumption 1](#Thmassumption1) with $\nu=\Omega(1/\operatorname{poly}(d))$, the query complexity is bounded by $\Omega(d/\log d)$.

In particular, we consider the target function $\tilde{F}$ defined by ([88](#S4.E88)) and ([93](#S4.E93)). As $\tilde{F}$ is $\rho$-Hessian Lipschitz and $\ell$-smooth, we can estimate the vector $\mathbf{v}$ within $\operatorname{poly}(\epsilon)$ distance under infinity norm(^3^33Here, we have ignored the dependence on $\ell$ and $\rho$ and regarded them as constants), which requires $d\log(1/\epsilon)$ bits of information. Furthermore, as the noisy zeroth-order oracle $\tilde{f}$ contains noise of strength $\nu=\Omega(1/\operatorname{poly}(d))$, each classical query reveals at most $O(\log(1/\delta))$ bits of information []. Therefore, any classical algorithm has to take at least

$$ $\displaystyle\Omega\left(\frac{d\log(1/\epsilon)}{\log(1/\delta)}\right)=\Omega\left(\frac{d}{\log d}\right)$ (107) $$

queries to the noisy oracle.

Moreover, Ref. [] shows even estimating a sub-gradient for a Lipschitz convex function within infinity norm $\epsilon=O(1/\operatorname{poly}(d))$ using zeroth-order oracle $f$ with noise rate $\nu=\Omega(1/\operatorname{poly}(d))$ requires $\Omega(d/\log d)$ classical queries. However, Jordan’s algorithm enables simultaneous queries to different points using a single oracle query. Thus, only $O(1)$ query to quantum oracle is required to estimate the sub-gradient, which provides the exponential speedup for quantum algorithms.

### 4.4 Lower Bound for First-order Methods

We now derive the lower bound for classical and quantum algorithms in finding $\epsilon$-SOSPs of target function $F$ through noisy function satisfying [Assumption 2](#Thmassumption2). We propose the following two theorems as two parts for the formal version of [Theorem 8](#Thmtheorem8). In the first part, we consider the case of adding noise such that for any quantum or classical algorithm we can find a hard instance that will make the algorithm fail with high probability, which is an analog of [Theorem 15](#Thmtheorem15) under [Assumption 2](#Thmassumption2). Formally, we have the following theorem

###### Theorem 16 (Formal version of Theorem 8 , Part I) .

For any $B>0,\ell>0,\rho>0$, any $\epsilon\in(0,\epsilon_{0}]$ for some $\epsilon_{0}=\Theta(\min\{\ell^{2}/\rho,(B^{2}\rho/d^{2})^{1/3}\})$, and any quantum or classical algorithm, we choose function pair $(\tilde{F},\tilde{f})$ with $\mathbf{v}$ defined in ([106](#S4.E106)) satisfies [Assumption 2](#Thmassumption2) with $\tilde{\nu}=\tilde{\Theta}(\epsilon/\sqrt{d})$ such that it will fail with high probability to find any $\epsilon$-SOSP of $\tilde{F}$ given only access to $U_{\mathbf{g}}$.

###### Proof.

We consider the same target function $\tilde{F}$ and noisy function $\tilde{f}$ in ([106](#S4.E106)). Except from the properties in [Lemma 21](#Thmlemma21), the noisy function $\tilde{f}$ is also smooth and $\norm{\nabla\tilde{f}-\nabla\tilde{F}}\leq\tilde{\Theta}(\epsilon/\sqrt{d})$. Therefore, the hard instance in ([106](#S4.E106)) also satisfies [Assumption 2](#Thmassumption2) with $\tilde{\nu}=\tilde{\Theta}(\epsilon/\sqrt{d})$. According to [Theorem 15](#Thmtheorem15), for any quantum and classical algorithm, we choose function pair $(\tilde{F},\tilde{f})$ with $\mathbf{v}$ such that it will success with probability no more than a constant to find any $\epsilon$-SOSP of $\tilde{F}$ given only access to $U_{\tilde{\mathbf{g}}}$.
∎

Next, we consider the quasi-polynomial lower bound under [Assumption 2](#Thmassumption2). Unlike [Theorem 14](#Thmtheorem14), we cannot directly apply the hard instance $(F,f)$ defined in ([93](#S4.E93)) and ([94](#S4.E94)) because $f$ is not differentiable (or more strictly, not continuous). To address this problem, we construct a different noisy function $f$ (as shown in [Figure 1](#S4.F1) (b)). We start with the “scale free” version. We still set the $\mu=300$ and define the target function $F(\mathbf{x})=h(\sin\mathbf{x})+\norm{\sin\mathbf{x}}^{2}$, which is the same with ([88](#S4.E88)). We uniformly choose $\mathbf{v}$ and divide the “hypercube” into different regions as

- •
“hypercube” $H=[-\pi/2,\pi/2]^{d}$ is the $d$-dimensional hypercube with length $\pi$.
- •
“ball” $\mathbb{B}(0,3/\mu)=\{\mathbf{x}\in\mathbb{R}^{d}:\norm{x}\leq 3/\mu\}$ is the $d$-dimensional ball with radius $3/\mu$.
- •
“band” $S=\{\mathbf{x}\in\mathbb{B}(0,3/\mu):\expectationvalue{\sin\mathbf{x},\mathbf{v}}\leq w\}$ with $w=O(\log d/\sqrt{d})$.
- •
“non-informative band” $S_{\mathbf{v}}=\{\mathbf{x}\in\mathbb{B}(0,3/\mu):\expectationvalue{\sin\mathbf{x},\mathbf{v}}\leq 0.9w\}$.
- •
“padding” $S_{2}=H-\mathbb{B}(0,3/\mu)$.

Meanwhile, the noisy function $f$ is defined as

$$ $\displaystyle f(\mathbf{x})=\begin{cases}\|\sin\mathbf{x}\|^{2},\quad\mathbf{x}\in S_{\mathbf{v}},\\ \|\sin\mathbf{x}\|^{2}+h_{3}(\mathbf{x})\cdot h_{2}(\sqrt{\norm{\sin\mathbf{x}}^{2}-(\mathbf{v}^{\top}\sin\mathbf{x})^{2}}),\quad\mathbf{x}\in S-S_{\mathbf{v}}\\ F(\mathbf{x}),\quad\mathbf{x}\notin S,\end{cases}$ (108) $$

where

$$ $\displaystyle h_{3}(\mathbf{x})=h_{1}(\mathbf{v}^{\top}\sin(10\mathbf{x}-9w\mathbf{v}/2)).$ (109) $$

By the chain rule of gradients we deduce the following lemma:

###### Lemma 22 .

The function pair $(F,f)$ defined in ([88](#S4.E88)) and ([108](#S4.E108)) satisfies:

- •
The value of $f$ in the non-informative region $S_{\mathbf{v}}$ is independent of $\mathbf{v}$. $f$ is differentiable and satisfies the Lipshitz condition.
- •
$\sup_{x\in S}\norm{\nabla f-\nabla F}_{\infty}\leq\tilde{O}(1/\sqrt{d})$.
- •
$F$ has no $\epsilon$-SOSP in the non-informative region $S_{\mathbf{v}}$.
- •
$F$ is $O(d)$-bounded, $O(1)$-Hessian Lipschitz, and $O(1)$-gradient Lipschitz.

We apply the scaled version of $f$ as

$$ $\displaystyle\tilde{f}=\epsilon rf\left(\frac{\mathbf{x}}{r}\right).$ (110) $$

Based on the hard instance $(\tilde{F},\tilde{f})$ defined in ([93](#S4.E93)), ([108](#S4.E108)) and ([110](#S4.E110)). We propose the following theorem.

###### Theorem 17 (Formal version of Theorem 8 , Part II) .

For any $B>0,\ell>0,\rho>0$, there exists $\epsilon_{0}=\Theta(\min\{\ell^{2}/\rho,(B^{2}\rho/d^{2})^{1/3}\})$ such that for any $\epsilon\in(0,\epsilon_{0}]$, the function pair $(\tilde{F},\tilde{f})$ defined in ([93](#S4.E93)), ([108](#S4.E108)) and ([110](#S4.E110)) satisfies [Assumption 2](#Thmassumption2) with $\tilde{\nu}=\tilde{\Theta}(\epsilon/\sqrt{d})$, and any quantum or classical algorithm that only requires a quasi-polynomial number $\Omega(d^{\log(d)})$ queries to function values of $\tilde{f}$ will fail with high probability, to find an $\epsilon$-SOSP of $\tilde{F}$.

###### Proof.

According to [Lemma 22](#Thmlemma22) and [Lemma 20](#Thmlemma20), the width of non-informative band is $0.9w=\tilde{\Theta}(\epsilon/\sqrt{d})$. Then we can directly apply the similar procedure when we prove [Theorem 5](#Thmtheorem5) as the non-informative band has the same width scaling.
∎

###### Theorem 16 (Formal version of Theorem 8 , Part I) .

###### Proof.

###### Lemma 22 .

###### Theorem 17 (Formal version of Theorem 8 , Part II) .

###### Proof.

## 5 Classical and Quantum Lower Bounds in ϵ italic-ϵ \epsilon

In this section, we prove classical randomized lower bounds and quantum lower bounds in $\epsilon$ for finding an $\epsilon$-SOSP of an objective function $F$ given access to noisy classical or quantum zeroth- or first-order oracles, where $F\colon\mathbb{R}^{d}\to\mathbb{R}$ is $\ell$-smooth and $\rho$-Hessian Lipschitz, and satisfies

$$ $\displaystyle F(\mathbf{0})-\inf_{\mathbf{x}}F(\mathbf{x})\leq\Delta,$ (111) $$

for some constant $\Delta$.

### 5.1 Hard Instance for Deterministic Classical Algorithms

We first discuss the construction and intuition of hard instances upon which we can obtain lower bound results for deterministic classical algorithms. Consider the toy example proposed by Nesterov [, Chapter 2.1.2],

$$ $\displaystyle F(\mathbf{x})\coloneqq\frac{1}{2}(x_{1}-1)^{2}+\frac{1}{2}\sum_{i=1}^{T-1}(x_{i}-x_{i+1})^{2},$ (112) $$

whose gradient satisfies that

$$ $\displaystyle\forall 1<i<T,\quad\nabla_{i}F(\mathbf{x})=\mathbf{0}\Leftrightarrow x_{i-1}=x_{i}=x_{i+1}.$ (113) $$

Then, if we query the gradient of $F$ at a point with only its first $t$ entries being nonzero, the derivative can only reveal information about the $(t+1)$th direction, if one does not have knowledge about the directions of the coordinate axes. Formally, such properties can be summarized to consist of the concept of zero-chain, which is defined as follows.

###### Definition 3 (Definition 3, Ref. [ 16 ] ) .

A function $F\colon\mathbb{R}^{d}\to\mathbb{R}$ is called a zero-chain if for every $\mathbf{x}\in\mathbb{R}^{d}$,

$$ $\displaystyle\operatorname{supp}\{\mathbf{x}\}\subseteq\{1,\ldots,i-1\}\Rightarrow\operatorname{supp}\{\nabla f(\mathbf{x})\}\subseteq\{1,\ldots,i\},$ (114) $$

where the support of a vector $\mathbf{y}\in\mathbb{R}^{d}$ is defined as

$$ $\displaystyle\operatorname{supp}\{\mathbf{y}\}\coloneqq\{i\in[d]\,|\,y_{i}\neq 0\}.$ (115) $$

From an algorithmic perspective, if we encode $F(\mathbf{x})$ or any other $T$-dimensional zero chain into a $d$-dimensional space with $d\gg T$ and apply a random rotation $U$, any deterministic algorithm making fewer than $T$ queries will fail on certain instances to find the directions of all the $T$ axes. Hence, from an algorithmic perspective, if we can construct a $T$-dimensional zero chain with all SOSPs or even FOSPs overlapped with all the $T$ axes, we can establish an $\Omega(T)$ lower bound for all deterministic classical algorithms.

Following this intuition, Ref. [] provided a concrete hard instance construction to obtain an $\Omega(1/\epsilon^{2})$ lower bound for deterministic classical algorithms. In particular, Ref. [] first defined the following zero-chain $\bar{F}_{T;\mu}(\mathbf{x})\colon\mathbb{R}^{T+1}\to\mathbb{R}$:

$$ $\displaystyle\bar{F}_{T;\mu}(\mathbf{x})=\frac{\sqrt{\mu}}{2}(x_{1}-1)^{2}+\frac{1}{2}\sum_{i=1}^{T}(x_{i+1}-x_{i})^{2}+\mu\sum_{i=1}^{T}\Gamma(x_{i}),$ (116) $$

where the non-convex function $\Gamma\colon\mathbb{R}\to\mathbb{R}$ is defined as

$$ $\displaystyle\Gamma(x)=120\int_{1}^{x}\frac{t^{2}(t-1)}{1+t^{2}}\mathrm{d}t.$ (117) $$

According to [Lemma 26](#Thmlemma26) in [Appendix A](#A1), finding an FOSP requires knowledge about the directions of all the $T$ axes. We further apply a unitary rotation $U\in\mathbb{R}^{(T+1)\times d}$ and certain appropriate scaling to obtain the formal hard instance

$$ $\displaystyle\tilde{F}_{T;U}(\mathbf{x})\coloneqq\lambda\sigma^{2}\bar{F}_{T}\big{(}\langle\mathbf{x}/\sigma,\mathbf{u}^{(1)}\rangle,\langle\mathbf{x}/\sigma,\mathbf{u}^{(2)}\rangle,\ldots,\langle\mathbf{x}/\sigma,\mathbf{u}^{(T+1)}\rangle\big{)},$ (118) $$

where $\mathbf{u}^{(i)}$ stands for the $i$-th column of the rotation matrix $U$, and all its columns $\{\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(T+1)}\}$ forms a set of orthonormal vectors. We use $\tilde{\mathcal{F}}$ to denote the set of functions that can be presented in the form of ([118](#S5.E118)) for some suitable parameters $T,U,\lambda,$ and $\sigma$ whose function value at point $\mathbf{0}$ is not far from its minimum value, i.e.,

$$ $\displaystyle F(\mathbf{0})-\inf_{\mathbf{x}}F(\mathbf{x})\leq\Delta,\quad\forall F\in\tilde{\mathcal{F}}.$ (119) $$

Based on $\tilde{\mathcal{F}}$, we have the following classical lower bound result.

###### Lemma 23 (Theorem 2, Ref. [ 17 ] ) .

There exist numerical constants $c,C\in\mathbb{R}_{+}$ and $\ell_{q}\leq e^{\frac{3q}{2}\log q+Cq}$ for every $q\in\mathbb{N}$ such that, for any deterministic classical algorithm making at most

$$ $\displaystyle c\cdot\Delta\Big{(}\frac{L_{1}}{\ell_{1}}\Big{)}^{\frac{3}{7}}\Big{(}\frac{L_{2}}{\ell_{2}}\Big{)}^{\frac{2}{7}}\epsilon^{-12/7}$ (120) $$

gradient queries, there exists a function $\tilde{F}\in\tilde{\mathcal{F}}$ such that the output of this algorithm on $\tilde{F}$ is not an $\epsilon$-FOSP of $\tilde{F}$.

This lower bound regarding deterministic classical algorithms is, however, hard to be extended to randomized classical algorithms straightforwardly. Intuitively, the concept of zero-chain in [Definition 3](#Thmdefinition3) can be extended to higher-order derivatives, and the hard instance $\tilde{F}_{T;U}$ in ([118](#S5.E118)) is no longer a zero chain for derivatives of second- or higher-orders. Hence, the algorithm may benefit from adding random perturbations and may not need to discover all the $T+1$ components $\{\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(T+1)}\}$ one by one. To the best of our knowledge, it remains unclear whether the same lower bound result holds for randomized classical algorithms.

In the remaining part of this section, we will demonstrate that the presence of noise can drastically increase the hardness of finding an $\epsilon$-FOSP in the worst case. Specifically, we first derive the lower bound result for general noise models parameterized by the concept of noise radius $r_{0}$. Then, we discuss the values of $r_{0}$ in different settings with noisy zeroth-order oracle ([Assumption 1](#Thmassumption1)) or noisy first-order oracle ([Assumption 2](#Thmassumption2)), respectively.

###### Definition 3 (Definition 3, Ref. [ 16 ] ) .

###### Lemma 23 (Theorem 2, Ref. [ 17 ] ) .

### 5.2 Noisy Quantum Lower Bound with Bounded Input Domain

In this subsection, we first introduce the quantum lower bound on functions with bounded input domains. The intuition is that the noise can create a non-informative region around $\mathbf{0}$, which is a hyperball $\mathbb{B}(0,r_{0})$ whose certain radius $r_{0}$ depends on the noise rate. Then, if the dimension of $\tilde{F}_{T;U}$ defined in Eq. ([118](#S5.E118)) is large enough, any random perturbation with bounded norm will fall in $\mathbb{B}(0,r_{0})$ with an overwhelming probability, which leads to the fact that the lower bound in [Lemma 23](#Thmlemma23) additionally holds for not only randomized classical algorithms but also quantum algorithms.

We adopt the quantum query model introduced in []. For a $d$-dimensional objective function $F$, assume we have access to its noisy evaluation $f\colon\mathbb{R}^{d}\to\mathbb{R}$ via the following quantum oracle $O_{f}$,

$$ $\displaystyle O_{f}\ket{\mathbf{x}}\ket{\mathbf{y}}\to\ket{\mathbf{x}}\ket{\mathbf{y}\oplus\big{(}f(\mathbf{x}),\nabla f(\mathbf{x})\big{)}}.$ (121) $$

We remark that the oracle $O_{f}$ here is even stronger than the zeroth- or the first-order oracles in ([7](#S1.E7)) and ([8](#S1.E8)). Then, any quantum algorithm $A_{\operatorname{quantum}}$ making $q$ queries to $O_{f}$ can be described by the following sequence of unitaries

$$ $\displaystyle V_{q}O_{f}V_{q-1}O_{f}\cdots V_{1}O_{f}V_{0}$ (122) $$

applied to some initial state, say $\ket{0}$ without loss of generality. In the special case where the objective function $\tilde{F}_{T;U}\in\tilde{F}$, for the convenience of notation we denote $O_{f;T;U}$ to be the quantum oracle encoding its noisy evaluation $f_{r_{0};T;U}$ in the form of ([121](#S5.E121)). To obtain our quantum lower bound, we set the noisy function to be in the form

$$ $\displaystyle f_{r_{0};T;U}(\mathbf{x})\coloneqq\lambda\sigma^{2}\bar{F}_{T}\big{(}\langle\mathbf{x}/\sigma,\mathbf{u}^{(1)}\rangle,\ldots,\langle\mathbf{x}/\sigma,\mathbf{u}^{(\operatorname{prog}_{\sigma r_{0}}(\mathbf{x})+1}\rangle,0,\ldots,0\big{)},$ (123) $$

where $\operatorname{prog}_{\sigma r_{0}}(\mathbf{x})$ is defined as the largest index $j$ between $1$ and $T$ satisfying $|\langle\mathbf{x},\mathbf{u}^{(j)}\rangle|\geq\sigma r_{0}$. Moreover, we define the following indicator function

$$ $\displaystyle\delta_{r_{0}}(y)\coloneqq\mathbbm{1}\{|y|\geq r_{0}\}\cdot y.$ (124) $$

Intuitively, in the noisy function $f_{r_{0};T;U}$ we eliminate the influence of the $i$th component on the function when the overlap between $\mathbf{x}$ and $\mathbf{u}^{(i)}$ is smaller than certain threshold $r_{0}$. The detailed values of $r_{0}$ under different noise assumptions will be specified later. Hence, when the dimension $d$ is large enough, any random perturbation with a bounded norm will make no observable difference with an overwhelming probability. Moreover, we can note that $\epsilon$-FOSPs of $f_{r_{0};T;U}(\mathbf{x})$ and $\tilde{F}_{T;U}(\mathbf{x})$ are the same. Hence, one needs to identify all the $T$ components $\{\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(T)}\}$ to find an $\epsilon$-FOSP, which we demonstrate later that can only be done sequentially even by a quantum algorithm.

For any possible quantum algorithm $A_{\operatorname{quantum}}$ making $k<T$ queries in total, adopting a similar technique introduced in [, ], we define a sequence of unitaries starting with $A_{0}=A_{\operatorname{quantum}}$ as follows:

$$ $\displaystyle A_{0}:$ $\displaystyle=V_{k}O_{f;T;U}V_{k-1}O_{f;T;U}\cdots O_{f;T;U}V_{1}O_{f;T;U}V_{0}$ (125) $\displaystyle A_{1}:$ $\displaystyle=V_{k}O_{f;T;U}V_{k-1}O_{f;T;U}\cdots O_{f;T;U}V_{1}O_{f;1;U_{1}}V_{0}$ $\displaystyle A_{2}:$ $\displaystyle=V_{k}O_{f;T;U}V_{k-1}O_{f;T;U}\cdots O_{f;2;U_{2}}V_{1}O_{f;1;U_{1}}V_{0}$ $\displaystyle\vdots$ $\displaystyle A_{k}:$ $\displaystyle=V_{k}O_{f;k;U_{k}}V_{k-1}O_{f;k-1;U_{k-1}}\cdots O_{f;2;U_{2}}V_{1}O_{f;1;U_{1}}V_{0},$ $$

where $U_{t}\in\mathbb{R}^{d\times t}$ is defined as the orthogonal matrix with columns $\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(t)}$, and the function $f_{r_{0};t;U_{t}}(\mathbf{x})$ encoded in $O_{f;t;U_{t}}$ is defined as

$$ $\displaystyle f_{r_{0};t;U_{t}}\coloneqq\lambda\sigma^{2}\bar{F}_{T}\big{(}\langle\mathbf{x}/\sigma,\mathbf{u}^{(1)}\rangle,\ldots,\langle\mathbf{x}/\sigma,\mathbf{u}^{(\operatorname{prog}_{\sigma r_{0}}^{t}(\mathbf{x})+1}\rangle,0,\ldots,0\big{)},$ (126) $$

where $\operatorname{prog}_{\sigma r_{0}}^{t}(\mathbf{x})$ is defined as the largest index $j$ between $1$ and $t-1$ satisfying $|\langle\mathbf{x},\mathbf{u}^{(j)}\rangle|\geq\sigma r_{0}$. Our goal is to demonstrate that $A_{0}$ will fail to find an $\epsilon$-FOSP with high probability. To do so, we employ a hybrid argument showing that the outputs of $A_{i}$ and $A_{i+1}$ defined in the sequence ([125](#S5.E125)) are close for every $i<k$, so does the outputs of $A_{0}$ and $A_{k}$, which cannot solve the problem with high probability since it contains no information of the $T$-th component, which is necessary for finding an $\epsilon$-FOSP with high success probability.

###### Lemma 24 ( $A_{t}$ and $A_{t-1}$ have similar outputs) .

Consider the hard instance $\tilde{F}_{T;U}(\mathbf{x})\colon\mathbb{R}^{d}\to\mathbb{R}$ defined in ([116](#S5.E116)) with domain $\mathbb{B}(0,2\sigma\sqrt{T})$ and its noisy evaluation $f_{r_{0};T;U}$ defined in ([123](#S5.E123)) with $d\geq 4T$, let $A_{t}$ for $t\in[k-1]$ be the unitaries defined in Eq. ([125](#S5.E125)). Then

$$ $\displaystyle\mathbb{E}_{U}\big{(}\|A_{t}\ket{\mathbf{0}}-A_{t-1}\ket{\mathbf{0}}\|^{2}\big{)}\leq 8Te^{-dr_{0}^{2}/(4T)}.$ (127) $$

###### Proof.

From the definition of the unitaries in Eq. ([125](#S5.E125)) and the unitary invariance of the spectral norm, we have

$$ $\displaystyle\|A_{t}\ket{\mathbf{0}}-A_{t-1}\ket{\mathbf{0}}\|=\big{\|}(O_{f;t;U_{t}}-O_{f;T;U})V_{t-1}O_{f;t-1;U_{t-1}}\cdots O_{f;1;U_{1}}V_{0}\ket{\mathbf{0}}\big{\|}.$ (128) $$

We will prove the claim for any fixed choice of vectors $\{\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(t-1)}\}$, which will imply the claim for any distribution over those vectors. Let us prove the claim for any fixed choice of vectors $\{\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(t-1)}\}$, which will imply the claim for any distribution over those vectors. Once we have fixed these vectors, the state $V_{t-1}O_{f;t-1;U_{t-1}}\cdots O_{f;1;U_{1}}V_{0}\ket{\mathbf{0}}$ is a fixed state, which can be referred to as $\ket{\psi}$. Thus our problem reduces to showing for all quantum states $\ket{\psi}$,

$$ $\displaystyle\mathbb{E}_{\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}}\big{(}\|(O_{f;t;U_{t}}-O_{f;T;U})\ket{\psi}\|^{2}\big{)}\leq 8Te^{-dr_{0}^{2}/(4T)}.$ (129) $$

We write the state $\ket{\psi}$ as $\ket{\psi}=\sum_{\mathbf{x}}\alpha_{\mathbf{x}}\ket{\mathbf{x}}\ket{\phi_{\mathbf{x}}}$, where $\mathbf{x}$ is the query made to the oracle, and $\sum_{\mathbf{x}}|\alpha_{\mathbf{x}}|^{2}=1$. Hence, the left-hand side of Eq. ([129](#S5.E129)) equals

$$ $\displaystyle\mathbb{E}_{\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}}\Big{(}\Big{\|}\sum_{\mathbf{x}}\alpha_{\mathbf{x}}(O_{f;t;U_{t}}-O_{f;T;U})\ket{\mathbf{x}}\ket{\phi_{\mathbf{x}}}\Big{\|}^{2}\Big{)}$ (130) $\displaystyle\qquad\leq\sum_{\mathbf{x}}|\alpha_{\mathbf{x}}|^{2}\cdot\mathbb{E}_{\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}}\big{(}\big{\|}(O_{f;t;U_{t}}-O_{f;T;U})\ket{\mathbf{x}}\big{\|}^{2}\big{)}.$ (131) $$

Since $|\alpha_{\mathbf{x}}|^{2}$ defines a probability distribution over $\mathbf{x}$, we can again upper bound the right-hand side for any $\mathbf{x}$ instead. Note that $O_{f;t;U_{t}}$ and $O_{f;T;U}$ behave identically for some inputs x, the only nonzero
terms are those where the oracles respond differently, which can only happen if

$$ $\displaystyle\big{(}f_{r_{0};t;U_{t}}(\mathbf{x}),\nabla f_{r_{0};t;U_{t}}(\mathbf{x})\big{)}\neq\big{(}f_{r_{0};T;U}(\mathbf{x}),\nabla f_{r_{0};T;U}(\mathbf{x})\big{)}.$ (132) $$

When the response is different, we can upper bound $\big{\|}(O_{f;t;U_{t}}-O_{f;T;U})\ket{\mathbf{x}}\|^{2}$ by $4$ using the triangle inequality. Thus for any $\mathbf{x}\in\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})$, we have

$$ $\displaystyle\mathbb{E}_{\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}}\big{[}\big{\|}(O_{f;t;U_{t}}-O_{f;T;U})\ket{\mathbf{x}}\big{\|}^{2}\big{]}$ (133) $\displaystyle\qquad\leq 4\Pr_{\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}}\big{[}\big{(}f_{r_{0};t;U_{t}}(\mathbf{x}),\nabla f_{r_{0};t;U_{t}}(\mathbf{x})\big{)}\neq\big{(}f_{r_{0};T;U}(\mathbf{x}),\nabla f_{r_{0};T;U}(\mathbf{x})\big{)}\big{]}.$ (134) $$

We use $\mathbf{x}_{\perp}$ to denote the projection of $\mathbf{x}$ to the span $\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}$. Intuitively, as long as each component of $\mathbf{x}_{\perp}$ has absolute value smaller than $\sigma r_{0}$, the components $\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}$ will have no observable impact. Quantitatively,

$$ $\displaystyle\Pr[\big{(}f_{r_{0};t;U_{t}}(\mathbf{x}),\nabla f_{r_{0};t;U_{t}}(\mathbf{x})\big{)}\neq\big{(}f_{r_{0};T;U}(\mathbf{x}),\nabla f_{r_{0};T;U}(\mathbf{x})\big{)}\big{]}$ (135) $\displaystyle\qquad\leq 1-\Pr[|\langle\mathbf{u}^{(t)},\mathbf{x}\rangle|,\ldots,|\langle\mathbf{u}^{(T)},\mathbf{x}\rangle|\leq\delta r_{0}\big{]}.$ (136) $$

Since $\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}$ are chosen uniformly at random in the $(d-t+1)$-dimensional orthogonal complement of span $\{\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(t-1)}\}$, for any $t\leq i\leq T$, by [Lemma 29](#Thmlemma29) we can further derive that

$$ $\displaystyle\Pr[|\langle\mathbf{u}^{(i)},\mathbf{x}\rangle|>r_{0}\big{]}\leq 2e^{-dr_{0}^{2}/(4T)},$ (137) $$

which leads to

$$ $\displaystyle\Pr[|\langle\mathbf{u}^{(t)},\mathbf{x}\rangle|,\ldots,|\langle\mathbf{u}^{(T)},\mathbf{x}\rangle|\leq r_{0}\big{]}$ $\displaystyle\geq\big{(}1-2e^{-dr_{0}^{2}/(4T)}\big{)}^{T}\geq 1-2Te^{-dr_{0}^{2}/(4T)},$ (138) $$

indicating

$$ $\displaystyle\mathbb{E}_{\{\mathbf{u}^{(t)},\ldots,\mathbf{u}^{(T)}\}}\big{[}\big{\|}(O_{f;t;U_{t}}-O_{f;T;U})\ket{\mathbf{x}}\big{\|}^{2}\big{]}\leq 8Te^{-dr_{0}^{2}/(4T)},$ (139) $$

and

$$ $\displaystyle\mathbb{E}_{U}\big{(}\|A_{t}\ket{\mathbf{0}}-A_{t-1}\ket{\mathbf{0}}\|^{2}\big{)}\leq 8Te^{-dr_{0}^{2}/(4T)}.$ (140) $$

∎

###### Proposition 1 .

Consider the $d$-dimensional function $\tilde{f}_{T;U}(\mathbf{x})\colon\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})\to\mathbb{R}$ defined in ([118](#S5.E118)) with the rotation matrix $U$ being chosen arbitrarily. Consider any quantum algorithm $A_{\operatorname{quantum}}$ containing $t<T$ queries to the noisy oracle $O_{f}$ defined in Eq. ([121](#S5.E121)), let $p_{U}$ be the probability distribution over $\mathbf{x}\in\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})$ obtained by measuring the state $A_{\operatorname{quantum}}\ket{0}$, which is related to the rotation matrix $U$. Then,

$$ $\displaystyle\Pr_{U,\mathbf{x}_{\text{out}}\sim p_{U}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}\leq 16Te^{-dr_{0}^{2}/(8T)}.$ (141) $$

###### Proof.

Consider the sequence of unitaries $\{A_{0},\ldots,A_{t}\}$ associated with $A_{\operatorname{quantum}}$ defined in ([125](#S5.E125)), we first demonstrate that $A_{t}$ cannot find a point with small gradient with high probability. In particular, let $p_{U}^{(t)}$ be the probability distribution over $\mathbf{x}\in\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})$ obtained by measuring the output state $A_{t}\ket{0}$. Then we have

$$ $\displaystyle\Pr_{U_{t},\mathbf{x}_{\text{out}}\sim p_{U_{t}}^{(t)}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}$ (142) $\displaystyle\quad\qquad\leq\max_{\mathbf{x}\in\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})}\Pr_{\{\mathbf{u}^{(t+1)},\ldots,\mathbf{u}^{(T+1)}\}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x})\|\leq\lambda\sigma\mu^{3/4}/8\big{]},$ (143) $$

whereby [Lemma 32](#Thmlemma32) we have

$$ $\displaystyle\Pr_{\{\mathbf{u}^{(t+1)},\ldots,\mathbf{u}^{(T+1)}\}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}\leq 8Te^{-dr_{0}^{2}/(8T)}$ (144) $$

for any $\mathbf{x}\in\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})$, which leads to

$$ $\displaystyle\Pr_{U_{t},\mathbf{x}_{\text{out}}\sim p_{U_{t}}^{(t)}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}\leq 8T^{2}e^{-dr_{0}^{2}/(4T)}.$ (145) $$

Moreover, by [Lemma 24](#Thmlemma24) and Cauchy-Schwartz inequality, we have

$$ $\displaystyle\mathbb{E}_{U}\big{[}\|A_{t}\ket{0}-A_{0}\ket{0}\|^{2}\big{]}\leq t\cdot\mathbb{E}_{U}\big{[}\sum_{k=1}^{t-1}\|A_{k+1}\ket{0}-A_{k}\ket{0}\|^{2}\big{]}\leq 8T^{2}e^{-dr_{0}^{2}/(4T)}.$ (146) $$

Then by Markov’s inequality,

$$ $\displaystyle\Pr_{U}\big{[}\|A_{t-1}\ket{0}-A_{0}\ket{0}\|^{2}\geq 4Te^{-dr_{0}^{2}/(8T)}\big{]}\leq 4Te^{-dr_{0}^{2}/(8T)},$ (147) $$

since both norms are at most 1. Hence, we can deduce that the total variance distance between $p_{U}$n and $p_{U}^{(t)}$ can be bounded by

$$ $\displaystyle 4Te^{-dr_{0}^{2}/(8T)}+4Te^{-dr_{0}^{2}/(8T)}\leq 8Te^{-dr_{0}^{2}/(8T)},$ (148) $$

which further leads to

$$ $\displaystyle\Pr_{U,\mathbf{x}_{\text{out}}\sim p_{U}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}$ (149) $\displaystyle\quad\qquad\leq\Pr_{U_{t},\mathbf{x}_{\text{out}}\sim p_{U_{t}}^{(t)}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}+8Te^{-dr_{0}^{2}/(8T)}\leq 16Te^{-dr_{0}^{2}/(8T)}.$ (150) $$

∎

###### Proposition 2 .

Let $r_{0},\Delta,L_{1},L_{2},\epsilon$ be positive and $\epsilon\leq L_{1}^{2}/L_{2}$. Then there exist positive numerical constants $c,C\in\mathbb{R}$ and $\ell_{q}\leq e^{\frac{3q}{2}\log q+Cq}$ for every $q\in\mathbb{N}$, and a set $\Omega$ consisting of function pairs $(\tilde{F}_{T;U},f_{r_{0};T;U})$ with $\tilde{F}_{T;U}$ and $f_{r_{0};T;U}$ defined in ([118](#S5.E118)) and ([123](#S5.E123)) respectively upon the input domain $\mathbb{B}(\mathbf{0},\mathcal{R})$ with

$$ $\displaystyle T=\frac{\Delta}{20}\Big{(}\frac{L_{2}}{\ell_{2}}\Big{)}^{\frac{5}{4}}\Big{(}\frac{L_{1}}{2\ell_{1}}\Big{)}^{\frac{3}{7}}(8\epsilon)^{-12/7},\qquad\mathcal{R}=2\sqrt{T}\cdot\Big{(}\frac{L_{2}}{\ell_{2}}\Big{)}^{-3/4}\Big{(}\frac{L_{1}}{\ell_{1}}\Big{)}^{-1/7}(8\epsilon)^{4/7},$ (151) $$

such that, for any quantum algorithm $A_{\operatorname{quantum}}$ making fewer than $T$ queries to the oracle $O_{f}$ in the form of ([121](#S5.E121)) encoding the function values and gradients of $f_{r_{0};T;U}$ in ([123](#S5.E123)), there exists an orthogonal matrix $U$ such that, $A_{\operatorname{quantum}}$ cannot find an $\epsilon$-FOSP of the corresponding $\tilde{F}_{T;U}$ with probability larger than, where $\tilde{F}_{T;U}$ is $L_{1}$-smooth and $L_{2}$-Hessian Lipschitz and satisfies

$$ $\displaystyle\tilde{F}_{T;U}(\mathbf{0})-\inf_{\mathbf{x}}\tilde{F}_{T;U}(\mathbf{x})\leq\Delta.$ (152) $$

###### Proof.

We set the scaling parameters $\lambda$, $\sigma$ in $\tilde{F}_{T;U}$ and $f_{r_{0};T;U}$ to be

$$ $\displaystyle\lambda=\frac{L_{1}}{2\ell_{1}},\qquad\mu=\frac{L_{2}\sigma}{\lambda\ell_{2}},\qquad\sigma=\Big{(}\frac{L_{2}}{\ell_{2}}\Big{)}^{-3/4}\lambda^{-1/7}(8\epsilon)^{4/7},$ (153) $$

which satisfy $\mu\leq 1$ since $\epsilon\leq L_{1}^{2}/L_{2}$. By [Proposition 1](#Thmproposition1), for any possible quantum algorithm $A_{\operatorname{quantum}}$ making $t<T$ queries to the oracle $O_{f}$ defined in ([121](#S5.E121)) encoding $(f_{r_{0};U;T},\nabla f_{r_{0};U;T})$, we have

$$ $\displaystyle\Pr_{U,\mathbf{x}_{\text{out}}\sim p_{U}}\big{[}\|\nabla\tilde{f}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}=\Pr_{U,\mathbf{x}_{\text{out}}\sim p_{U}}\big{[}\|\nabla\tilde{f}_{T;U}(\mathbf{x}_{\text{out}})\|\leq\epsilon\big{]}\leq 16Te^{-dr_{0}^{2}/(8T)},$ (154) $$

where $p_{U}$ is the probability distribution over $\mathbf{x}\in\mathbb{B}(\mathbf{0},2\sigma\sqrt{T})$ obtained by measuring the state $A_{\operatorname{quantum}}\ket{0}$, indicating that the success probability of $A_{\operatorname{quantum}}$ finding an $\epsilon$-FOSP of $\tilde{F}_{T;U}$ is at most $16Te^{-dr_{0}^{2}/(8T)}$.
Moreover, by [Lemma 27](#Thmlemma27) we can derive that, for any $T\times d$ orthogonal matrix $U$, the function $\tilde{F}_{T;U}$ is $(1+\mu)\ell_{1}=L_{1}$-smooth and $\lambda\mu\ell_{2}/\sigma=L_{2}$-Hessian Lipschitz, with

$$ $\displaystyle\tilde{F}_{T;U}(\mathbf{0})-\inf_{\mathbf{x}}\tilde{F}_{T;U}(\mathbf{x})\leq\lambda\sigma^{2}\Big{(}\frac{\sqrt{\mu}}{2}+10\mu T\Big{)}\leq\Delta.$ (155) $$

∎

[Proposition 2](#Thmproposition2) shows that, if we restrict the input domain of the function pair $(F,f)$ to a hyperball with radius $\mathcal{R}$, in the worst case every quantum algorithm has to make at least $\Omega\big{(}\epsilon^{-12/7}\big{)}$ queries to the noisy evaluation $f$ to find an $\epsilon$-FOSP of $F$ with high probability. Moreover, the dimension $d$ of the hard instance achieving this lower bound is of order $\Omega\big{(}\epsilon^{-12/7}\log(1/\epsilon)/r_{0}^{2}\big{)}$, where the noise radius $r_{0}$ is determined by the noise rate with different relations under different noise assumptions, on which a detailed discussion is given in [Section 5.4](#S5.SS4) after we extend this lower bound to unbounded input domain in [Section 5.3](#S5.SS3).

###### Lemma 24 ( A t subscript 𝐴 𝑡 A_{t} and A t − 1 subscript 𝐴 𝑡 1 A_{t-1} have similar outputs) .

###### Proof.

###### Proposition 1 .

###### Proof.

###### Proposition 2 .

###### Proof.

### 5.3 Noisy Quantum Lower Bound with Unbounded Input Domain

In this subsection, we extend the quantum lower bound proved in [Proposition 2](#Thmproposition2) to functions with an unbounded input domains. In particular, Ref. [] introduced a method for extending lower bound to unbounded input domain by adding a scaling term on the input vector and additionally introducing a quadratic term. The intuition is that, if the input vector has a large norm, the corresponding function value is almost solely determined by the quadratic term and it cannot be an approximate stationary point. Hence, it is not beneficial for any classical algorithm to explore any point outside a certain bounded region, indicating that the lower bound with an unbounded input domain is the same as the one with a bounded input domain. The same argument also holds for quantum algorithms, as shown in Ref. [].

Quantitatively, we consider the following $T+1$ dimensional kernel function defined on $\mathbb{R}^{T+1}$,

$$ $\displaystyle\bar{\mathfrak{F}}_{T;\mu}(\mathbf{x})\coloneqq\bar{F}_{T;\mu}(\gamma_{\alpha}(\mathbf{x}))+\beta\|\sin\mathbf{x}\|^{2},$ (156) $$

where $\gamma_{\alpha}(\mathbf{x})$ is defined as

$$ $\displaystyle\gamma_{\alpha}(\mathbf{x})\coloneqq\begin{cases}\Big{(}1-\frac{\|\mathbf{x}\|}{\alpha\sqrt{T}}\Big{)}^{3}\cdot\mathbf{x},\quad\|\mathbf{x}\|\leq\alpha\sqrt{T},\\ \mathbf{0},\quad\|\mathbf{x}\|>\alpha\sqrt{T}.\end{cases}$ (157) $$

By [Lemma 28](#Thmlemma28), finding an $\epsilon$-SOSP or even an $\epsilon$-FOSP of $\bar{\mathfrak{F}}_{T;\mu}$ requires knowledge of all the $T+1$ coordinate directions, if it is projected to a $d$-dimensional space via an arbitrary orthogonal matrix $U\in\mathbb{R}^{d\times(T+1)}$. Moreover, to guarantee that the hard instance satisfies the $B$-boundedness condition required in the empirical risk setting considered in this paper, we additionally add a sine function to the quadratic term and obtain the following hard instance defined on the hypercube $[-\pi\mathcal{L}/2,\pi\mathcal{L}/2]^{d}$ with $\mathcal{L}=\zeta\alpha\sqrt{T}$ for some constant $\zeta\geq 2$,

$$ $\displaystyle\hat{\mathfrak{F}}_{T;U}(\mathbf{x})\coloneqq\bar{F}_{T;\mu}\big{(}\gamma_{\alpha}(U^{T}\mathbf{x})\big{)}+\beta\mathcal{L}^{2}\|\sin(\mathbf{x}/\mathcal{L})\|^{2},$ (158) $$

where the constants $\alpha,\beta$ are chosen according to [Lemma 28](#Thmlemma28), and for any $\mathbf{y}\in\mathbb{R}^{d}$, $\sin\mathbf{y}$ is defined as

$$ $\displaystyle\sin\mathbf{y}\coloneqq(\sin y_{1},\ldots,\sin y_{d})^{T}.$ (159) $$

###### Lemma 25 .

Consider the function $\hat{\mathfrak{F}}_{T;U}\colon[-\pi\mathcal{L}/2,\pi\mathcal{L}/2]^{d}\to\mathbb{R}$ defined in Eq. ([158](#S5.E158)), suppose that the parameter $\mu$ satisfies $\mu\leq 1$. Then, there exist positive constants $\alpha,\beta,\zeta$ such that

- 1.
For any $\mathbf{x}\in[-2\zeta\alpha\sqrt{T},2\zeta\alpha\sqrt{T}]^{d}$ such that
$\displaystyle|\langle\mathbf{x},\mathbf{u}^{T}\rangle|,|\langle\mathbf{x},\mathbf{u}^{T+1}\rangle|\leq\frac{0.05}{T+1/\sqrt{\mu}},$
(160)
its gradient satisfies
$\displaystyle\|\nabla\bar{\mathfrak{F}}_{T;U}(\mathbf{x})\|\geq\mu^{3/4}/32;$
(161)
- 2.
$\bar{\mathfrak{F}}_{T;U}(\mathbf{0})-\inf_{\mathbf{x}}\bar{\mathfrak{F}}_{T;U}(\mathbf{x})\leq\frac{\sqrt{\mu}}{2}+10\mu T$;
- 3.
For $p=1,2$, the $p$-th order derivatives of $\bar{\mathfrak{F}}_{T;U}$ are $(2\mathbb{I}\{p=1\}+\mu)\ell_{p}$-Lipschitz continuous in the hyperball $\mathbb{B}(\mathbf{0},\alpha\sqrt{T})$, where $\ell_{p}\leq\exp\big(\frac{3p}{2}\log p+cp\big{missing})$ for a numerical constant $c<\infty$.

###### Proof.

We set the constants $\alpha,\beta$ according to [Lemma 28](#Thmlemma28). Note that for any vector $\mathbf{y}$ with $\|\mathbf{y}\|\leq 1/(2\zeta)$, the values as well as first- and second-order derivatives of $\|\mathbf{y}\|^{2}$ and $\|\sin\mathbf{y}\|^{2}$ are close to each other given that $\zeta$ reaches a large enough value that is independent from $d$. Quantitatively, we have

$$ $\displaystyle\|\mathbf{y}\|^{2}-\|\sin\mathbf{y}\|^{2}\leq\sum_{i=1}^{d}y_{i}^{2}-\big{(}y_{i}-y_{i}^{3}/6\big{)}^{2}\leq\sum_{i=1}^{d}\frac{y_{i}^{4}}{3}\leq\frac{1}{48\zeta^{4}},$ (162) $$

and

$$ $\displaystyle\big{\|}\nabla\cdot(\|\mathbf{y}\|^{2}-\|\sin\mathbf{y}\|^{2})\big{\|}=\|2\mathbf{y}-\sin(2\mathbf{y})\|\leq\frac{1}{6}\cdot\frac{1}{\zeta^{3}}=\frac{1}{6\zeta^{3}}.$ (163) $$

Moreover, we notice that

$$ $\displaystyle\nabla^{2}(\|\mathbf{y}\|^{2}-\|\sin\mathbf{y}\|^{2})=I-\begin{bmatrix}\cos 2y_{1},&\cdots,&0\\ \vdots,&\ddots,&\vdots\\ 0,&\cdots,&\cos 2y_{d}\end{bmatrix},$ (164) $$

which leads to

$$ $\displaystyle\big{\|}\nabla^{2}(\|\mathbf{y}\|^{2}-\|\sin\mathbf{y}\|^{2})\big{\|}\leq\frac{1}{2}\cdot(2/\zeta)^{2}=\frac{2}{\zeta^{2}}.$ (165) $$

Hence, there exists a large enough $\zeta=O(1/\mu)$ independent from $d$ such that, $\hat{\mathfrak{F}}_{T;U}$ is close enough to the pure rotation of $\bar{\mathfrak{F}}_{T;\mu}$ in the hyperball $\mathbb{B}(\mathbf{0},\alpha\sqrt{T})$ up to the second-order derivatives, and the above three conditions can be satisfied.
∎

Note that if we replicate the hypercube $[-\pi\mathcal{L}/2,\pi\mathcal{L}/2]^{d}$ in $\mathbb{R}^{d}$ consecutively and have the function value in each hypercube being $\hat{\mathfrak{F}}_{T;U}$ respectively, the new function defined on $\mathbb{R}^{d}$ is still infinitely differentiable. Moreover, we can notice that finding an $\epsilon$-SOSP in $\mathbb{R}^{d}$ is equivalent to finding an $\epsilon$-SOSP in one specific hypercube $[-\pi\mathcal{L}/2,\pi\mathcal{L}/2]^{d}$, since for any $\mathbf{x}$ on the boundary of $[-\pi\mathcal{L}/2,\pi\mathcal{L}/2]^{d}$, the Hessian matrix

$$ $\displaystyle\nabla^{2}\hat{\mathfrak{F}}_{T;U}(\mathbf{x})=2\beta\cdot\begin{bmatrix}\cos(2x_{1}/\mathcal{L})&\ldots&0\\ \vdots&\ddots&\vdots\\ 0&\cdots&\cos(2x_{d}/\mathcal{L})\end{bmatrix},$ (166) $$

is positive definite with the matrix norm being $2\beta$, indicating that $\mathbf{x}$ cannot be an $\epsilon$-SOSP. Similar to [Section 5.2](#S5.SS2), we add scaling parameters $\lambda$ and $\sigma$ to $\hat{\mathfrak{F}}_{T;U}$ and obtain the formal hard function

$$ $\displaystyle\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})\coloneqq\lambda\sigma^{2}\hat{\mathfrak{F}}_{T;U}(\mathbf{x}/\sigma).$ (167) $$

Moreover, we assume access to the following noisy evaluation $\mathfrak{f}_{r_{0};T;U}$ of $\hat{\mathfrak{F}}_{T;U}$,

$$ $\displaystyle\mathfrak{f}_{r_{0};T;U}$ $\displaystyle\coloneqq\lambda\sigma^{2}\big{[}\bar{F}_{T;\mu}\big{(}\gamma_{\alpha}(\langle\mathbf{x}/\sigma,\mathbf{u}^{(1)}\rangle),\ldots,\gamma_{\alpha}(\langle\mathbf{x}/\sigma,\mathbf{u}^{(\operatorname{prog}_{r_{0}}(\gamma_{\alpha}(\mathbf{x}/\mu))+1)}\rangle),0,\ldots,0\big{)}$ (168) $\displaystyle\qquad\quad+\beta\mathcal{L}\|\sin(\mathbf{x}/(\sigma\mathcal{L}^{2}))\|^{2}\big{]},$ (169) $$

which is encoded in the quantum oracle $O_{\mathfrak{f}}$ with form ([121](#S5.E121)). Then, we can prove the following quantum lower bound via the function pair $(\tilde{\mathfrak{F}}_{T;U},\mathfrak{f}_{r_{0};T;U})$.

###### Theorem 18 .

Let $\Delta,\epsilon,r_{0}$ be positive and $\epsilon\leq 1/2$, where the noise radius $r_{0}$ is a parameter related to the noise rate. Then there exist positive numerical constants $c,C,\alpha,\beta\in\mathbb{R}$ and $\ell_{q}\leq e^{\frac{3q}{2}\log q+Cq}$ for every $q\in\mathbb{N}$, and a set $\Omega$ consisting of function pairs $(\tilde{\mathfrak{F}}_{T;U},\mathfrak{f}_{r_{0};T;U})$ with $\tilde{\mathfrak{F}}_{T;U}$ and $\mathfrak{f}_{r_{0};T;U}$ defined in ([167](#S5.E167)) and ([168](#S5.E168)) respectively with

$$ $\displaystyle T=\frac{\Delta}{20}\Big{(}\frac{1}{\ell_{2}}\Big{)}^{\frac{5}{4}}\Big{(}\frac{1}{2\ell_{1}}\Big{)}^{\frac{3}{7}}(16\epsilon)^{-12/7},$ (170) $$

such that, for any quantum algorithm $A_{\operatorname{quantum}}$ making fewer than $T$ queries to the oracle $O_{\mathfrak{f}}$ in the form of ([121](#S5.E121)) encoding the function value and gradient of $\mathfrak{f}_{r_{0};T;U}$ in ([168](#S5.E168)), there exists an orthogonal matrix $U$ such that, $A_{\operatorname{quantum}}$ cannot find an $\epsilon$-SOSP of the corresponding $\tilde{\mathfrak{F}}_{T;U}$ with probability larger than $e^{-dr_{0}^{2}/(2\alpha^{2}T)}$, where $\tilde{\mathfrak{F}}_{T;U}$ is $B$ bounded, $L_{1}$-smooth, and $L_{2}$-Hessian Lipschitz with

$$ $\displaystyle B=O\big{(}\Delta+\epsilon^{-12/7}\big{)},\quad L_{1}=O(1),\quad L_{2}=O(1),$ (171) $$

and satisfies

$$ $\displaystyle\tilde{\mathfrak{F}}_{T;U}(\mathbf{0})-\inf_{\mathbf{x}}\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})\leq\Delta.$ (172) $$

###### Proof.

Since the functions and noisy evaluations in each hypercube are the same, without loss of generality we assume all queries happen in the hypercube $[-\pi\sigma\mathcal{L}/2,\pi\sigma\mathcal{L}/2]^{d}$ centered at $\mathbf{0}$. Similar to the setting of [Proposition 2](#Thmproposition2), we set the scaling parameters $\lambda,\mu$ and $\mu$ in $\tilde{\mathfrak{F}}_{T;U}$ and $\mathfrak{f}_{r_{0};T;U}$ to be

$$ $\displaystyle\lambda=\frac{1}{2\ell_{1}},\quad\mu=\frac{\sigma}{\lambda\ell_{2}},\quad\sigma=\ell_{2}^{3/4}\lambda^{-2/7}(16\epsilon)^{4/7},$ (173) $$

which satisfies $\mu\leq 1$ since $\epsilon\leq 1$. By [Lemma 25](#Thmlemma25), finding an $\lambda\sigma\mu^{3/4}/32=\epsilon$-SOSP of $\tilde{\mathfrak{F}}$ with high probability requires complete knowledge of all the $T+1$ columns of the matrix $U$. Equivalently, we can find an $2\epsilon$-SOSP of the function $\tilde{F}_{T;U}$ by finding an $\frac{\epsilon}{2}$-SOSP of $\tilde{\mathfrak{F}}_{T;U}$ with the same $U$ and same settings of parameters, which by [Proposition 2](#Thmproposition2) requires at least $T$ queries to the quantum oracle $O_{f}$ encoding the noisy evaluation $f_{r_{0};T;U}$ of $\tilde{F}_{T;U}$ to guarantee a success probability at least $e^{-dr_{0}^{2}/(2\alpha^{2}T)}$.

In addition, we notice that one query to the quantum oracle $O_{f}$ can be implemented via one query to the quantum oracle $O_{\mathfrak{f}}$ encoding the noisy evaluation $\mathfrak{f}_{r_{0};U;T}$. Hence, by [Proposition 2](#Thmproposition2) we can claim that to find an $\epsilon$-SOSP of $\tilde{\mathfrak{F}}_{T;U}$ with success probability at least $e^{-dr_{0}^{2}/(2\alpha^{2}T)}$, it takes at least

$$ $\displaystyle T=\frac{\Delta}{20}\Big{(}\frac{1}{\ell_{2}}\Big{)}^{\frac{5}{4}}\Big{(}\frac{1}{2\ell_{1}}\Big{)}^{\frac{3}{7}}(16\epsilon)^{-12/7}$ (174) $$

queries to the oracle $O_{\mathfrak{f}}$.

Moreover, by the second entry of [Lemma 25](#Thmlemma25), we know that

$$ $\displaystyle\tilde{\mathfrak{F}}_{T;U}(\mathbf{0})-\inf_{\mathbf{x}}\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})\leq\lambda\sigma^{2}\Big{(}\frac{\mu}{2}+10\mu T\Big{)}\leq\Delta.$ (175) $$

Further, we can observe that

$$ $\displaystyle\sup_{\mathbf{x}}\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})-\tilde{\mathfrak{F}}_{T;U}(\mathbf{0})$ $\displaystyle\leq\lambda\sigma^{2}\sup_{\|\mathbf{x}\|\leq\alpha\sqrt{T}}\bar{F}_{T;\mu}(\mathbf{x})+\lambda\sigma^{2}\beta\mathcal{L}^{2}\sup_{\mathbf{x}}\|\sin(\mathbf{x}/(\sigma\mathcal{L}))\|^{2}$ (176) $\displaystyle\leq\lambda\sigma^{2}\big{(}2\alpha^{2}T+60\alpha^{2}T+\beta\zeta^{2}\alpha^{2}T\big{)}$ (177) $\displaystyle=O(\lambda\sigma^{2}\zeta^{2}T)=O(\lambda\sigma^{2}\mu^{-2}T)$ (178) $\displaystyle=O\big{(}\epsilon^{-12/7}\big{)},$ (179) $$

indicating that $\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})$ is $B$-bounded for $B=O(\Delta+\epsilon^{-12/7})$.

By the third entry of [Lemma 25](#Thmlemma25), $\tilde{F}_{T;U}$ is $\lambda(2+\mu)\ell_{1}=O(1)$-smooth and $\mu\ell_{2}/\sigma=O(1)$-Hessian Lipschitz in the region $\mathbb{B}(\mathbf{0},\alpha\sigma\sqrt{T})$. For any point $\mathbf{x}\in[-\pi\mathcal{L}\sigma/2,\pi\mathcal{L}\sigma/2]^{d}-\mathbb{B}(\mathbf{0},\alpha\sigma\sqrt{T})$, we have

$$ $\displaystyle\|\nabla^{2}\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})\|=\beta\mathcal{L}^{2}\sigma^{2}\Big{\|}\nabla^{2}\sin^{2}\Big{(}\frac{\mathbf{x}}{\sigma\mathcal{L}}\Big{)}\Big{\|}\leq 4\beta=O(1),$ (180) $$

and

$$ $\displaystyle\|\nabla^{3}\tilde{F}_{T;U}(\mathbf{x})\|=\beta\mathcal{L}^{2}\sigma^{2}\Big{\|}\nabla^{3}\sin^{2}\Big{(}\frac{\mathbf{x}}{\sigma\mathcal{L}}\Big{)}\Big{\|}\leq\frac{8\beta}{\sigma\mathcal{L}}=O(1).$ (181) $$

Hence, we can conclude that $\tilde{\mathfrak{F}}_{T;U}$ is $O(1)$-smooth and $O(1)$-Hessian Lipschitz in the entire space $\mathbb{R}^{d}$.
∎

###### Lemma 25 .

###### Proof.

###### Theorem 18 .

###### Proof.

### 5.4 Lower Bound for Quantum Algorithms with Noisy Zeroth- and First-order Oracles

In this subsections, we specify the value of noise radius $r_{0}$ appearing in [Theorem 18](#Thmtheorem18) when we are given noisy zeroth-order oracle or noisy first-order oracle satisfying [Assumption 1](#Thmassumption1) or [Assumption 2](#Thmassumption2), respectively, and further discuss the requirement on dimension $d$ to obtain our lower bound in $\epsilon$.

We first discuss the setting with zeroth-order oracle access.

###### Corollary 2 (Formal version of Theorem 9 , Part 1) .

Let $\Delta,\epsilon>0$ and $\epsilon\leq 1/2$. Then there exist positive numerical constants $c,C,\alpha,\beta\in\mathbb{R}$ and $\ell_{q}\leq e^{\frac{3q}{2}\log q+Cq}$ for every $q\in\mathbb{N}$, and a set $\Omega$ consisting of function pairs $(F,f)$ satisfying [Assumption 1](#Thmassumption1) with some $\nu$ satisfying

$$ $\displaystyle\nu=\Omega\big{(}\epsilon^{-16/7}/d\big{)},$ (182) $$

such that, for any quantum algorithm $A_{\operatorname{quantum}}$ making fewer than $\Theta(\epsilon^{-12/7})$ queries to the oracle $O_{f}$ defined in ([121](#S5.E121)) encoding the function value and gradient of $f$, there exists a function pair $(F,f)$ such that $A_{\operatorname{quantum}}$ cannot find an $\epsilon$-SOSP of $F$ with probability larger than $1/3$, where $F$ is $B$ bounded, $L_{1}$-smooth, and $L_{2}$-Hessian Lipschitz with

$$ $\displaystyle B=O\big{(}\Delta+\epsilon^{-12/7}\big{)},\quad L_{1}=O(1),\quad L_{2}=O(1),$ (183) $$

and satisfies

$$ $\displaystyle F(\mathbf{0})-\inf_{\mathbf{x}}F_{T;U}(\mathbf{x})\leq\Delta.$ (184) $$

###### Proof.

We adopt the settings of functions and parameters in [Theorem 18](#Thmtheorem18) and set $\Omega$ to be

$$ $\displaystyle\Omega=\{(\tilde{\mathfrak{F}}_{T;U},\mathfrak{f}_{r_{0};T;U})\,|\,U\in\mathbb{R}^{d\times(T+1)}\text{ s.t. }U^{\top}U=I\},$ (185) $$

where

$$ $\displaystyle T=\frac{\Delta}{20}\Big{(}\frac{1}{2\ell_{1}}\Big{)}^{\frac{3}{7}}\Big{(}\frac{1}{\ell_{2}}\Big{)}^{\frac{5}{4}}(16\epsilon)^{-12/7}.$ (186) $$

By [Lemma 33](#Thmlemma33), the parameter $r_{0}$ satisfies

$$ $\displaystyle\lambda\sigma^{2}(50r_{0}^{2}T+2\alpha r_{0}\sqrt{T})\leq\nu.$ (187) $$

Moreover, by [Theorem 18](#Thmtheorem18), if the dimension $d$ satisfies

$$ $\displaystyle d\geq\frac{4\alpha^{2}T}{r_{0}^{2}},$ (188) $$

then for any quantum algorithm $A_{\operatorname{quantum}}$ making $T$ queries to $O_{f}$, there exists a function pair
$(F,f)=(\tilde{\mathfrak{F}}_{T;U},\mathfrak{f}_{r_{0},T;U})\in\Omega$ such that the success probability of $A_{\operatorname{quantum}}$ finding an $\epsilon$-SOSP of $\tilde{\mathfrak{F}}_{T;U}$ is at most

$$ $\displaystyle\exp\big(-dr_{0}^{2}/(2\alpha^{2}T)\big{missing})\leq\frac{1}{3}.$ (189) $$

In order to guarantee inequality ([188](#S5.E188)), we can require $\nu$ to satisfy

$$ $\displaystyle\nu\geq\frac{4\alpha^{2}(50+2\alpha)\lambda\sigma^{2}T^{2}}{d}\geq\Omega(\epsilon^{-16/7}/d).$ (190) $$

Moreover, by [Theorem 18](#Thmtheorem18) we can conclude that $F=\tilde{\mathfrak{F}}_{T;U}$ is $O(\Delta+\epsilon^{-12/7})$-bounded, $O(1)$-smooth and $O(1)$ Hessian Lipschitz with

$$ $\displaystyle F(\mathbf{0})-\inf_{\mathbf{x}}F_{T;U}(\mathbf{x})\leq\Delta.$ (191) $$

∎

A similar conclusion can be obtained concerning the setting with first-order oracle access.

###### Corollary 3 (Formal version of Theorem 9 , Part 2 ) .

Let $\Delta,\epsilon>0$ and $\epsilon\leq 1/2$. Then there exist positive numerical constants $c,C,\alpha,\beta\in\mathbb{R}$ and $\ell_{q}\leq e^{\frac{3q}{2}\log q+Cq}$ for every $q\in\mathbb{N}$, and a set $\Omega$ consisting of function pairs $(F,f)$ satisfying [Assumption 2](#Thmassumption2) except the smoothness condition of $f$ with some $\tilde{\nu}$ satisfying

$$ $\displaystyle\tilde{\nu}=\Omega(\epsilon^{-8/7}/\sqrt{d})$ (192) $$

such that, for any quantum algorithm $A_{\operatorname{quantum}}$ making fewer than $\Theta(\epsilon^{-12/7})$ queries to the oracle $O_{f}$ defined in ([121](#S5.E121)) encoding the function value and gradient of $f$, there exists a function pair $(F,f)$ such that $A_{\operatorname{quantum}}$ cannot find an $\epsilon$-SOSP of $F$ with probability larger than $1/3$, where $F$ is $B$ bounded, $L_{1}$-smooth, and $L_{2}$-Hessian Lipschitz with

$$ $\displaystyle B=O\big{(}\Delta+\epsilon^{-12/7}\big{)},\quad L_{1}=O(1),\quad L_{2}=O(1),$ (193) $$

and satisfies

$$ $\displaystyle F(\mathbf{0})-\inf_{\mathbf{x}}F_{T;U}(\mathbf{x})\leq\Delta.$ (194) $$

###### Remark 1 .

One may notice that in the statement of [Corollary 3](#Thmcorollary3), the hard instance $(F,f)$ we consider only satisfies part of [Assumption 2](#Thmassumption2) except the smoothness condition of $f$. Nevertheless, adopting a similar smoothing technique presented in [Section 4.4](#S4.SS4), we can modify the hard instance to further satisfy the smoothness condition of $f$ without affecting the asymptotic lower bound.

###### Proof.

We adopt the settings of functions and parameters in [Theorem 18](#Thmtheorem18) and set $\Omega$ to be

$$ $\displaystyle\Omega=\big{\{}(\tilde{\mathfrak{F}}_{T;U},\mathfrak{f}_{r_{0};T;U})\,|\,U\in\mathbb{R}^{d\times(T+1)}\text{ s.t. }U^{\top}U=I\big{\}},$ (195) $$

where

$$ $\displaystyle T=\frac{\Delta}{20}\Big{(}\frac{1}{2\ell_{1}}\Big{)}^{\frac{3}{7}}\Big{(}\frac{1}{\ell_{2}}\Big{)}^{\frac{5}{4}}(16\epsilon)^{-12/7}.$ (196) $$

By , the parameter $r_{0}$ satisfies

$$ $\displaystyle 6\lambda\sigma r_{0}\sqrt{T}\leq\tilde{\nu}.$ (197) $$

Moreover, by [Theorem 18](#Thmtheorem18), if the dimension $d$ satisfies

$$ $\displaystyle d\geq\frac{4\alpha^{2}T}{r_{0}^{2}},$ (198) $$

then for any quantum algorithm $A_{\operatorname{quantum}}$ making $T$ queries to $O_{f}$, there exists a function pair
$(F,f)=(\tilde{\mathfrak{F}}_{T;U},\mathfrak{f}_{r_{0},T;U})\in\Omega$ such that the success probability of $A_{\operatorname{quantum}}$ finding an $\epsilon$-SOSP of $\tilde{\mathfrak{F}}_{T;U}$ is at most

$$ $\displaystyle\exp\big(-dr_{0}^{2}/(2\alpha^{2}T)\big{missing})\leq\frac{1}{3}.$ (199) $$

In order to guarantee inequality ([199](#S5.E199)), we can require $\tilde{nu}$ to satisfy

$$ $\displaystyle\tilde{\nu}\geq 6\lambda\sigma\cdot\sqrt{4\alpha^{2}T^{2}/d}=\Omega(\epsilon^{-8/7}/\sqrt{d}).$ (200) $$

Moreover, by [Theorem 18](#Thmtheorem18) we can conclude that $F=\tilde{\mathfrak{F}}_{T;U}$ is $O(\Delta+\epsilon^{-12/7})$-bounded, $O(1)$-smooth and $O(1)$ Hessian Lipschitz with

$$ $\displaystyle F(\mathbf{0})-\inf_{\mathbf{x}}F_{T;U}(\mathbf{x})\leq\Delta.$ (201) $$

∎

###### Corollary 2 (Formal version of Theorem 9 , Part 1) .

###### Proof.

###### Corollary 3 (Formal version of Theorem 9 , Part 2
) .

###### Remark 1 .

###### Proof.

## Acknowledgement

We thank Yizhou Liu for helpful discussions about the quantum tunneling walk in []. CZ was supported by the AFOSR under grant FA9550-21-1-039. TL was supported by a startup fund from Peking University, and the Advanced Institute of Information Technology, Peking University.

## Appendix A Auxiliary Lemmas

###### Lemma 26 (Lemma 3, Ref. [ 17 ] ) .

Consider the function $\bar{F}_{T;\mu}\colon\mathbb{R}^{T+1}\to\mathbb{R}$ defined in Eq. ([116](#S5.E116)), suppose the parameter $\mu$ satisfies $\mu\leq 1$. Then for any $\mathbf{x}\in\mathbb{R}^{T+1}$ such that (^4^44The condition below is a bit different from the original condition in Lemma 3 of [], which is $x_{T}=x_{T+1}=0$. Nevertheless, the following stricter conditions can be achieved with only minor modifications to the original proof.)

$$ $\displaystyle|x_{T}|,|x_{T+1}|\leq\frac{0.1}{T+1/\sqrt{\mu}},$ (202) $$

we have

$$ $\displaystyle\big{\|}\nabla\bar{F}_{T;\mu}(\mathbf{x})\big{\|}\geq\mu^{3/4}/8.$ (203) $$

###### Lemma 27 (Lemma 4, Ref. [ 17 ] ) .

The function $\bar{F}_{T;\mu}(\mathbf{x})$ defined in Eq. ([116](#S5.E116)) satisfies the following.

- 1.
$\bar{F}_{T;\mu}(\mathbf{0})-\inf_{\mathbf{x}}\bar{F}_{T;\mu}(\mathbf{x})\leq\frac{\sqrt{\mu}}{2}+10\mu T$;
- 2.
For $\mu\leq 1$ and every $p\geq 1$, the $p$-th order derivatives of $\bar{F}_{T;\mu}$ are $(\mathbb{I}\{p=1\}+\mu)\ell_{p}$-Lipschitz continuous, where $\ell_{p}\leq\exp\big(\frac{3p}{2}\log p+cp\big{missing})$ for a numerical constant $c<\infty$.

###### Lemma 28 (Lemma 3 and Lemma 4, Ref. [ 17 ] ) .

Consider the function $\bar{\mathfrak{F}}_{T;\mu}\colon\mathbb{R}^{T+1}\to\mathbb{R}$ defined in Eq. ([156](#S5.E156)), suppose the parameter $\mu$ satisfies $\mu\leq 1$. Then, there exist positive constants $\alpha,\beta$ such that(^5^55The formula of the function $\bar{\mathfrak{F}}_{T;\mu}$ is a bit different from the original function considered in Lemma 3 and Lemma 4 of Ref. []. Nevertheless, this lemma can be proved via only minor modifications to the original proof.)

- 1.
For any $\mathbf{x}\in\mathbb{R}^{T+1}$ satisfying
$\displaystyle|x_{T}|,|x_{T+1}|\leq\frac{0.05}{T+1/\sqrt{\mu}},$
(204)
its gradient satisfies
$\displaystyle\|\nabla\bar{\mathfrak{F}}_{T;\mu}(\mathbf{x})\|\geq\mu^{3/4}/16;$
(205)
- 2.
$\bar{\mathfrak{F}}_{T;\mu}(\mathbf{0})-\inf_{\mathbf{x}}\bar{\mathfrak{F}}_{T;\mu}(\mathbf{x})\leq\frac{\sqrt{\mu}}{2}+10\mu T$;
- 3.
For every $p>1$, the $p$-th order derivatives of $\bar{\mathfrak{F}}_{T;\mu}$ are $(2\mathbb{I}\{p=1\}+\mu)\ell_{p}$-Lipschitz continuous, where $\ell_{p}\leq\exp\big(\frac{3p}{2}\log p+cp\big{missing})$ for a numerical constant $c<\infty$.

###### Lemma 29 (Proposition 14, Ref. [ 30 ] ) .

Let $\mathbf{x}\in\mathbb{B}(\mathbf{0},1)$. Then for a $d$-dimensional random unit vector $\mathbf{u}$ and all $c>0$,

$$ $\displaystyle\Pr_{\mathbf{u}}(|\langle\mathbf{x},\mathbf{u}\rangle|\geq c)\leq 2e^{-dc^{2}/2}.$ (206) $$

###### Lemma 30 (Lemma 9, Ref. [ 67 ] ) .

Let $H_{1}$ and $H_{2}$ be two Hermitian operators and $H$ be the sum of two operators. For any $t>0$ and state vector $\ket{\varphi}$, we have

$$ $\displaystyle\norm{e^{-iH_{1}t}e^{-iH_{2}t}\ket{\varphi}-e^{-iHt}\ket{\varphi}}\leq\frac{t^{2}}{2}\sup_{\tau_{1},\tau_{2}\in[0,t]}\norm{[H_{1},H_{2}]e^{-iH_{2}\tau_{2}}e^{-iH_{1}\tau_{1}}\ket{\varphi}}.$ (207) $$

###### Lemma 31 (Corollary 1, Ref. [ 67 ] ) .

Consider a quadratic function of form $F_{q}=(\mathbf{x}-\mathbf{x}_{s})H(\mathbf{x}-\mathbf{x}_{s})+f_{0}$ for Hermitian function $H$ and constant $f_{0}$, and the Shroödinger equation

$$ $\displaystyle i\frac{\partial}{\partial t}\Phi=\left[-\frac{r_{0}^{2}}{2}\Delta+\frac{1}{r_{0}^{2}}F_{q}\right]\Phi,$ (208) $$

with periodic boundary conditions and initial state in ([238](#A3.E238)). We have

$$ $\displaystyle\norm{\nabla\Phi(t)}\leq C\sqrt{\frac{d}{r_{0}}}(\log t)^{\alpha}$ (209) $$

for some constant $\alpha$ and $C$.

###### Lemma 26 (Lemma 3, Ref. [ 17 ] ) .

###### Lemma 27 (Lemma 4, Ref. [ 17 ] ) .

###### Lemma 28 (Lemma 3 and Lemma 4, Ref. [ 17 ] ) .

###### Lemma 29 (Proposition 14, Ref. [ 30 ] ) .

###### Lemma 30 (Lemma 9, Ref. [ 67 ] ) .

###### Lemma 31 (Corollary 1, Ref. [ 67 ] ) .

## Appendix B Technical Lemmas

###### Lemma 32 (Cannot guess stationary point) .

Let $k<T$ be a positive in $\big{\{}\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(k)}\big{\}}$ be a set of orthonormal vectors. Let $\{\mathbf{u}^{k+1},\ldots,\mathbf{u}^{T}\}$ be chosen uniformly at random from $\operatorname{span}\big{(}\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(k)}\big{)}^{\perp}$ such that all columns of the matrix $U=\big{[}\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(T+1)}\big{]}$ forms a set of orthonormal vectors. Then,

$$ $\displaystyle\forall\mathbf{x}\in\mathbb{B}\big{(}\mathbf{0},2\sigma\sqrt{T}\big{)},\quad\Pr_{\{\mathbf{u}^{k+1},\ldots,\mathbf{u}^{T+1}\}}\big{[}\|\nabla\tilde{F}_{T;U}(\mathbf{x})\|\leq\lambda\sigma\mu^{3/4}/8\big{]}\leq 8Te^{-dr_{0}^{2}/(8T)},$ (210) $$

for the function $\tilde{F}_{T;U}\colon\mathbb{R}^{d}\to\mathbb{R}$ defined in Eq. ([118](#S5.E118)), given that the parameters $r>1$ and

$$ $\displaystyle r_{0}\leq\frac{0.2\sqrt{T}}{T+1/\sqrt{\mu}}.$ (211) $$

###### Proof.

By [Lemma 29](#Thmlemma29), with probability at least $1-8Te^{-dr_{0}^{2}/(8T)}$, we have

$$ $\displaystyle|\langle\mathbf{x},\mathbf{u}^{(T)}/\sigma\rangle|,|\langle\mathbf{x},\mathbf{u}^{(T+1)}/\sigma\rangle|\leq\frac{r_{0}}{2\sqrt{T}}\leq\frac{0.1}{T+1/\sqrt{\mu}}$ (212) $$

at the same time. Then by [Lemma 26](#Thmlemma26), we have

$$ $\displaystyle\|\nabla\tilde{F}_{T;U}(\mathbf{x})\|\leq\lambda\sigma\|\nabla\bar{F}_{T;\mu;r}(U^{\top}\mathbf{x}/\sigma)\|\leq\lambda\sigma\mu^{3/4}/8.$ (213) $$

∎

###### Lemma 33 .

Consider the functions $\tilde{\mathfrak{F}}_{T;U}\colon\mathbb{R}^{d}\to\mathbb{R}$
and $\mathfrak{f}_{r_{0};T;U}\colon\mathbb{R}^{d}\to\mathbb{R}$
defined in Eq. ([167](#S5.E167)) and Eq. ([168](#S5.E168)), respectively. We have

$$ $\displaystyle\max_{\mathbf{x}}|\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})-\mathfrak{f}_{r_{0};T;U}(\mathbf{x})|\leq\lambda\sigma^{2}(50r_{0}^{2}T+2\alpha r_{0}\sqrt{T}),$ (214) $$

and

$$ $\displaystyle\max_{\mathbf{x}}\big{\|}\nabla\tilde{\mathfrak{F}}_{T;U}-\nabla\mathfrak{f}_{r_{0};T;U}(\mathbf{x})\big{\|}\leq 6\lambda\sigma r_{0}\sqrt{T}.$ (215) $$

where we regard $\nabla\mathfrak{f}_{r_{0};T;U}$ to be $\mathbf{0}$ on the sphere $\mathbb{S}(\mathbf{0},\alpha\sigma\sqrt{T})$ of each hypercube in $\mathbb{R}^{d}$, given that $\mu,\epsilon\leq 1$ and $r_{0}<\sigma$.

###### Proof.

Without loss of generality, we prove this lemma with the input domain being the hypercube $[-\pi\sigma\mathcal{L}/2,\pi\sigma\mathcal{L}/2]^{d}$ centered at $\mathbf{0}$. Denote the vector $\mathbf{y}\in\mathbb{R}^{T+1}$ to be

$$ $\displaystyle\mathbf{y}\coloneqq\big{(}\gamma_{\alpha}(\langle\mathbf{u}^{(1)},\mathbf{x}/\sigma\rangle),\ldots,\gamma_{\alpha}(\langle\mathbf{u}^{(T+1)},\mathbf{x}/\sigma\rangle)\big{)}^{\top},$ (216) $$

which satisfies $\|\mathbf{y}\|\leq\alpha\sqrt{T}$. For the convenience of notations, we denote $y_{0}\coloneqq 0$. Then,

$$ $\displaystyle\max_{\mathbf{x}}\big{|}\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})-\mathfrak{f}_{r_{0};T;U}(\mathbf{x})\big{|}=\lambda\sigma^{2}\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{|}\bar{F}_{T;\mu}(\mathbf{y}^{\operatorname{prog}})-\bar{F}_{T;\mu}(\mathbf{y})\big{|},$ (217) $$

where

$$ $\displaystyle\mathbf{y}^{\operatorname{prog}}\coloneqq\big{(}\gamma_{\alpha}(\langle\mathbf{x}/\sigma,\mathbf{u}^{(1)}\rangle),\ldots,\gamma_{\alpha}(\langle\mathbf{x}/\sigma,\mathbf{u}^{(\operatorname{prog}_{r_{0}}(\gamma_{\alpha}(\mathbf{x}/\mu))+1)}\rangle),0,\ldots,0\big{)}^{\top}.$ (218) $$

Note that

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{|}\bar{F}_{T;\mu}(\mathbf{y}^{\operatorname{prog}})-\bar{F}_{T;\mu}(\mathbf{y})\big{|}$ (219) $\displaystyle\quad\qquad\leq\frac{1}{2}\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\Big{|}\sum_{i=0}^{T}(y_{i}-y_{i+1})^{2}-(y^{\operatorname{prog}}_{i}-y^{\operatorname{prog}}_{i+1})^{2}\Big{|}$ (220) $\displaystyle\quad\qquad+\mu\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},2\alpha\sqrt{T})}\Big{|}\sum_{i=1}^{T+1}\big{(}\Gamma(y_{i})-\Gamma(y^{\operatorname{prog}}_{i})\big{)}\Big{|},$ (221) $$

where

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\Big{|}\sum_{i=1}^{T+1}\big{(}\Gamma(y_{i})-\Gamma(y_{i}^{\operatorname{prog}})\big{)}\Big{|}\leq(T+1)(\Gamma(0)-\Gamma(r_{0}))\leq 40Tr_{0}^{3},$ (222) $$

and

$$ $\displaystyle(y_{1}-1)^{2}-(y_{1}^{\operatorname{prog}}-1)^{2}=0,\qquad\forall\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T}),$ (223) $$

since $\operatorname{prog}_{r_{0}}(\gamma_{\alpha}(\mathbf{x}/\mu))+1\geq 1$ for all possible $\mathbf{x}$ and corresponding $\mathbf{y}$. As for the term in ([220](#A2.E220)), we note that

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\Big{|}\sum_{i=1}^{T}(y_{i}-y_{i+1})^{2}-(y_{i}^{\operatorname{prog}}-y_{i+1}^{\operatorname{prog}})^{2}\Big{|}$ (224) $\displaystyle\quad\qquad\leq 4Tr_{0}^{2}+2\alpha r_{0}\sqrt{T}.$ (225) $$

Thus we can conclude that

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sigma\sqrt{T})}\big{|}\bar{F}_{T;\mu}(\delta_{r_{0}}(\mathbf{y}))-\bar{F}_{T;\mu}(\mathbf{y})\big{|}$ $\displaystyle\leq 50r_{0}^{2}T+2\alpha r_{0}\sqrt{T},$ (226) $$

and

$$ $\displaystyle\max_{\mathbf{x}}\big{|}\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})-\mathfrak{f}_{r_{0};T;U}\big{|}\leq\lambda\sigma^{2}(50r_{0}^{2}T+2\alpha r_{0}\sqrt{T}).$ (227) $$

Similarly, we can observe that

$$ $\displaystyle\max_{\mathbf{x}}\big{\|}\nabla\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})-\nabla\mathfrak{f}_{r_{0};T;U}(\mathbf{x})\big{\|}\leq\lambda\sigma\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\bar{F}_{T;\mu}(\delta_{r_{0}}(\mathbf{y}))-\nabla\bar{F}_{T;\mu}(\mathbf{y})\big{\|},$ (228) $$

where

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\bar{F}_{T;\mu}(\delta_{r_{0}}(\mathbf{y}))-\nabla\bar{F}_{T;\mu}(\mathbf{y})\big{\|}$ (229) $\displaystyle\quad\qquad\leq\frac{1}{2}\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\cdot\sum_{i=0}^{T}\big{[}(y_{i}-y_{i+1})^{2}-(y_{i}^{\operatorname{prog}}-y_{i+1}^{\operatorname{prog}})^{2}\big{]}\big{\|}$ (230) $\displaystyle\quad\qquad+\mu\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\cdot\sum_{i=1}^{T+1}\big{[}\Gamma(y_{i})-\Gamma(y_{i}^{\operatorname{prog}})\big{]}\big{\|},$ (231) $$

where the term in ([231](#A2.E231)) satisfies

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\cdot\sum_{i=1}^{T+1}\big{[}\Gamma(y_{i})-\Gamma(y_{i}^{\operatorname{prog}})\big{]}\big{\|}\leq 2\sqrt{T}\cdot|\Gamma^{\prime}(r_{0})-\Gamma^{\prime}(0)|\leq 2r_{0}\sqrt{T}$ (232) $$

As for the term in ([230](#A2.E230)), we first note that for any $0\leq i\leq T$ and any $\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})$, we have

$$ $\displaystyle\frac{1}{2}\big{\|}\nabla\cdot[(y_{i}-y_{i+1})^{2}-(y_{i}^{\operatorname{prog}}-y_{i+1}^{\operatorname{prog}})^{2}]\big{\|}\leq 2\sqrt{2}r_{0},$ (233) $$

which leads to

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\cdot\sum_{i=1}^{T}\big{[}(y_{i}-y_{i+1})^{2}-(y_{i}^{\operatorname{prog}}-y_{i+1}^{\operatorname{prog}})^{2}\big{]}\big{\|}\leq 4r_{0}\sqrt{T}.$ (234) $$

Hence,

$$ $\displaystyle\max_{\mathbf{y}\in\mathbb{B}(\mathbf{0},\alpha\sqrt{T})}\big{\|}\nabla\bar{F}_{T;\mu}(\delta_{r_{0}}(\mathbf{y}))-\nabla\bar{F}_{T;\mu}(\mathbf{y})\big{\|}\leq 6r_{0}\sqrt{T},$ (235) $$

by which we can conclude that

$$ $\displaystyle\max_{\mathbf{x}}\big{\|}\nabla\tilde{\mathfrak{F}}_{T;U}(\mathbf{x})-\nabla\mathfrak{f}_{r_{0};T;U}(\mathbf{x})\big{\|}\leq 6\lambda\sigma r_{0}\sqrt{T}.$ (236) $$

∎

###### Lemma 32 (Cannot guess stationary point) .

###### Proof.

###### Lemma 33 .

###### Proof.

## Appendix C Perturbed Gradient Descent with Quantum Simulation and Gradient Estimation

In this section, we consider an alternative version of [Algorithm 3](#alg3) that has a faster convergence rate in some cases. Inspired by Ref. [], we replace the uniform perturbation in [Algorithm 3](#alg3) with quantum simulation. We consider the scaled evolution under Schrödinger equation

$$ $\displaystyle i\frac{\partial}{\partial t}\Phi=\left[-\frac{r_{0}^{2}}{2}\Delta+\frac{1}{r_{0}^{2}}f\right]\Phi,$ (237) $$

where $\Phi$ is a wave function in $\mathbb{R}^{d}$, $\Delta$ is the Laplacian operator, $r_{0}$ is the scaling parameter, and $f$ is the potential of the evolution. To construct a quantum algorithm using this evolution, quantum simulations are required. There is rich literature on the cost of quantum simulations [, , , , , ]. Here, we introduce the following theorem concerning the cost of simulating ([237](#A3.E237)) using zeroth-order oracle $F$, which was originally proposed in Ref. [].

###### Lemma 34 (Lemma 2, Ref. [ 67 ] ) .

Let $F(\mathbf{x})\colon\mathbb{R}^{d}\to\mathbb{R}$ be a real-valued function that has a saddle point at $\mathbf{x}=0$ such that $f(\mathbf{0})=0$. Consider the (scaled) Schrödinger equation in ([237](#A3.E237)) defined on the domain $\Omega=\{\mathbf{x}\in\mathbb{R}^{d}\colon\norm{\mathbf{x}}\leq M\}$ with periodic boundary condition, where $M>0$ is the diameter specified later. Given the noiseless zeroth-order oracle $U_{f}(\ket{\mathbf{x}}\otimes\ket{0})=\ket{\mathbf{x}}\otimes\ket{f(\mathbf{x})}$ and an arbitrary initial state. The evolution for time $t>0$ can be simulated using $\tilde{O}(t\log d\log^{2}(t/\epsilon))$ queries to $U_{f}$, where $\epsilon$ is the simulation precision.

Notice that $F$ is assumed to be Hessian Lipschitz in both [Assumption 1](#Thmassumption1) and [Assumption 2](#Thmassumption2), we can approximate the function value near a saddle point. The approximation is more accurate on a ball with radius $r_{0}$ centered at this saddle point. We scale the initial distribution and the Schrödinger equation to be localized in term of $r_{0}$ and results in [Algorithm 6](#alg6), which is originally proposed in Ref. [].

Figure: Algorithm 6 QuantumSimulation($\tilde{\mathbf{x}},r_{0},t_{e},f(\cdot)$).

[Algorithm 6](#alg6) is the main building block of the quantum implementation of perturbation in PGD. It can effectively reduce the iteration number compared to the classical perturbations in [Algorithm 3](#alg3) [] for some functions. To achieve a better performance than [Theorem 11](#Thmtheorem11), we have to add some constraints on the target and the noisy function $(F,f)$. Specifically, we consider the following setting.

###### Assumption 3 .

The underlying target function $F$ is $B$-bounded, $\ell$-smooth, and $\rho$-Hessian Lipschitz. We can query a noisy function $f$ that is twice differentiable. We assume

$$ $\displaystyle\nu$ $\displaystyle=\sup_{\mathbf{x}}\norm{F(\mathbf{x})-f(\mathbf{x})}_{\infty}=\tilde{O}\left(\frac{\epsilon^{6}}{d^{4}}\right),$ (239) $\displaystyle\tilde{\nu}$ $\displaystyle=\sup_{\mathbf{x}}\norm{\nabla F(\mathbf{x})-\nabla f(\mathbf{x})}_{\infty}=\ell_{f}M=O\left(d^{-3}\right),$ (240) $\displaystyle\hat{\nu}$ $\displaystyle=\sup_{\mathbf{x}}\norm{\nabla^{2}F(\mathbf{x})-\nabla^{2}f(\mathbf{x})}_{\infty}=\rho_{f}M=O\left(d^{-3}\right),$ (241) $$

where $\ell_{f}$ and $\rho_{f}$ are arbitrary constants, and $M=O(d^{-3})$ is some value to be fixed later.

By using quantum simulations to implement perturbations, we propose the following [Algorithm 7](#alg7) that can effectively find an $\epsilon$-SOSP of $F$ using queries to noisy $f$ for function pair $(F,f)$ in [Assumption 3](#Thmassumption3) with high probability.

Figure: Algorithm 7 Perturbed Gradient Descent with Quantum Gradient Computation.

[Algorithm 7](#alg7) has the following performance guarantee:

###### Theorem 19 .

Suppose we have a target function $F$ and its noisy evaluation $f$ satisfying [Assumption 3](#Thmassumption3) with $\nu\leq\tilde{O}(\delta^{2}\epsilon^{6}/d^{4})$. Then with probability at least $1-\delta$, [Algorithm 7](#alg7) can find an $\epsilon$-SOSP of $F$ satisfying ([4](#S1.E4)), using

$$ $\displaystyle\tilde{O}\left(\frac{\ell B}{\epsilon^{2}}\cdot\log^{2}d\right)$ (242) $$

queries to $U_{f}$, under the following parameter choices:

$$ $\displaystyle\ell^{\prime}=\ell+\frac{1}{2}\ell_{f},\quad\rho^{\prime}=\rho+\rho_{f},\quad\eta=\frac{1}{\ell^{\prime}},\quad\delta_{0}=\min\left\{\frac{\delta}{162B}\frac{\epsilon^{3}}{\rho^{\prime}},\frac{\eta\epsilon^{2}\delta}{16B}\right\},\quad\mathscr{F}=\frac{2}{81}\sqrt{\frac{\epsilon^{3}}{\rho^{\prime}}},$ (243) $\displaystyle\mathscr{T}=\frac{8}{(\rho^{\prime}\epsilon)^{1/4}}\log\left(\frac{\ell^{\prime}}{\delta_{0}\sqrt{\rho^{\prime}\epsilon}}(d+2\log(\frac{3}{\delta_{0}}))\right),\quad r_{0}=\frac{4c_{r}^{3}}{9\mathscr{T}^{4}}\left(\frac{\delta_{0}}{3}\cdot\frac{1}{d^{3/2}+2c_{0}d\ell^{\prime}(\log\mathscr{T})^{\alpha}}\right)^{2},$ (244) $$

where $c_{0}$, $\alpha$, and $c_{r}$ are absolute constants specified in the proof.

Before proving [Theorem 19](#Thmtheorem19), we first consider the effectiveness of quantum simulations for adding perturbations. We focus on the scenarios with $\epsilon\leq\ell^{2}/\rho$, which is the standard assumption adopted in Ref. []. The local landscape in this case “flat” and the Hessian has only a small spectral radius. The classical gradient descent will move slowly while the variance of the probability distribution corresponding
to the Gaussian wavepacket still has a large increasing rate. If we evolve the Gaussian wavepacket for a long enough time period and measure its position, we will obtain a vector that indicates a negative curvature direction with high probability.

However, [Algorithm 6](#alg6) using quantum simulation and noisy oracle in [Assumption 3](#Thmassumption3) suffers two deviation terms from the ideal Gaussian evolution: the deviation of $F$ from quadratic potential and the noise of $f$ from $F$. We have to bound the resulting deviation on the distribution from the perfect Gaussian wavepacket. We specify the constant $c_{r}$ as the ratio between the wavepacket variance and the radius of the simulation region. By choosing a small enough $c_{r}$, the simulation region is much larger than the range of the wavepacket. As the function $F$ is $\ell$-smooth, the spectral norm of the Hessian matrix is upper bounded by constant $\ell$. The radius $M$ of the simulation region is chosen as

$$ $\displaystyle M=\frac{r_{0}}{C_{r}}=\frac{4c_{r}^{2}}{9\mathscr{T}^{4}}\left(\frac{\delta_{0}}{3}\cdot\frac{1}{d^{3/2}+2c_{0}d\ell(\log\mathscr{T})^{\alpha}}\right)^{2}\leq 1.$ (245) $$

By choosing the above $M$, we can reach the following lemma.

###### Lemma 35 .

Under the setting of [Assumption 3](#Thmassumption3) and [Theorem 2](#Thmtheorem2), let $H$ be the Hessian matrix of $F$ at the saddle point $\mathbf{x}_{s}$, and define $F_{q}(\mathbf{x})=f(\mathbf{x}_{s})+(\mathbf{x}-\mathbf{x}_{s})^{\top}H(\mathbf{x}-\mathbf{x}_{s})$ to be the quadratic approximation of $F$ near $\mathbf{x}_{s}$. We denote the measurement outcome from [Algorithm 6](#alg6) with noisy function $f$ and evolution $t_{e}$ as a random variable $\xi$, and the measurement outcome from the ideal potential $F_{q}$ and the same evolution time $t_{e}$ as another random variable $\xi^{\prime}$. We define $\mathbb{P}_{\xi}$ and $\mathbb{P}_{\xi^{\prime}}$ to be the distribution of $\xi$ and $\xi^{\prime}$. If the quantum wavepacket is confined to a hypercube with regions length $M$, then

$$ $\displaystyle TV(\mathbb{P}_{\xi},\mathbb{P}_{\xi^{\prime}})\leq\left(\frac{\sqrt{d}\rho^{\prime}}{2}+\frac{2c_{f}\ell^{\prime}}{\sqrt{r_{0}}}(\log t_{e})^{\alpha}\right)\frac{dMt_{e}^{2}}{2},$ (246) $$

where $TV(\cdot,\cdot)$ denotes the total variation distance, $\alpha$ is an absolute constant, and $c_{f}$ is an $F$-related constant.

###### Proof.

We first define the following notations:

$$ $\displaystyle A=-\frac{r_{0}^{2}}{2}\Delta,\quad B=\frac{1}{r_{0}^{2}}f,\quad B^{\prime}=\frac{1}{r_{0}^{2}}F_{q},$ (247) $\displaystyle H=A+B,\quad H^{\prime}=A+B^{\prime},\quad E=H-H^{\prime}=\frac{1}{r_{0}^{2}}(f-F_{q}).$ (248) $$

We denote $\ket{\Phi(t)}=e^{-iHt}\ket{\Phi_{0}}$ and $\ket{\Phi^{\prime}(t)}=e^{-iH^{\prime}t}\ket{\Phi_{0}}$ be the wave functions at time $t$ for two different Hamiltonians $H$ and $H^{\prime}$. By
[Lemma 30](#Thmlemma30), we have

$$ $\displaystyle\norm{e^{iEt_{e}}\ket{\Phi^{\prime}(t_{e})}-\ket{\Phi(t_{e})}}$ $\displaystyle\leq\frac{t_{e}^{2}}{2}\sup_{\tau_{1},\tau_{2}\in[0,t_{e}]}\norm{[H^{\prime},E]e^{-iE\tau_{2}}e^{-iH^{\prime}\tau_{1}}\ket{\Phi_{0}}}$ (249) $\displaystyle=\frac{t_{e}^{2}}{2}\sup_{\tau_{1}\in[0,t_{e}]}\norm{[H^{\prime},E]e^{-iH^{\prime}\tau_{1}}\ket{\Phi_{0}}}.$ (250) $$

Denoting $\ket{\Psi(\tau_{1})}=e^{-iH^{\prime}\tau_{1}}\ket{\Phi_{0}}$, we have

$$ $\displaystyle\sup_{\tau_{1}\in[0,t_{e}]}\norm{[H^{\prime},E]\Psi(\tau_{1})}$ $\displaystyle=\frac{1}{2}\sup_{\tau_{1}\in[0,t]}\norm{[-\Delta,f-F_{q}]\Psi(\tau_{1})}$ (251) $\displaystyle=\frac{1}{2}\sup_{\tau_{1}\in[0,t_{e}]}\norm{-\Delta(f-F_{q})\Psi(\tau_{1})-2\nabla(f-F_{q})\cdot\nabla\Psi(\tau_{1})}$ (252) $\displaystyle\leq\frac{1}{2}\norm{\Delta(f-F_{q})}_{\infty}+\norm{\nabla(f-F_{q})}_{\infty}\norm{\nabla\Psi(\tau_{1})}.$ (253) $$

The first equality follows from $[H^{\prime},E]=[A+B^{\prime},E]$ and $B^{\prime}$ commutes with $E$. The second equality follows from $[-\Delta,g]\varphi=-(\Delta g)\varphi-2\nabla g\cdot\nabla\varphi$ for any smooth function $\varphi$ and $g$. As we assume $F$ is $\rho$-Hessian Lipschitz, we can deduce that

$$ $\displaystyle\absolutevalue{\Delta(f(\mathbf{x})-F_{q}(\mathbf{x}))}$ $\displaystyle=\absolutevalue{\tr(\nabla^{2}f(\mathbf{x})-\nabla^{2}F(\mathbf{x}))}+\absolutevalue{\tr(\nabla^{2}F(\mathbf{x})-\nabla^{2}F_{q}(\mathbf{x}))}$ (254) $\displaystyle=\absolutevalue{\tr(\nabla^{2}f(\mathbf{x})-\nabla^{2}F(\mathbf{x}))}+\absolutevalue{\tr(\nabla^{2}F(\mathbf{x})-\nabla^{2}F(\mathbf{x}_{s}))}$ (255) $\displaystyle\leq d\norm{\nabla^{2}f(\mathbf{x})-\nabla^{2}F(\mathbf{x})}+d\norm{\nabla^{2}F(\mathbf{x})-\nabla^{2}F(\mathbf{x}_{s})}$ (256) $\displaystyle\leq d^{3/2}(\rho+\rho_{f})M$ (257) $\displaystyle=d^{3/2}\rho^{\prime}M.$ (258) $$

Next, we bound the term on the gradient of $f-F_{q}$:

$$ $\displaystyle\norm{\nabla(f-F_{q})}_{\infty}$ $\displaystyle\leq\sup_{\mathbf{x}}\norm{\nabla f(\mathbf{x})-\nabla F_{q}(\mathbf{x})}$ (259) $\displaystyle=\sup_{\mathbf{x}}\norm{\nabla f(\mathbf{x})-\nabla F(\mathbf{x})}+\sup_{\mathbf{x}}\norm{\nabla F(\mathbf{x})-H(\mathbf{x}-\mathbf{x}_{s})}$ (260) $\displaystyle\leq\sup_{\mathbf{x}}\norm{\nabla f(\mathbf{x})-\nabla F(\mathbf{x})}+\sup_{\mathbf{x}}\norm{\nabla F(\mathbf{x})}+\sup_{\mathbf{x}}\norm{H(\mathbf{x}-\mathbf{x}_{s})}$ (261) $\displaystyle\leq(2\ell+\ell_{f})Md^{-1/2}$ (262) $\displaystyle=2\ell^{\prime}Md^{-1/2}$ (263) $$

The upper bound for $\sup_{\tau_{1}\in[0,t_{e}]}\norm{\nabla\Psi(\tau_{1})}$ is given by [Lemma 31](#Thmlemma31). Combining the above bounds, we obtain

$$ $\displaystyle\norm{e^{iEt_{e}}\ket{\Phi^{\prime}(t_{e})}-\ket{\Phi(t_{e})}}\leq\left(\frac{\sqrt{d}\rho^{\prime}}{2}+\frac{2c_{f}\ell^{\prime}}{\sqrt{r_{0}}}(\log t_{e})^{\alpha}\right)\frac{dMt_{e}^{2}}{2}.$ (264) $$

In the following part, we denote $\Psi^{\prime}$ for $\Psi^{\prime}(t_{e})$ and $\ket{\Psi^{\prime\prime}}=e^{-iEt_{e}}\ket{\Psi^{\prime}}$. We observe that $\absolutevalue{\Psi^{\prime}}^{2}=\absolutevalue{\Psi^{\prime\prime}}^{2}$ as $e^{-iEt_{e}}$ is a scalar function with modulus $1$. Thus

$$ $\displaystyle TV(\mathbb{P}_{\xi},\mathbb{P}_{\xi^{\prime}})$ $\displaystyle=TV(\absolutevalue{\Psi}^{2},\absolutevalue{\Psi^{\prime\prime}}^{2})$ (265) $\displaystyle=\frac{1}{2}\int_{\mathbf{x}}\absolutevalue{\Psi\Psi^{\dagger}-\Psi^{\prime\prime}\Psi^{{}^{\prime\prime}\dagger}}d\mathbf{x}$ (266) $\displaystyle\leq\frac{1}{2}\int_{\mathbf{x}}\absolutevalue{(\Psi-\Psi^{\prime\prime})\Psi^{\dagger}}d\mathbf{x}+\frac{1}{2}\int_{\mathbf{x}}\absolutevalue{\Psi^{\prime\prime}(\Psi-\Psi^{\prime\prime})^{\dagger}}d\mathbf{x}$ (267) $\displaystyle\leq(\frac{1}{2}\int_{\mathbf{x}}\absolutevalue{\Psi-\Psi^{\prime\prime}}^{2}d\mathbf{x})^{1/2}$ (268) $\displaystyle\leq\left(\frac{\sqrt{d}\rho^{\prime}}{2}+\frac{2c_{f}\ell^{\prime}}{\sqrt{r_{0}}}(\log t_{e})^{\alpha}\right)\frac{dMt_{e}^{2}}{2}.$ (269) $$

∎

[Lemma 35](#Thmlemma35) indicates that the actual perturbation given by quantum simulation $\xi\sim\mathbb{P}_{\xi}$ deviates from the ideal Gaussian case $\xi^{\prime}\sim\mathbb{P}_{\xi^{\prime}}$ for at most $\tilde{O}(Md^{3/2}t_{e}^{2})$. In [Algorithm 7](#alg7) with $t_{e}=\mathscr{T}=O(\log d)$, such deviation can be bounded for the choice of $M$ in ([245](#A3.E245)). Based on [Lemma 35](#Thmlemma35), we reach the following lemma.

###### Lemma 36 (Adaptive version of Proposition 1, Ref. [ 67 ] ) .

Suppose $(F,f)$ satisfies [Assumption 3](#Thmassumption3). For arbitrary $\delta_{0}$, we choose the following parameters:

$$ $\displaystyle\eta=\frac{1}{\ell^{\prime}},\mathscr{T}=\frac{8}{(\rho^{\prime}\epsilon)^{1/4}}\log\left(\frac{\ell^{\prime}}{\delta_{0}\sqrt{\rho^{\prime}\epsilon}}(d+2\log(\frac{3}{\delta_{0}}))\right),$ (270) $\displaystyle\mathscr{F}=\frac{2}{81}\sqrt{\frac{\epsilon^{3}}{\rho^{\prime}}},\quad r_{0}=\frac{4c_{r}^{3}}{9\mathscr{T}^{4}}\left(\frac{\delta_{0}}{3}\cdot\frac{1}{d^{3/2}+2c_{0}d\ell^{\prime}(\log\mathscr{T})^{\alpha}}\right)^{2},$ (271) $$

where $\rho^{\prime}$, $\ell^{\prime}$, $c_{r}$, $c_{0}$, and $\alpha$ are the same with [Theorem 19](#Thmtheorem19). Then, for an saddle point $\mathbf{x}_{s}$ with $\norm{F(\mathbf{x}_{s})}\leq\epsilon$ and $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{s}))\leq-\sqrt{\rho\epsilon}$, [Algorithm 7](#alg7) provides a perturbation that decreases the function value for at least $\mathscr{F}$ with probability at least $1-\delta_{0}$.

We now prove [Theorem 19](#Thmtheorem19).

###### Proof.

We set the zeroth-order noise bound $\nu\leq c_{\nu}\delta^{2}\epsilon^{6}/d^{4}$ for small enough $c_{\nu}$ and let the total total iteration number to be

$$ $\displaystyle T=4\max\left\{\frac{2B}{\mathscr{F}},\frac{4B}{\eta\epsilon^{2}}\right\}=\tilde{O}\left(\frac{B}{\epsilon^{2}}\cdot\log d\right).$ (272) $$

We first consider the iteration number at saddle points $\mathbf{x}_{t}$ with $\norm{F(\mathbf{x}_{t})}\leq\epsilon$ and $\lambda_{\min}(\nabla^{2}F(\mathbf{x}_{t}))\leq-\sqrt{\rho\epsilon}$. According to [Lemma 36](#Thmlemma36), each iteration of [Algorithm 7](#alg7) in this case will decrease the function value for at least $\mathscr{T}$. Under this assumption, [Algorithm 6](#alg6) can be called for at most $T/2$ times, for otherwise the function value decreases greater than $2B\geq F(\mathbf{x}^{*})-F(\mathbf{x}_{0})$. The failure probability is bounded by

$$ $\displaystyle 81\sqrt{\frac{\rho}{\epsilon^{3}}}\cdot\delta_{0}=\frac{\delta}{2}.$ (273) $$

Except for these iterations that quantum simulation is implemented to add perturbations, we still have $T/2$ iterations. We consider the iterations with large gradients $\norm{F(\mathbf{x}_{t})}\geq\epsilon$. In each iteration, the function value will decrease at least $\eta\epsilon^{2}/4$. There can be at most $T/4$ iterations, for otherwise the function value decreases greater than $2B\geq F(\mathbf{x}^{*})-F(\mathbf{x}_{0})$. The failure probability is bounded by

$$ $\displaystyle\frac{4B}{\eta\epsilon^{2}}\cdot\delta_{0}=\delta/2.$ (274) $$

In summary, with probability at least $1-\delta$, there are at most $T/2$ iterations when the quantum simulation is called and at most $T/4$ iterations when the gradient is large. There are thus at least $T/4$ iterations resulting in $\epsilon$-SOSP of $F$.

The number of queries can be decomposed into two parts, the number of queries required for gradient estimations, denoted by $T_{1}$, and the number of queries required for quantum simulations, denoted by $T_{2}$. For the first part, we have

$$ $\displaystyle T_{1}=O(T)=\tilde{O}\left(\frac{B}{\epsilon^{2}}\cdot\log d\right).$ (275) $$

For $T_{2}$, the number of queries is given by [Lemma 34](#Thmlemma34) as

$$ $\displaystyle T_{2}=\tilde{O}\left(\frac{B}{\epsilon^{2}}\cdot\log^{2}d\right).$ (276) $$

The total query complexity $T_{1}+T_{2}$ is bounded by

$$ $\displaystyle\tilde{O}\left(\frac{B}{\epsilon^{2}}\cdot\log^{2}d\right).$ (277) $$

∎

###### Lemma 34 (Lemma 2, Ref. [ 67 ] ) .

###### Assumption 3 .

###### Theorem 19 .

###### Lemma 35 .

###### Proof.

###### Lemma 36 (Adaptive version of Proposition 1, Ref. [ 67 ] ) .

###### Proof.

## Appendix D Existence of Example with Quantum Advantage using Quantum Tunnelling Walk

In [Theorem 6](#Thmtheorem6), we have proved that when the noise under [Assumption 1](#Thmassumption1) increases to $\nu\geq\Theta(\epsilon^{1.5})$, we can find a hard instance for any classical or quantum algorithm even using exponentially many queries. Although the noise bound for the quantum algorithms is the same, there might be quantum speedup for a specific instance. In this section, we provide a candidate for this argument under some proper additional assumptions.

We set the constant $\mu=300$. For the target function $F$, we still consider the following function defined in ([88](#S4.E88)):

$$ $\displaystyle F(\mathbf{x}):=h(\sin\mathbf{x})+\norm{\sin\mathbf{x}}^{2},$ (278) $$

where $h(\mathbf{x}):=h_{1}(\mathbf{v}^{\top}\mathbf{x})\cdot h_{2}\left(\sqrt{\norm{\mathbf{x}}^{2}-(\mathbf{v}^{\top}\mathbf{x})^{2}}\right)$, and

$$ $\displaystyle h_{1}(x)=g_{1}(\mu x),\quad g_{1}(x)$ $\displaystyle=(-16\absolutevalue{x}^{5}+48x^{4}-48\absolutevalue{x}^{3}+16x^{2})\cdot\mathbb{I}\{\absolutevalue{x}<1\},$ (279) $\displaystyle h_{2}(x)=g_{2}(\mu x),\quad g_{2}(x)$ $\displaystyle=(3x^{4}+8\absolutevalue{x}^{3}+6x^{2}-1)\cdot\mathbb{I}\{\absolutevalue{x}<1\}.$ (280) $$

We adopt the construction in Ref. [] for the construction of noisy function $f$. In the following, we denote $R$ to be the radius of the hyperball where the main construction is. We also choose $\mathbf{v}$ uniformly in the unit sphere. We define two regions $W_{-}=\mathbb{B}(0,a)$ and $W_{+}=\mathbb{2b\mathbf{v},a}$ with $b\geq a$. We choose $a$ and $b$ such that $W_{-}$ and $W_{+}$ are in $\mathbb{B}(0,R)$. We denote the region $S_{\mathbf{v}}\coloneqq\{\mathbf{x}|\mathbf{x}\in\mathbb{B}(0,R),\absolutevalue{\mathbf{x}\cdot\mathbf{v}}\leq w\}$, where $w$ is chosen in $[0,\sqrt{3}w/2)$. We define

$$ $\displaystyle B_{\mathbf{v}}\coloneqq\{\mathbf{x}|w<\mathbf{x}\cdot\mathbf{v}<2b-w,\sqrt{\norm{\mathbf{x}}^{2}-(\mathbf{x}\cdot\mathbf{v})^{2}}<\sqrt{a^{2}-w^{2}},\mathbf{x}\notin W_{-}\cup W_{+}\}.$ (281) $$

The construction of $f$ is given by

$$ $\displaystyle f=\begin{cases}\frac{1}{2}\omega^{2}\norm{\mathbf{x}}^{2},\quad\mathbf{x}\in W_{-},\\ \frac{1}{2}\omega^{2}\norm{\mathbf{x}-2b\mathbf{v}}^{2},\quad\mathbf{x}\in W_{+},\\ H_{1},\quad\mathbf{x}\in B_{\mathbf{v}},\\ H_{2},\quad\text{otherwise.}\end{cases}$ (282) $$

We choose $0<\omega^{2}a^{2}/2\sim H_{1}\ll H_{2}$. There are two local minima for $f$ in ([282](#A4.E282)), $\mathbf{0}$ and $2b\mathbf{v}$. We can verify that the function pair $(F,f)$ satisfies the following properties.

- •
$\sup_{x}\norm{f-F}_{\infty}\leq\tilde{O}(1)$.
- •
$F$ is $O(d)$-bounded, $O(1)$-Hessian Lipschitz, and $O(1)$-gradient Lipschitz.

We apply the same scaling in the main text as

$$ $\displaystyle\tilde{F}(\mathbf{x})$ $\displaystyle\coloneqq\epsilon rF\left(\frac{\mathbf{x}}{r}\right),$ (283) $\displaystyle\tilde{f}(\mathbf{x})$ $\displaystyle\coloneqq\epsilon rf\left(\frac{\mathbf{x}}{r}\right),$ (284) $$

where $r=\sqrt{\epsilon/\rho}$. According to Ref. [], quantum tunneling walk can provide a speedup for finding SOSP of $f$ using ground states containing information of $\mathbf{v}$ and $W_{+}$.

###### Lemma 37 (Proposition 4.2 and Theorem 4.1, Ref. [ 43 ] ) .

Assume we start from point $\mathbf{0}$ and we are provided with knowledge that $\mathbf{0}$ is a local minimum. We know local ground states associated with $W_{-}$ and $W_{+}$. By properly choosing the parameter $a$, $b$, $H_{1}$, and $H_{2}$, quantum tunneling walk can find the another local minima with high probability using $O(\operatorname{poly}(d))$ queries while any classical algorithm requires $\Omega(e^{dB})$ queries to zeroth-order oracle $f$.

Under the setting of this paper, we consider choosing $R$ such that $2b\mathbf{v}$ is also a local minimum of $F$. Notice that $\mathbf{0}$ is not a local minimum of $F$, our goal is to find the $\epsilon$-SOSP near the local minima $2b\mathbf{v}$ of $F$ taking queries to noisy oracle $f$ in ([7](#S1.E7)). We can reach the following corollary using [Lemma 37](#Thmlemma37).

###### Corollary 4 .

Consider the hard instance $(\tilde{F},\tilde{f})$ defined by ([283](#A4.E283)), ([284](#A4.E284)), and a proper chosen $R$ such that $2b\mathbf{v}$ is also a local minimum of $\tilde{F}$. There exists a choice of parameters $a$, $b$, $H_{1}$, and $H_{2}$ such that a quantum algorithm starting at $\mathbf{0}$ can find an $\epsilon$-SOSP of $\tilde{F}$ with high probability using $O(\operatorname{poly}(d))$ queries to the noisy $\tilde{f}$ and proper initial ground state. However, any classical algorithm with proper initial ground states requires $\Omega(e^{dB})$ queries.

The above corollary demonstrates that if we assume that we have some ground states revealing information above $\mathbf{v}$, the quantum algorithm can provide an exponential speedup in solving a special hard instance $(F,f)$ that satisfies [Assumption 1](#Thmassumption1). It is worthwhile to mention that the additional assumption on the local ground state is essential for this speedup and the quantum algorithm also requires query complexity that is exponential in $d$ without such assumption  [].

###### Lemma 37 (Proposition 4.2 and Theorem 4.1, Ref. [ 43 ] ) .

###### Corollary 4 .

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. In the regime of Table 2 and Theorem 2.5 under the first-order assumption, are there known classical lower bounds?
2. What are the key algorithmic insights for results that achieve exponential speed-ups? 
3. In the final version, I will encourage the author to expand on open questions more systematically. In general, there are several open gaps to establish minimax optimal query complexities for the problem.
soundness: 4
strengths: The paper provides a comprehensive analysis of upper and lower bounds on query complexities of quantum algorithms for an important problem in non-convex optimization, and thus, the contributions are important to the community. The paper is well-written.
summary: This paper investigates the robustness of quantum algorithms for non-convex optimization, in the context of finding an $\epsilon$-approximate second-order stationary point ($\epsilon$-SOSP) in a d-dimensional non-convex function. As is usually done in optimization literature, the algorithm has access to the function via noisy zeroth or first-order oracles that satisfy certain standard assumptions. 

The paper provides several foundational results for this setup in both upper and lower bounds. The upper bounds, under zeroth and first-order oracles, respectively, are nicely summarized in Table 1 and Table 2 under different noise regimes. Notably, under the zeroth order assumption and low noise regimes, the algorithms achieve exponential speed-ups. Additionally, they establish lower bounds for classical and quantum algorithms, summarized in Tables 1, 2, and 3, under various noise regimes and Zeroth and First order Assumptions.
weaknesses: No major weaknesses. See questions.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: 1. Can you give a more descriptive title to Section 4.3 like the surrounding sections?
2. Table 3 is for lower bounds in $\epsilon$. But the zeroth-order lower bound for deterministic classical algorithm entry is still an expression in $d$.
soundness: 4
strengths: The paper provides a comprehensive set of results that cover a wide range of noise scale regimes, and oracle assumptions. The comparison with the classical results are meaningful and well presented.
summary: The work studies the task of finding $\epsilon$-approximate second-order stationary points of $d$-dimensional non-convex functions with zeroth- or first-order noisy quantum oracles. Under various different noise regimes (as functions of $\epsilon$ and $d$), the work presents upper and lower bounds for the classical and the quantum query complexities of the task. 
With zeroth order oracle, it has been shown that the quantum algorithm proposed gives an exponential speedup (against classic lower bound) when the noise is at a small scale of $\tilde O( \epsilon^6 / d^4 )$, and a polynomial speedup (compared to the state-of-the-art classical algorithm) when the noise is of scale $[ \tilde \Omega(\epsilon^6 / d^4), O(\epsilon^{1.5} / d) ] $.
With first-order oracle, there is a polynomial quantum speedup (compared to the state-of-the-art classical algorithm) when the noise is of scale $\Theta(\epsilon / d^{0.5})$.
weaknesses: The quantum query complexity bounds established are far from being tight.
Most of the algorithms are almost identical to the classical version with the gradient estimation replaced by Jordan’s algorithm. The analysis also looks like a rehash of the classical proofs by substituting the guarantees from Jordan’s algorithm. The lower bound constructions seem to be just borrowed from Jin et al., 2018a and Carmon et al., 2021 (up to a unitary rotation and a scaling factor).

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 1
questions: - It appears that $\nabla f(x+z) - \nabla f(x)$ is intended as an estimate of the Hessian rather than the gradient, as indicated in line 312?

-The most recent work that this paper compares against in Table 1 is from 2018. Are there been any more recent results in this direction?
soundness: 2
strengths: - Applying quantum oracles to speedup existing results is a timely and meaningful interesting problem.
- This work gives a dense collection of results.
- The summarization of the results in Tables 1, 2 and 3 is informative and clear.
summary: This paper studies how to apply quantum algorithms for finding the $\epsilon$-approximate second-order stationary point ($\epsilon$-SOSP) of a $d$-dimensional non-convex function, given noisy zeroth- (i.e., noisy evaluation query) or first-order(i.e., noisy gradient query) oracles as inputs. The study focuses on settings where only noisy zeroth-order (evaluation queries) or noisy first-order (gradient queries) oracles are accessible. Specifically, the authors analyze scenarios under various levels of noise, parameterized by poly $(\epsilon, 1/d)$,  and demonstrate that their approach significantly outperforms state-of-the-art (SoTA) methods regarding query complexity. Furthermore, they establish several lower bounds for alternative scenarios where efficient query complexity is not achievable with the current methods. Tables 1, 2 and 3 concisely summarize the main results, offering a comparative view of query complexity improvements relative to existing methods.
weaknesses: - The presentation of technical results in this paper feels somewhat vague; for instance, there is no pseudocode or intuitive explanation of the underlying algorithms. This lack of detail impacts the paper's clarity and readability.

- The current presentation makes it challenging to assess the paper's novelty. For instance, when referencing Jordan's algorithm, the paper points to [2] for details on Jordan's gradient estimation (line 223) and states that it "replaces the gradient queries in PAGD with this oracle" (line 232). However, there is insufficient discussion on the complexity of replacing the oracle, which obscures an evaluation of the paper's originality.

- There are no related discussions on when the noise levels are practical, for example, what problem setting would generate a noise level of $\tilde{\Omega} (\epsilon^{1.5} / d)$? 

- The definition of $\epsilon$-SOSP doesn't align with the one in [1]. Instead of letting $\|F(x)\| \leq \epsilon$, the saddle point should satisfy $\|\nabla F(x)\| \leq \epsilon$?


- Several notations are used for the same purpose in this work, for example, [line 119-130], $\||$ , | |, and | are used to denote similar norms. The reviewer would recommend using one notation to denote all the norms.

Minor Comments:
- Some $O(\cdot)$ sign probably should be $\Theta(\cdot)$ in the column "noise strength" in Table 1?

[1] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., & Jordan, M. I. (2017, July). How to escape saddle points efficiently. In International conference on machine learning (pp. 1724-1732). PMLR.

[2]Chakrabarti, S., Childs, A. M., Li, T., & Wu, X. (2020). Quantum algorithms and lower bounds for convex optimization. Quantum, 4, 221.

Meta-review: This is an interesting paper extensively studying the the complexity of finding an $\epsilon$-approximation of a second-order stationary point of a non-convex objective function via noisy zeroth-order and gradient queries. A few quantum poly(d,epsilon) algorithms were provided, and also a lower bound.

Overall the reviewers are positive about the paper. I recommend acceptance.

Decision: Accept (Poster)