Quantum Algorithms for Non-smooth Non-convex Optimization

We thank the reviewer for the positive and helpful comments.

To Weakness 1 (the presentation of Section 3):

Thank you for this question. Hopefully, the following explanation will give you a better picture of the structure of Section 3.

The main goal in Section 3 is to construct unbiased quantum estimators $\hat{{\bf g}}$ and ${\Delta}{\bf g}$, which will be used in Algorithms 1 and 2. We present the query complexities on ${\bf U}\_F$ in constructing these oracles in Section 3.2, Theorem 3.4.

The implementation of such (mini-batch) unbiased quantum estimators $\hat{{\bf g}}$ and ${\Delta}{\bf g}$ requires the access to quantum stochastic oracles ${\bf O}\_{{\bf g}\_\delta}$ or ${\bf O}\_{\Delta{\bf g}\_\delta}$, which are not given. Instead, we only have access to the quantum stochastic function value oracle $\mathbf{U}\_F$. We show the procedure for constructing ${\bf O}\_{{\bf g}\_\delta}$ and ${\bf O}\_{\Delta{\bf g}\_\delta}$ by ${\bf U}\_F$ and a quantum sampling oracle $\mathbf{O}\_{\xi, \mathbf{w}}$ in Lemma 3.2 and Corollary 3.3 in Section 3.1, respectively. Then, in Section 3.3, we explicitly show how this quantum sampling oracle $\mathbf{O}\_{\xi, \mathbf{w}}$ can be constructed from scratch.

A diagram showing the logic flow presented above is as follows:

$

\underbrace{\hbox{Section 3.3}}_{\text{Construct ${\bf O}\_{\xi,{\bf w}}$}} \longrightarrow \underbrace{\hbox{Lemma 3.2 and Corollary 3.3}}_{\text{Obtain ${\bf O}\_{{\bf g}\_{\delta}}$ and ${\bf O}\_{\Delta{\bf g}\_{\delta}}$ from ${\bf O}\_{\xi,{\bf w}}$ and ${\bf U}\_F$}} \longrightarrow \underbrace{\hbox{Theorem 3.4}}_{\text{Construct $\hat{{\bf g}}$ and $\Delta{{\bf g}}$ from ${\bf O}\_{{\bf g}\_{\delta}}$ and ${\bf O}\_{\Delta{\bf g}\_{\delta}}$}}

$

To Weakness 2 (discussion on the quantum speedup):

The quantum mean estimator (Theorem B.1) is one of the main ingredients providing the speedup which leads to better estimators of $\nabla f\_{\delta}({\bf x})$ and $\nabla f\_{\delta}({\bf y})-f\_{\delta}({\bf x})$ as presented in Theorem 3.4 (also see the discussion in Remark 3.5). However, achieving the speedup shown in Theorem 3.4 requires additional considerations, including implementing a sampling oracle for the desired distribution and constructing a stochastic gradient oracle from it and the function value oracle. A high-level picture of those steps is detailed above in our answer to Weakness 1.

Incorporating such better estimators in our quantum algorithm allows us to achieve better query complexities over the classical ones. More concretely, one needs to carefully select the variance level $\hat{\sigma}\_{1,t}^2$ in Algorithm 1 and $\hat{\sigma}\_{1,t}^2, \hat{\sigma}\_{2,t}^2$ in Algorithm 2 when utilizing the Theorem 3.4.

As for the speedup on the quantum mean estimator [13, 42] over classical estimators, it can be viewed as a consequence of combinations of quantum Fourier transform [A] and the quantum amplitude amplification algorithm [B].

We will involve more discussion on this in the revision.

[A]. Shor, P. W. “Algorithms for quantum computation: Discrete logarithms and factoring”. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1995.

[B]. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. “Quantum Amplitude Amplification and Estimation”. In: Contemporary Mathematics 305, 2002.

To Quetsion 1: The complexities of finding Clarke differential and smooth differential are not comparable due to the following reasons:

1. We do not assume $f(\cdot)$ is differential. Since $f(\cdot)$ it in general non-convex and non-smooth, thus the differential of it may be intractable.

2. There are no finite time algorithm that can find an $\epsilon$-stationary point such that $\|\|\partial f({\bf x})\|\|\leq \epsilon$ in non-convex and non-smooth setting, where $\partial f(\cdot)$ denotes the Clarke differential of $f(\cdot)$. Please refer to [Theorem 5, 51]. On the other hand finding an $\epsilon$-stationary point of a smooth differential in non-convex smooth optimization can be done in polynomial time [18, 31].

We thank the reviewer for the positive and helpful comments.

To Weakness 1 (discussion on the technical novelty):

We appreciate the feedback. We highlight our technical novelty on the construction of zeroth-order estimator and the design of quantum algorithms as follow:

• In term of the zeroth-order quantum estimator, utilizing the existing quantum mean value estimation procedure requires having a suitable quantum sampling oracle that returns a superposition over the desired distribution. We fixed the following gaps between this paper and the one of [42]:

  1. [42] requires the assumption of direct accesses of quantum stochastic gradient oracle. But this is not applicable in our setting because instead, we are given only access to quantum stochastic function value oracle ${\bf U}\_F$. We overcome this by providing the efficient procedure for constructing our wanted oracle from ${\bf U}\_F$ and sampling oracle $\bf{O}\_{\xi, {\bf w}}$, which is summarized in Lemma 3.2.

  2. Furthermore, [42] does not provide how to construct the quantum sampling oracle, which leaves a gap between the quantum algorithm and its detailed implementation on the quantum circuits. We fill this gap by giving an explicit and efficient construction on ${\bf O}\_{\xi,{\bf w}}$ for desired distribution in Section 3.3.

• In term of the quantum algorithms for finding the Goldstein stationary point, our new proposed quantum algorithms are quite different from the classical ones for finding the Goldstein stationary point and the quantum methods for non-convex optimization.

  1. The most related classical algorithm is GFM+[7], where they adopted SPIDER algorithm, while we adopt the PAGE-framework, which makes the algorithm single-loop. To the best of our knowledge, such framework has not been investigated in finding the Goldstein stationary point even for classical optimization.
  2. Our algorithm framework is also different from existing quantum algorithms for non-convex optimization, where they fixed the desired variance level when using quantum mean estimator, while we adaptively set the variance level and make $\hat{\sigma}_{2,t}\propto \|\|{\bf x}_t-{\bf x}\_{t-1}\|\|$, such strategy allows us not only to show the quantum advantage for finding the Goldstein stationary point in non-convex non-smooth optimization, but also to provide a better query complexity over the state-of-the-art non-convex smooth quantum optimization methods [42].

To Weakness 2 (Discussion on the Lower Bound):

We agree that including a result of quantum lower bound will make the investigation on this problem more well-rounded. But we don't think the lack of a lower bound would diminish our contribution for the following reasons:

1. The main purpose of this paper is to show the quantum advantage on non-convex non-smooth optimization. We have provided an upper bound of $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-7/3})$ for finding the $(\delta,\epsilon)$-Goldstein stationary point, which cannot be achieved by ANY of the classical methods due to the classical lower bound $\delta^{-1}\epsilon^{-3}$ established by [14, 30].

2. Even for non-convex smooth function, the quantum lower bound has not been fully investigated [42, 49]. There are only negative results that show no quantum speed-up for non-convex smooth optimization when the dimension $d$ is large [49]. On the other hand, the construction of classical lower bound for finding Goldstein stationary point is based on the lower bound of finding stationary point of non-convex smooth function [14, 30]. Hence, we think the quantum lower bound can be regarded as an important open problem for both non-convex non-smooth optimization and non-convex smooth optimization.

To Question 1:

Existing zeroth-order methods for finding the $(\delta,\epsilon)$-Goldstein stationary point of a non-convex non-smooth objective are to find the $\epsilon$-stationary point [7, 32, 33] or $(\delta,\epsilon)$-stationary point [29] of its smoothed surrogate $f_{\delta}({\bf x})$. However, there is a gap between the function value of $f(\cdot)$ and $f_{\delta}(\cdot)$, which can be only bounded by $|f(\cdot)-f_{\delta}(\cdot)|\leq \delta L$. This yields a factor of $\delta^{-1}$ in iteration complexities, which is irrelevant to using classical or quantum oracles.

Therefore, we think the improvement on $\delta$ dependency cannot be achieved by existing algorithm framework and leave it as an important future work.

To Minor Issues 1-5: Thanks for pointing out these. We will make the consistency of the big-O notation in the revision and fix the typos.

We thank the reviewer for the positive and helpful comments.

To Weakness 1: We think the assumption of having a quantum stochastic function value oracle is reasonable and not strong due to the following reasons:

1. It is very common to assume having a classical stochastic function value oracle, when the objective is in the form of expectation [7, 30, 32, 33].

2. One can efficiently construct such quantum stochastic function value oracle with the same asymptotic computational complexity by replacing the gates in the classical circuit with reversible gates [38].

Such quantum stochastic function value oracle is important to further design quantum algorithms.

To Weakness 2: Utilizing the existing quantum mean value estimation procedure requires having a suitable quantum sampling oracle that returns a superposition over the desired distribution. The closest work to ours is [42], which utilizes quantum mean estimation in non-convex optimization. We state below the technical novelty in our paper:

1. [42] requires the assumption of direct accesses of quantum stochastic gradient oracle. But this is not applicable in our setting because instead, we are given only access to quantum stochastic function value oracle ${\bf U}_F$. We overcome this by providing the efficient procedure for constructing our wanted oracle from ${\bf U}_F$ and sampling oracle ${\bf O}\_{\xi, {\bf w}}$, which is summarized in Lemma 3.2.

2. Furthermore, [42] does not provide how to construct the quantum sampling oracle, which leaves a gap between the quantum algorithm and its detailed implementation on the quantum circuits. We fill this gap by giving an explicit and efficient construction on ${\bf O}\_{\xi,{\bf w}}$ for desired distribution in Section 3.3.

In conclusion, our technical novelty on quantum part is to provide an explicit and efficient construction of quantum $\delta$-estimated stochastic gradient oracle (Definition 3.3) by using quantum stochastic function value oracle.

To Question 1: We give a more specific description: Given $|{\bf x}\rangle \in \mathcal{H}^m$ and $|{\bf y}\rangle \in \mathcal{H}^n$, we denote their tensor product by $\ket{\bf x} \otimes \ket{\bf y}\triangleq (x_1y_1, x_1y_2 \cdots, x_1y_n, x_2y_1, \cdots, x_m y_n)^\top \in \mathcal{H}^{m\times n}$.

To Question 2: We want to first respectfully point out that it is inappropriate to compare computational complexity and query complexity. Computational complexity considers the number of basic operations or gates used, whereas query complexity measures the number of calls to a particular process in a black-box manner. In generally, this process can cause significant costs (including a large number of basic operations) or may not be efficiently computed locally.

This paper focus on the query complexities, which follows the previous work in [4, 5, 42]. Unlike [42] which does not consider the implementation of the sampling oracles, our Section 3.3 enables us to give the gate counts for constructing one quantum $\delta$-estimated stochastic gradient oracle.

Specifically, the steps in Lemma 3.2 needs $1$ access to sampling oracle, $1$ addition operation, $2$ subtraction operations, and $1$ multiplication operation. Hence, the gate complexity stems from the two parts below:

1. The gate complexity for implementing the sampling oracle is $\mathcal{O}(\lceil\log N\rceil + \log (1/\epsilon_0) d)$ where $N$ is the number of the stochastic components of $\xi$, and $\epsilon_0$ being the incurred precision error. More precisely, this construction utilizes $\lceil\log N\rceil + \log (1/\epsilon_0) d$ Hadamard gates and $d-1$ circuits of calculating $\sin$ and $\cos$ on a single qubit.

2. There are various existing methods to implement quantum arithmetic operations, e.g. [41]. Using methods from [41] gives implementations of addition, subtraction and multiplication with gate complexity $\mathcal{O}(C^2)$, $\mathcal{O}(C^2)$, and $\mathcal{O}(C^3)$, respectively, where $C$ is the number of qubits that represent the numbers being manipulated in our algorithm and is usually independent of $d$, $\epsilon$, and $\delta$.

Hence, the asymptotic total gate complexity for constructing one quantum estimated gradient oracle is $\mathcal{O}(\lceil\log N\rceil+\log (1/\epsilon_0) d + C^3)$.

To Limitation 1: We agree that including a result of quantum lower bound will make the investigation on this problem more well-rounded. But we don't think the lack of a lower bound would diminish our contribution for the following reasons:

1. The main purpose of this paper is to show the quantum advantage on non-convex non-smooth optimization. We have provided an upper bound of $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-7/3})$ for finding the $(\delta,\epsilon)$-Goldstein stationary point, which cannot be achieved by ANY of the classical methods due to the classical lower bound $\delta^{-1}\epsilon^{-3}$ established by [14, 30].

2. Even for non-convex smooth function, the quantum lower bound has not been fully investigated [42, 49]. There are only negative results that show no quantum speed-up for non-convex smooth optimization when the dimension $d$ is large [49]. On the other hand, the construction of classical lower bound for finding Goldstein stationary point is based on the lower bound of finding stationary point of non-convex smooth function [14, 30]. Hence, we think the quantum lower bound can be regarded as an important open problem for both the non-convex non-smooth optimization and the non-convex smooth optimization.

To Limitation 2: Our algorithms don't need QRAM. Remark 3.7 serves as a discussion for general scenarios on the distribution of $\xi$. More concretely, a distribution that can be efficiently sampled classically guarantees an efficient construction of a quantum sample oracle over it; while for other cases, QRAM might be needed on a case-by-case basis.

Thank the authors for the detailed response! Since the quantum upper bound provided in the paper is $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-7/3})$, while a possible classical upper bound is $\mathcal{O}(d\delta^{-1}\epsilon^{-3})$ the classical lower bound is $\delta^{-1}\epsilon^{-3}$, does it mean that quantum speedup can only occur when the requirement of the precision is relatively high compared with the dimension, given the dimension fixed? If so, regarding current physical realization constraints like noises in quantum devices, it seems that this result is more of a theoretical one with few potential applications. Another problem is the time/gate complexity part. Thank the authors for their effort to analyze and calculate the gate cost in great detail of constructing one quantum estimated gradient oracle. However, it seems that for one call of the gradient oracle, the cost is at least proportional to the dimension, which is relatively expensive for some problems and may be a major concern in solving them. Due to the above reasons, I'll keep my rating currently and keep in mind your detailed comments for future discussions.

We thank the reviewer for the positive and helpful comments.

To Weakness 1: We think such sub-optimal dependency on $d$ is reasonable due to the following reasons:

1. The sub-optimality on dimension $d$ is a common trade-off in quantum optimization. [49] proved that there are no quantum speedups for finding stationary points of a non-convex smooth object function when the dimension $d$ is large. [42] showed that it requires $\mathcal{O}(\sqrt{d}\epsilon^{-2.5})$ queries of quantum stochastic first-order oracle to find the $\epsilon$-stationary point of a non-convex smooth objective, while the classical optimal methods [18, 31] require $\mathcal{O}(\epsilon^{-3})$ queries. This paper considers a more difficult function class which is non-convex and non-smooth.

2. The algorithm frameworks pointed out by the reviewer in Kornowski and Sharmir [30], Cutkosky et al. [14] construct the gradient estimator by $2$-queries of stochastic function value oracle or one query of stochastic gradient oracle, which means we cannot apply quantum mean estimator to improve such estimator. Hence, whether using their framework can recover the $\mathcal{O}(d)$ dependency while still improve the dependency on $\epsilon$ is not clear.

To Question 1: We answer this question from the following two aspects:

1. The quantum oracles can be viewed as instances of quantum circuits. Since the current hardware implementation of quantum computers is still in a relatively early stage, the practical feasibility of implementing these quantum circuits depends on factors such as the size of the circuits and the types of gates used.

2. The gates used in constructing our quantum stochastic gradient oracle, aside from the provided black-box quantum function value oracle, are primarily simple single-qubit and two-qubit gates, such as Hadamard gate, controlled NOT gate, and controlled rotation gate, which are known to be efficiently implementable [A]. Therefore, if the size of our problem is not large and the black-box quantum function value oracle is practically feasible, then our algorithm can be practically feasible.

[A]. Groenland, Koen, et al. "Signal processing techniques for efficient compilation of controlled rotations in trapped ions." New Journal of Physics, 2020.

To Question 2 and 3: Yes. Your understanding is correct and we will make them clear in the revision.

To Question 4: Thanks for pointing out this. For part 1, it should be $\mathbb{E}\left[\||\hat{{\bf g}}-\nabla f\_{\delta}({\bf x})\||^2\right]\leq \hat{\sigma}\_1^2$, which is a typo. For part 2, it should be $d^{3/2}L\|\|{\bf y}-{\bf x}\|\|\hat{\sigma}_{2}^{-1}\delta^{-1}$, where we forget to present the dependency on $\delta$.

They do not impact the results of Theorem 4.1 and Theorem 4.3. Part 2 of Theorem 3.4 only impact the size of $b_1$ in Theorem 4.3. We determine the size of $b_1$ in line 507 of Appendix D by setting

according to line 494, then we have

$

b\_1 = \tilde{\mathcal{O}}\left(d^{3/2}L\|\|{\bf x}\_{t+1}-{\bf x}\_t\|\|\hat{\sigma}\_{2,t}^{-1}\delta^{-1}\right)
 = \tilde{\mathcal{O}}\left(d^{3/2}L\|\|{\bf x}\_{t+1}-{\bf x}\_t\|\| (\epsilon^{-1/3}\|\|{\bf x}\_{t+1}-{\bf x}\_t\|\|^{-1}L^{-2/3}d^{-1/2}\delta)\delta^{-1}\right)
 = \tilde{\mathcal{O}}\left(dL^{1/3}\epsilon^{-1/3}\right),

$

which means $b_1$ remains the same and it is independent of $\delta$.

We will fix them in the revision.

To Question 5 and 6: Thanks for pointing out these, we will modify them in the revision.