Quantum Algorithms for Non-smooth Non-convex Optimization
Authors: Chengchang Liu
Chaowen Guan
Jianhao He
John C.S. Lui
Venue: NeurIPS 2024 poster (2024)
Keywords: quantum computing
non-convex non-smooth optimization
Primary area: optimization
TL;DR: We show the quantum speedups for finding the Goldstein stationary point by proposing gradient-free quantum algorithms.

Abstract: This paper considers the problem for finding the  $(\delta,\epsilon)$-Goldstein stationary point of Lipschitz continuous objective, which is a rich function class to cover a great number of important applications. 
We construct a novel zeroth-order quantum estimator for the gradient of the smoothed surrogate. 
Based on such estimator, we propose a novel quantum algorithm  that achieves a query complexity of $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-3})$ on the stochastic function value oracle, where $d$ is the dimension of the problem. 
We also enhance the query complexity to $\tilde{\mathcal{O}}(d^{3/2}\delta^{-1}\epsilon^{-7/3})$ by introducing a variance reduction variant. 
Our findings demonstrate the clear advantages of utilizing quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods on the dependency of $\epsilon$ by a factor of $\epsilon^{-2/3}$.

Quantum Algorithms for Non-smooth Non-convex Optimization
Chengchang Liu"
Chaowen Guan
Jianhao He
John C.S. Lui
The Chinese University of Hong Kong
University of Cincinnati
71 Liichennchangg@@mail com j jinhaoheeCcuhk edu.hk
guance@ucmail. uc. ww..duee. edu cslui@cse. cuhk, edu hk
Abstract
This paper considers the problem of finding the (ō, --Goodstein stationary point of the Lipschitz continuous objective, which is rich function class cover a large number of important applications. We construct a novel zeroth-order quan- tum estimator for the gradient of the smoothed surrogate. Based on such estima- tor, we propose a novel quantum algorithm that achieves query complexity of (dd128811-)) on the stochastic function value oracle, where d is the dimension of the problem. We also improve the query complexity to 0(d8/28-1<-7/)) by introducing variance reduction variant. Our findings demonstrate the clear ad- vantages of using quantum techniques for non-convex non-smooth optimization, as they outperform the optimal classical methods in dependence on by factor of 2/3
Introduction
In this paper, we study the following problem
min (f(x) = Be [F(;;))) xeE
(1)
where the stochastic component F I--ipsshitz continuous but possibly non-convex and non-smooth. This problem has received increasing attention recently because it is general enough to
cover many important applications, including deep neural networks (21, 40], reinforcement learn-
ing (9, 49 and statistical learning [17. 39 62
Due to the absence of both smoothness and convexity the objective function, neither the gradient nor the sub-differentials are valid anymore to measure the convergence behavior. The Clarke subdif- ferential is a natural extension for describing the first-order information the Lipschitz continuous function [10]. however, it is intractable for finding the near-approximate stationary point in terms of the Clarke subdifferential as suggested by the hard instances [31. 50, 63]. Zhang et al. [63] intro- duce the notion of (6, -)Gooddstnin stationary point (cf.. Section 2.2). which weakens the traditional stationary point by considering the convex hull of the Clarke subdifferentials. Following this, we focus on the problem of finding the (6, -)Gooddstiin stationary points of the objective.
There are many optimization methods for finding the (o.o)-Goldstein stationary points via classical stochasic oracles [G. 14. 28. 31
52 633) Zhang et al. (63] proposed stochastic interpo- lated normalized gradient descent method (SINGD) with the first non-asymptotic result, which has
35, 47.
the stochastic first-order complexity of ( Later, Tian al. [52] developed the perturbed
denotes equal contributions: denotes the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: We summarize the complexities of classical and quantum veroth-order methods for finding the (c, (c,5)-Golll -Goodsttnii point of a non-smooth non-convex objective, where d is the dimension of the problem.
Methods
Oracle
Query Complexity
Reference
GFM
classical
0 (1
Lin et al. [35]
GFM+
classical
O (1)1281)))
Chen et al. [6]
OptimalZO
classical
0 (
Kornowski and Shamir [32]
QGFM
quantum
Ô (1128-1(2))
Theorem
QGFM+
quantum
Ô (18128-16-113
Theorem
Table 2: We summarize the complexities of classical and quantum first-order methods for finding the c-stationary point of a smooth non-convex objective, where is the dimension of the problem.
Methods
Oracle
Query Complexity
Reference
SPIDER/PAGE
classical
0
Fang al. [18). Li et al. [34]
Q-SPIDER
quantum
(1122
Sidford and Zhang [48)
QGM+
quantum
(1132(-)13)
Theorem
SINGD method which queries the gradient at the differentiable point and established the same com- plexity. Cutkosky et al. [13] improved the stochastic first-order oracle complexities to ( by using the "online to non-convex conversation", assuming f(-) is differentiable. This improvement aligns with the theoretical lower bound [1]]
Zeroth-order methods, which only query the function value oracle, are more practical for the Lips- chitz continuous objective. This is because computing first-order oracles can be extremely challeng- ing 29 52
or even inaccessible for numerous real-world applications [16, 27. 43 Lin et al. [35 proposed a gradient-free method find the ( stationary point within (62 1 query complexity to the stochastic function value via connection between the randomized smooth- ing (41) and the Goldstein stationary point. This complexity was further improved to O (d3/2-1ee" and ((d8-1e-3) by Chen al. [6]. Kornowski and Shamir (32) respectively. However, all these methods using the classical oracles to find the Goldstein stationary point face a bottleneck of 8-1--3
due to the lower bound reported by [1]]
Recently, we have witnessed the power of quantum optimization methods by accessing the quantum counterparts of classical oracles for non-convex optimization 77. 23
61. 644, convex opti- 54). However, most these results focus deterministic methods and the case where the objective function is smooth. Garg et al. [19] and Zhang and Li (60] showed the negative results for non-smooth convex and smooth non- conver optimization that quantum algorithms have improved rates over classical ones when the dimension is large. Sidford and Zhang [48] proposed stochastic quantum methods which show the advantage of using quantum stochastic first-order oracles for smooth objectives when the dimension is relatively small. To the best of our knowledge, there is no work showing the quantum speedups for minimizing non- smooth non-convex objectives, which the most general and fundamental function class. Based on this, it is natural question to ask:
37.
48
mization 44. 5. 48. 55, 644,, and semi-definite programming [, 2. 53,
Can we go beyond the complexity of (88 to find the (ō. ( Goldstein stationary point for non-smooth non-comvex stochastic optimization by involving quantum oracles?
We give an affirmative answer to the above question by proposing novel quantum zeroth-order meth- ods and showing their explicit query complexities. We summarize our contributions as follows.
We construct efficient quantum gradient estimators for the smoothed surrogate of the objectives with O(1)-queries of the function value oracles, which allows to construct efficient quantum

---

zeroth-order methods. Moreover, we provide explicit constructions of quantum superposition over required distributions. We present these results in Section Appendix
We propose the quantum gradient-free method (QGFM) and the fast quantum gradient- method (QGFM+) for non-smooth non-convex optimization. We achieve the query complexities of ( --=))) for QGFM and 0 for QGFM+ in finding the (Goldseen stationary point using quantum stochastic function value oracle. The query complexity of QGFM+ surpasses the optimal result achieved by classical methods by factor of -//3, We compare our methods with the classical zeroth-order methods in Table I and present the results in Section
We generalize the algorithm framework of QGFM+ for smooth non-conver optimization (i.e. the gradient of the objective function is Lipschitz continuous). We propose the fast quantum gradient method (QGM+), which takes the advantage of QGFM+ to choose the variance level adaptively. QGM+ enjoys improved complexity of (d (//)) queries of the quantum stochastic gradi- ent oracle, which outperforms the existing state-of-thh-aad method (Q-SPIDER (48]) by factor of -1/6 We compare our method with the classical and quantum first-order methods in Table
A discussion of this is presented in Remark 4.5 and the formal results are stated in Appendix G
2 Preliminaries
We introduce preliminaries for quantum computing model and non-smooth non-convex optimization in this section.
2.1 Preliminaries for Quantum Computing Model
Here we formally review the basics and some concepts from quantum computing with which we work. For more details, Nielsen and Chuang (42)
Quantum Basics. A quantum state can be seen as vector x (2............... Rm) in the Hilbert space Hmm such that Σ, |0,22 1. We follow the Dirac bra/ket notation on quantum states, i.c., we denote the quantum state for x by (x) and denote x by (x) where + means the Hermitian conjugation.
Given a state (w) = Σ:- G/i),, we call o C the amplitude of the state (i). Given two quantum states (x) e 7 and ly) E H.m, we denote their inner product by (xly) = E, x/9. Given (x) H. denote their tensor product by (x) ly) & "", measure state (b)) = E cale) on a computational basis, we will obtain with probability le,1 and the state will collapse into (i) after measurement for all A quantum algorithm works by applying a sequence of unitary operators to a initial quantum state.
and ly) H".
H If
Quantum Query Complexity. Corresponding to the classical query model, quantum query com- plexity considers the number of queries to a black box of a particular function which needs to be invoked to solve problem. In many cases, the black box corresponds highest overhead, and therefore reducing the number of queries to it will effectively reduce the com- putational complexity of the entire algorithm. For example, if a classical oracle C, for a function if is a black box that, when queried with a point x, outputs the function value C)(x) fxx), then the corresponding quantum oracle U, is unitary transformation that maps a quantum state (x) (g) to the state (x) lg + f(x).. Moreover, given the superposition input Σx.q Ox,a (x) (q). applying the quantum oracle once will, by linearity, output the quantum state Σx,g 0x.g (x) (g f(x)).
the process that has the
2.2 Preliminaries for Non-convex Non-smooth Optimization
We introduce the necessary background for non-convex non-smooth optimization, with the follow- ing mild assumption that the objective function is Lipschitz continuous.
Assumption 1. We assume the stochastic component F(:EE) of the objective f(.) satisfies that
IF(x;)) Fly: s T.Ix-ll yyl every x,y (Rd. In addition, we assume f Rdd R. is lower bounded and denote f infxeee f (x))
3

---

The Rademencher theorem indicates that f()) is differentiable almost everywhere under Assump- tion which allows us to define its Clarke subdifferential as follows [10].
Definition 2.1 (Clarke sub- dib-diffferentil)). The Clarke aub-differential of a Lipschita, at point x is defined by (x) conv {g g limxe-x (x(
We then introduce the Goldstein subdifferential (22) and the (6.cc-Gol stationary point
63
Definition 2.2 (Goldstein sub-differential). The Goldstein subdifferential of Crrschitz.functiin at point x is defined by f fx) = conv (x)=B.(x)0ff)))
Definition 2.3 ((6, GGoldttni stationary point). We call x the (ő, c)-Goldsteiin stationary point of a given Lipschitz function if satisfies dist(O, (x)( e, where Oxf(x) is the Goldstein subdif- ferential.
Next, we define the smoothed surrogate of f() as follows. Definition 2.4 (ó-smoothed surrogate). The 8-smoothed surrogate of f is defined by
fx(x) Ew-p [f(x 6w)],
where P the uniform distribution on unit ball.
Although f(-) is non-smooth, its smoothed surrogate fa(() enjoys some good properties as presented
the following proposition (6, 15 35 59).
Proposition 2.1. If f()) satisfies Assumption I its smoothed surrogate fo(.) satisfies that:
f() 6L and lfs(x) fo(y)) L|x yl.
* Vfs(-) is e evddo= Lipschirz, for some constant e > O, i.e. [Vf((x) - V sevd
ff((-) O-)()). where f-) is the Goldstein subdifferential.
Remark 2.2. Proposition 2. implies that the task of finding the (d.e)-Goldstein stationary point of f() is equivalent finding the e-stationary point of smoothed function fa(-), i.e. finding some point x such that VV c.
3 Zeroth-order Based Stochastic Quantum Estimator
In this section, we present a novel quantum estimator for the gradient of the smoothed surrogate fs(-) by using the quantum stochastic function value oracle, which is essential for designing our quantum algorithms for non-convex non-smooth optimization.
3.1 Quantum Estimators via Quantum Stochastic Function Value Oracle
In this section, we construct quantum estimators for the gradient of the smoothed surrogate by O(1) -queries of the quantum stochastic function value oracle.
We start with the definition the stochastic function value oracle. Classically, a stochastic function value evaluation is defined F(x. {) for function f IRd IR with Ç such that Eg (xx {) fxx.. this work, we assume access quantum stochastic function value oracle Ur for f()). which is defined as follows.
Definition 3.1 (Quantum stochastic function value oracle). For f IRd R. the quantum stochastic
function value oracle, denoted by Ur, works as: Up (x) ()) (b) xx) @ (E) @ F(x,
where Fxx.5 {) is sampled from a distribution (-)-) such that Eg [x: [)] F(x).
is common to construct the following stochastic gradient estimator for (-a
6
32
35
36
d
(x::; w. x) 28
(F(x dw;:) - - F(x - ddx;) ww,
where w Rdd uniformly distributed on a unit sphere. The following proposition shows that (x(x; w) is good estimator of f.))..

---

Proposition 3.1 (6., Proposition and 4]). Under Assumption i.e. the random variable & satisfies that
[F F(y:))
and =
(4)
hold for all x.y ER., then (ox:w, defined in eq. 3 satisfies that Ew.g[gs(x;))) (, v Ew wwws<lllss((; w. v fx(() [+)) endL,, and Ew.slllss w. ga wI s L yl
where 16
Next, to exploit the power of quantum algorithms,, we generalize (3) to its quantum counter- part. Based on eq. (3 and Proposition [.1] g& (x; w) can interpreted as a random variable. In the quantum setting, accessing a random variable typically involves querying quanium sampling oracle, which returns quantum superposition over the associated distribution.
Definition 3.2 (Quantum sampling oracle). For a random variable with sample space Q its quantum sampling oracle Ox is defined as Ox [0) - Σx /PrpP[[x x @ |/xx), where ((xx) is arbitrary quantum state for every
The content in the second quantum register can also be viewed as possible quantum garbage appear- ing during the implementation of the oracle. Observe that we directly measure the output of Ox, it will collapse to a classical sampling access to X that returns a random sample x with respect to probability Pr[X x]. Note that the output of Ox x can also be represented integral continuous random variables, as used in [8 48].
observation that gx(x; (,; E) can be viewed random variable, our target oracle Og, uus-quntumm stochastic gradient oracle-is essentially a quantum sampling oracle. Given this, formally define the quantum 8-estimated stochastic gradient oracle as follows.
Hence, based
Definition 3.3 (Quantum 5-estimated stochastic gradient oracle). For fo(.) Rd R, its quantum 5-estimated stochastic gradient oracle is defined as
xx)
00) - (x) @
EVPrrW.EIIBssxxww @ Www.e),
&,w
where the random variable w uniformly distributed unit sphere and & satisfies eq.
estimator of Vss, and can be calculated with access to quantum 5-estimated stochastic gradient oracle as defined above. The following theorem shows that such an oracle can be built with only O(1) access to the quantum stochastic function value oracle.
Proposition 3.1 implies g-(-) can
Lemma 3.2. Given access to quantum sampling oracle Og,w to the joint distribution on (E, w) construct quantum 8-estimated stochastic gradient oracle (as defined in Definition 3.3 with two queries to the quantum stochastic function value oracle Up.
Remark 3.3. In Lemma 3.2
we assume a black- black-box access to quantum sampling oracle Og.w fol- lowing Sidford and Zhang [88] We present the explicit construction of this oracle in Appendix
Similarly, also constructed the estimator of (xx))) fy) by the following oracle:
O (x)
0)
xx) & Σ
w,, gs gy(:w,E)) @ ((w.e),
with only -querris of stochastic quantum function value oracle.
Corollary 3.4. Under the same conditions in Lemma 3.2 one can construct O O with four queries to the quantum stochastic function value oracle U
3.2 Mini-batch Quantum Estimators via Quantum Mean Estimation
We constructed the quantum oracles Og and Oage with O(1)-queries of quantum function value oracles in Section 3.1 These oracles produce outputs in the form of random variables. Specifically..O O provides an output with expectation fss(x) with the input x, and O Agg provides an output with expectation V fx() fys(y) for O Dags with the inputs x and
5

---

Algorithm Quantum Gradient-Free Method (QGFM)
1: for fort=0, 0,1,
2: Construct g: as an unbiased quantum estimator of V.ā((x)) with variance at most of using
UF according to Theorem 3.5
3: Xt+1 = X - 7
4:
end for
The variance of the outputs can be reduced by constructing the mini-batch estimator. Inspired by the recent advance on quantum mean estimation 11, 12 48 which improve the classical mini- batch estimator for multi-dimensional random variables, we construct improved estimators for (s((x) and v v v.s(y). We formally present the results the following theorem.
Theorem 3.5. Under Assumption D and given access to quantum sampling oracle Og. to the joint distribution on (E. w). it holds that:
1. there exists an algorithm that can construct an unbiased quantum estimator & of Vf((x) such that E. [1g vfs(x) &
s oî within (dd.āy)) queries Up in expectation.
2. there exists an algorithm that can construct an unbiased quantum estimator Ag of fx((x)) Vss(y) such that E. [11A -V/I(())VV queries Up in expectation.
62 within O x x11ā210-1
Remark 3.6. Compared to the classical mini-batch estimator for Vx(()), which requires OdT,aa7²) queries of CF to achieve the level of variance of (Ld Corollary 2.1]), our mini-batch quantum estimator for v f in Theorem 3.5 reduces a factor of L without increasing the dimension dependence.
4 Quantum Algorithms for Finding the Goldstein Stationary Point
In this section, we develop novel quantum algorithms for finding the (GooddGGl stationary point of non-smooth non-convex objective f()). Instead of finding the stationary point directly, we consider finding the e-stationary point of its smoothed surrogate fa).. which is equivalent to the original problem according to Remark 2.21 The classical zeroth-order methods based on such equivalence require to access the gradient estimator to (-) by stochastic function values (d 32 35. 36]. Different from the classical methods, which can be constructed by accessing quantum stochastic function value oracles due to our novel results in Section
take the advantage of the quantum estimators,
We first propose an algorithm which uses the quantum gradient estimator to replace fx((x) to do the gradient descent step at each iteration. We present the quantum gradient-free method (QGFM) in Algorithm [ Given desired variance level o? line and efficiently by the quantum stochastic function value oracles UF according to Theorem 3.5 The following theorem gives the upper bound on the total U that Algorithm require to access for finding the (ò, e G)ooosstti stationary point.
Algorithm can be constructed explicitly
Theorem 4.1. Under Assumption
Z by setting the parameter in Algorithm 0 as
(2 and o = then the total queries of stochastic quantum function value oracle UF for finding the Golds-Gol stationary point of f(-) can be bounded by Ö (d312 L L2A
6e
where A = fxx)) - Remark 4.2. QGFM(Algorithnl) T speedups the gradient-free method (GFM) stationary point by a factor of 1
35 for finding (d,
In particular, Algorithm | utilized a simple gradient descent step to achieve 1(8-1c which is
optimal for classical zeroth-order and first-order methods in terms of and 6. It is worth mentioning that the classical methods that achieve this lower bound typically involve multiple loops (6) or rely on additional online optimization algorithms 13 32
To further enhance the query complexity Theorem
we propose the fast quantum gradient- free method (QGFM+) by incorporating variance reduction techniques, outlined in Algorithm

---

Algorithm Fast Quantum Gradient-Free Method (QGFM+)
1: Construct go as an unbiased estimator of (xf( with variance at most 07.0-
2: for 0.1...7
3: Xt+1 X, 7/t
4: Flip a coin 0, e {0,1) where P(0: 1) Pt
5: If 0, = then
6: Construct gi-1 unbiased quantum estimator of Vf((x(-1) with variance at most fi.+1 using UF according to Theorem 3.5
7: else
8: Construct Ag++ as an unbiased quantum estimator of (x(x (x)( with variance
at most 02,4+ using Up according to Theorem 3.5
9:
= = Agæ+1
10:
end for
QGFM+ can be seen as a quantum-acceeleratel version of GFM+ (d). Unlike GFM+, which required double loops. QGEM+ simplifies the implementation by using a single loop based the PAGE framework [34]. Moreover, we replace all classical estimators with quantum estimators lines
and 8 of Algorithm 2 These quantum estimators
be constructed efficiently using stochastic quantum function value oracles with a desired variance level, as demonstrated Theorem 3.5 We present the total number of queries of Up for QGFM+ in the following theorem. We present the total queries F for QGFM+ in the following theorem.
Theorem 4.3. Under Assumption 7 by setting the parameters in Algorithm as follows
" = 82 Dr 2==
= and o²,, 2/3 4/3 X x 13/02,
then the total queries of stochastic quantum function value oracle UF for finding the (6, (GlossGtn stationary point of I(.) can be bounded by Ô (d3/2
1,71
+ 1,43 where f(xo) - --
277
Remark 4.4. QGFM+ (Algorithm) 2 speedups the GFM+ for finding (6, -stationnyy point by factor of Le 22/3.
We can see that QGFM+ achieves the query complexity of (1332 which cannot be achieved by any of the classical methods. Furthermore, we observe the applicability of our frame- work to smooth non-conver optimization.
Remark 4.5. QGFM+ is different from the quantum speedups algorithm (Q-SPIDER) for non- convex smooth stochastic optimization [48]: QGFM+ adjusts the variance level of Ag, according to the difference between the current iteration point and the previous one, while Q-SPIDER fixes the variance levels. Using the adaptive variance level and the QGFM + framework, accelerate the Q-SPIDER for smooth non-convex optimization. In Appendix G we propose the fast quantum gradient method (QGM +) with the query complexity of ((Vde-7/3) which improves the one of (vdee" 552)) obtained in Sidford and Zhang [48).
further
Conclusion and Future Work
In this paper, we have presented quantum algorithms for finding the (8, e) Golddsttn stationary point for a non-smooth non-convex objective. Our query complexities demonstrate clearly quantum speedup over the classical methods. future work, would be intriguing to explore the framework without ideal distributions which is caused by the limitation of classical or quantum resources. It also interesting find the quantum speedups for deterministic methods [14, 28 51] or the NS- NC objective with constraints [38]. We are also interested in seeing if similar strategies can be
applied to quantum online optimization with zeroth-order feedback [25. 26 33 56. 58]. The query
complexity of the proposed methods still have heavy dependency on the dimension: it is also possible to reduce the dimension dependency based on other quantum techniques and design efficient first- order quantum methods.

---

Acknowledgement
Chengehang Liu thanks Luo Luo and Zongqi Wan for a valuable discussion. The work of John C.S. Lui was supported in part by the RGC GRF:14207721.
References
[1] Fernando GSL Brandao and Krysta M Svore. Quantum speed-ups for solving semidefinite pro- grams. In 2017 JEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 415 426. IEEE, 2017.
[2] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen- Lin, Krysta M Svore, and Xiaodi Wu. Quantum sdp solvers: Large speed-ups. optimality, and applications quan- tum learning. 46th International Colloquium on Automata, Languages, and Programming
(ICALP 2019). schloss-Dagstuh-LLebbnii Zentrum für Informatik, 2019.
[3] Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308-1) 2018
[4] Shouvanik Chakrabarti, Andrew M Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020.
[5] Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang. and Xiaodi Wu. Quantum algorithm for estimating volumes of convex bodies. ACM Transactions on Quantum Computing, 4(3):1-60, 2023.
[6] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. ICML, 2023.
[7] Andrew M Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang. Quantum simulation of real-space dynamics. Quantum, 6:860, 2022.
[8] Andrew M Childs, Tongyang Li. Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang. Quan- tum algorithms for sampling log- log-concave distributions and estimating normalizing constants. Advances in Neural Information Processing Systems, 35:23205 23217, 2022.
[9] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. Interna- tional Conference on Machine Learning, pages 970-978. PMLR, 2018.
[10] Frank H Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
[11] Arjan Cornelissen and Yassine Hamoudi. A sublinear-time quantum algorithm for approximat- ing partition functions. In Proceedings of the 2023 Annual ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 1245-1264. SIAM, 2023.
[12) Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 33 43, 2022.
[13] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non- convex optimization through online-to-non-come conversion. In International Conference on Machine Learning, pages 6643-66700 PMLR, 2023.
[14] Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. A gradient sampling method with complexity guarantees for lipschitz functions in high and low dimensions. Advances in neural information processing systems, 35:6692-6703, 2022.
[15] John C Duchi, Peter L Bartlett, and Martin Wainwright. Randomized smoothing for stochas- tie optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[16] Darrell Duffie. Dynamic asset pricing theory. Princeton University Press, 2010.

---

[17] Jianqing Fan and Runze Li. Variable selection via nonconeave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456):1348-1300 2001.
[18] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018.
[19] Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No quantum speedup over gradient descent for non-smooth convex optimization. arXiv preprint arXiv:2010.01801, 2020.
[20] Craig Gidney. Asymptotically efficient quantum karatsuba multiplication. arXiv preprint arXiv:1904.07356, 2019.
[21] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 315-323, JMLR Workshop and Conference Proceedings, 2011.
[22] AA Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13:14-22, 1977.
[23] Weiyuan Gong, Chenyi Zhang, and Tongyang Li. Robustness of quantum algorithms for non- convex optimization. arXiv preprint arXiv:2212.02548, 2022.
[24] Lov Grover and Terry Rudoiph. Creating superpositions that correspond to efficiently inte- grable probability distributions. arXiv preprint quant-ph/02081 12, 2002.
[25] Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li. Quantum algorithm for online convex optimization. Quantum Science and Technology, 7(2)025022, 2022.
[26] Jianhao He, Chengehang Liu, Xutong Liu, Lyzhou Li, and John CS Lui. Quantum algo- rithm for online exp-concave optimization. In Forty-first International Conference on Machine Learning, 2024.
[27] Jeff Hong, Barry L Nelson, and Jie Xu. Discrete optimization via simulation. Handbook of simulation optimization, pages 9-44, 2015.
[28] Michael Jordan, Guy Komnwski,, Tianyi Lin, Ohad Shamir, and Manolis Zampetakis. De- terministic nonsmooth nonconvex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 4570-4597, PMLR, 2023.
[29] Sham M Kakade and Jason D Lee. Provably correct automatic sub-differentiation for qualified programs. Advances in neural information processing systems, 31, 2018.
[30] lordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Inno- vations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibri Zentrum fuer Informatik, 2017.
[31] Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 34:324-333 334, 2021.
[32] Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-deependenee for zero- order nonsmooth nonconvex stochastic optimization. arXiv preprint arXiv:2307.04504 2023.
[33] Tongyang Li and Ruizhe Zhang. Quantum speedups of optimizing approximately convex func- tions with applications to logarithmic regret stochastic convex bandits. Advances in Neural Information Processing Systems, 35:3152-3164 2022.
[34] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International conference on machine learning, pages 6286-6295. PMLR, 2021.
[35] Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances Neural Information Processing Systems, 2022.

---

[36] Zhenwei Lin, Jingfan Xia, Qi Deng, and Luo Luo. Decentralized gradient-frre free methods for stochastic non-smooth non-convex optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[37] Yizhou Liu, Weijie J Su, and Tongyang Li. On quantum speedups for nonconvex optimization via quantum tunneling walks. Quantum, 7:1030, 2023.
[38] Zhuanghua Liu, Cheng Chen, Luo Luo, and Bryan Kian Hsiang Low. Zeroth-order meth- ods for constrained nonconvex nonsmooth stochastic optimization. In Forty-first International Conference on Machine Learning, 2024.
[39] Rahul Mazumder, Jerome Friedman, and Trevor Hastie. Sparsenet: Coordinate descent with nonconvex penalties. Journal of the American Statistical Association, (66(495):112511133
2011.
[40] Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann ma- chines. In Proceedings of the 27th international conference machine learning (ICMI-10), pages 807-814, 2010.
[41] Yurii Nesterov and Vladimir Spokoiny. Random gradient- minimization of convex func- tions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
[42] Michael A Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010.
[43] Damien Power. Supply chain management integration and implementation: literature review. Supply chain management: an International journal, 10(4):252-263, 2005.
[44] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018.
[45] Mehdi Ramezani, Morteza Nikaeen, Farnaz. Farman, Seyed Mahmoud Ashrañ, and Alireza Bahrampour. Quantum multiplication algorithm based on the convolution theorem. Physical Review A, 108(5)0052405, 2023.
[46] Lidia Ruiz-Perez and Juan Carlos fourier transform. Quantum Information Processing, 16:1 16:1-14, 2017.
Quantum arithmetic with the quantum
[47] Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. In Forty-first In- ternational Conference on Machine Learning. 2024.
[48] Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
[49] Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake. Do differentiable simu- lators give better policy gradients? In International Conference on Machine Learning, pages PMLR, 2022.
[50] Lai Tian and Anthony Man-Cho So. On the hardness of computing near-approximate stationnay points of clarke regular nonsmooth nonconvex problems and certain de programs. In ICMI. Workshop on Beyond First-Order Methods in ML. Systems, 2021.
[51] Lai Tian and Anthony Man-Cho So. No dimension-free deterministic algorithm computes approximate stationarittis of lipschitzians. Mathematical Programming, pages 1-24, 2024.
[52] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and prac- tical computation of approximate stationarity concepts of lipschitz functions. In International Conference on Machine Learning, pages 21360-21379. PMLR, 2022.
[53] Joran Van Apeldoorn and András Gilyén. Improvements in quantum sdp-solving with appli- cations. arXiv preprint
2018.
[54] Joran Van Apeldoomn András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum sdp- solvers: Better upper and lower bounds. In 2017 IEFE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 403-414, IEEE, 2017.
10

---

[55] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimiza- tion using quantum oracles. Quantum, 4:220, 2020.
[56] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, and Xiaoming Sun. Quantum multi- armed bandits and stochastic linear bandits enjoy logarithmic regrets. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
[57] Daochen Wang. Aarthi Sundaram, Robin Kothari, Ashish Kapoor, and Martin Roetteler. Quan- tum algorithms for reinforcement learning with generative model. In International Confer- ence on Machine Learning, pages 10916-10926. PMLR, 2021.
[58] Yulian Wu, Chaowen Guan, Vaneet Aggarwal, and Di Wang. Quantum heavy-tailed bandits. arXiv preprint wrXiv:2301.0968) 2023.
[59] Farzad Yousefian, Angelia Nedić, and Uday Shanbhag. On stochastic gradient and subgra- dient methods with adaptive steplength sequences. Automatica, 48(1):56-67, 2012.
[60] Chenyi Zhang and Tongyang Li. Quantum lower bounds for finding stationary points of non- convex functions. In International Conference on Machine Learning, pages 41268 41268-41299, 41299.. PMLR, 2023.
[61] Chenyi Zhang, Jiaqi Leng, and Tongyang Li. Quantum algorithms for escaping from saddle points. Quantum, 5:529, 2021.
[62] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty, Ann. Statist., 38(1):894 942, 2010.
[63] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pages 11172-11182. PMLR, 2020.
[64] Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, and Tongyang Li. Quantum algorithms and lower bounds for finite-sum optimization. arXiv preprint arXiv:2406.0300 2024.

---

A Explicit Construction of Quantum Sampling Oracles
In this section, we propose a novel quantum process to realize quantum sampling oracle Ow.s : (0) - Ew.g / Pr[w.E]lww [T]..w)llw.. with uniform distribution, where & is uniformly distributed on {0, (O,-.,N 1 and w is sampled uniformly on a discrete unit sphere.
The uniform distribution of & in the quantum state can be constructed using Hadamard gates. The construction of a uniform distribution on discrete unit sphere is more tricky. Classically, such a distribution can be constructed by sampling each coordinate from a standard Gaussian distribution and then normalizing the vector to have unit length by dividing by its norm. However, preparing superposition state with Gaussian amplitudes is not trivial because the Gaussian distribution is defined in an infinite interval. Constructing such a state with Grover's method (24) will lead to some issues in dealing with the domain and normalization of the measurement probability. Instead, here, starting with the simple uniform superposition state, we use a central limit theorem to construct the standard Gaussian distribution.
The overall quantum algorithm proceeds as follows:
Step 1. Prepare the initial quantum state (0) @ml @ (0) (ddma) @ [0] (d)oo Set k = O. Apply Hθmı @ Hōdma that is, apply Hadamard gates to the first and second registers. Here, m1, 12 N..
Step 2. Define h: {0.1) R. h()) = 2 m2 J1 j1+j2+ 0.5) Apply I U where Un, Vinz
the unitary transform corresponding to h. maps the quantum state [i) (0) to the quantum state [j} |0 + h())) The k-th Un takes the k-th m2 qubits the second register as input, and the output is stored in the k-th log m2 qubits in the third register, for all A: E (O....,, , 1}.
Step 3. Consider the third register as a d-dimension vector w', with log m2 qubits to store each coordinate w Apply Unarm /w> [0 + ||w])), the result is stored in an additional ancillary register. Then normalize w' to have unit length by dividing by |w| in each component.
Analysis and Correctness. In Step 1, it starts with the quantum state (0) 8mm
10) ((dm2)
(0) m(dlogmz), where all the registers are initialized O. The first register is prepared create the superposition of &, and the second and third registers are prepared for creating the superposition of w. We apply Hadamard gates to the first and the second registers, to obtain uniform superposition of computation basis, which gives
2
1
Σ
Σ
(0)
(0) Jmz
②
Σ
(d-11)
((d-1) @ 10).
2mydma
(d-1)
(d-1)
J...
Let m1 [log N7. and we relabel the first register to obtain
ΣKS R
Σ
(0)
Σ
(d-1)
Im @ 8/0).
((d-1)
/2mid
(0)
(0)
=0
(d-))
bu (d-1)
=0
After Step 2, as each Un operates in the same manner, we take one as an example,
/2 ji + j2 + ... + Jmz
Σle @ ... Σ
0.5
2 drzz dmz
/mz
Jm
Once measured, j1.... Im, are independent and identically distributed random variables with mean 0.5 and variance 0.25. By the central limit theorem, the average of { approximates the Gaus- sian distribution when m2 is large. We obtain the standard Gaussian distribution after changing and
0.5 then the measurement g( ((6) 5(++
scaling the average of them. We denote w/. 22/m²
/mz
results of Ejs (w/) follow the distribution of (1 1).
After Step 3, the vector in the third register mapped the unit sphere and the measurement result follows the uniform distribution on a discrete unit sphere. Rearrange the order of the registers,
12

---

denote all the garbage qubits as | .), we obtain
Σ
[Pr[w.&]lww (ow.e))
W
where w'/l is uniformly distributed on discrete unit sphere and is uniformly distributed on [0, -
This realizes the discrete version of the quantum sample oracle Ow.g with uniform distribution.
Remark A.I. In the ideal scenario where do not need to limit the number of qubits, allowing mi and m2 to be sufficiently large, we can achieve swesa-1 Vu( Wdw (w) as needed in Proposi- tion 3.I Specifically, our process requires mi + m2 x d Hadamard gates, O(dm2) fundamental arithmetic operations, and calls to the norm circuit. Here, mn [log N1 and my the number of random variables that are used to approximate the Gaussian distribution. Note that many gates here can be performed in parallel, for example, all the H gates can be performed simultancously. and the sum of m2 qubits can be implemented in a circuit of O(lag (2logg) m2) depth. The total depth complexity is (log m2 (og((dlogm)) small when m2 increases. This ensures that our construction is feasible even in the context of the NISQ quantum computer [3. 44)), which only supports low-depth circuits. particular, this proce- dure does not require querying F.. thus not increasing the query complexity of Up. Nevertheless, is still important to give such an explicit and efficient construction to ensure that the quantum state preparation will not ruin the quantum advantage for the overall time complexity.
which indicates that the depth of the eircuit will remain
Remark A.2. If & sampled from distribution other than uniform distribution, there still exist quan- tum techniques which can construct such quantum sample oracle. When detailed classical sampling circuits are known, we can make it reversible by replacing gates in the classical eircuits with re- versible quantum gates such as the Toffoli gate [42], to obtain a quantum circuit [57]] When there only black box access to the classical circuit, we discuss the construction by cases. For the continuous case where the distribution is described by a probability density function, we can use the Grover's method (24]], which requires an efficient integrating circuit. For the discrete case, we can extend the Grover's method by using the QRAM data structure. The complexity of constructing QRAM data structure linearly dependent on the size of the sample space. Once it is constructed, the complexity of generating the quantum sample oracle depends only logarithmly on the size of sample space [30].
B The Proof of Lemma 3.2
Proof. First, we claim that a unitary operator Ug.5 for computing the stochastic gradient estimator ()) can be efficiently constructed. More precisely, we can construct
U R [x) 2 (E) @ (w) (b) lx) @ [gs w)) @ ((w.e)
(5)
with 2 queries to Up. Now we assume the access to Ug.5 and the description of its construction will be deferred to the end of this proof. Next we show how this can lead to a quantum 8-estimated stochastic gradient oracle O Og.5 as defined in Definition B.3 Given initial state (x) @ (0) @ (0), we
can prepare the desired quantum state by first applying the quantum sampling oracle Ow.g and then U 6 as follows:
U g,6 (I gg w I) @ 10) @ 10) U ((x)
Σ Vp(5. w)lg. w) @ @0))
S.w
Σ
xx) Σ VplE, ()Ba @ (w.s).
S.w
Next we finish the proof by presenting how to implement Ug with two queries to Up. Since 8 and d are fixed and known beforehand, we can easily construct the following three operators via the quantum unitary implementations of the corresponding classical arithmetic operations:
A. xx) @ (w) (0)
(x) @ w/ x &w), A_ (x) @ w) @ (0)
|x) w) @ Ix 6w).
13

---

8
sub (a) 0 (6)
(a) @ b),
and
Fmul :c))
2d
Let (x;
(F(x + (w: F(x dw: Then we construct unitary D as follows:
2d
D
x
@ ( w 8
0) (0) @ (0)
(a) xx
- (0)
(6) x) ()
[() x ow) @ @0
(6)
(e) (x) (
PPxxxx:; F(x @ ów) @ +ww
(4) xx)
F' (x; |F {)
x -w) x 5w)
[x) @ 89 W
x: w {)) @ (w.s).
where (a) follows by applying A_ the first, third and sixth registers; (6) uses the quantum
stochastic function value oracle Ur on the second, fourth and sixth registers; (c) uses A, and Ur in way similar steps (a) and (b); (d) applies sub the fourth and fifth registers, and then
applies Fmul on the fourth register. is easy to see that this unitary uses only queries to Up.
For any input state x)
@
W.
@
@ 10) ed apply D to obtain
xx)
(E) @ (w) (x; w. {)) @ Iw @ 10)ed
x) (<) |wi..., wa) @ (x: w. {)) (ww.s) @0)0d
Next we will utilize quantum multiplication operator U mul (a) 8 (b) @ (c) - la) @ (b) e ab). This can be implemented by the quantization of classical multiplication algorithms, whose details can be found in 20 45 46].
Applying U mul to each wwy, F") @ (0) for all i [d] yields
xx) @ ( [wi""", wa) F (x Sw; {)) (owee F ( F'(x ow:
xx) (<) [u,,..,, wa) @ Fx {)) @ (Wwee) Fx
= (x) @ [ [w,"" wa) @ F ow; { (ww.e) (x: w,)
= (x) @ [1/w.s) @ (x; E))-
(8)
By swapping the last two quantum registers, we obtain (x) @ (x( @ (/w.e)) Hence, Ug.4 can be implemented with two queries Ur.
C The Proof of Corollary 3.4
Proof. Analogous to eq. queries to Up:
5 we claim that the following unitary V R.. can be implemented with
V &g xx) ② by) ( (w) @ (6)
x) c yy) gg w. go gy: (t/w.e).
With access to V g. and O g.6, construct O Agg as
O
Vg.5 (I 1).
Next, implement Vg. with queries Ur, r, we can first follow the steps in eq. 16 eq. and eq. H to get unitary that performs the mapping below
xx
@ 0) &
@
(0) xx) @ ly) @ //w.s) (x:
@gg w)
Then applying sub and SWAP gate to the output above yields
xx) ② )y) Σ
//r[w..]lsss(:ww.s gs(y; @ /ww.e)
14

---

D The Proof of Theorem 3.5
Before we present the proof, we first introduce the results for the quantum mean estimation by Sid- ford and Zhang 48).
Theorem D.1 (148, Theorem 4)), For a random variable X with bounded variance such that
Var [X] s L.2 there exists an algorithm that can oulput an unbiased estimator it of p. E [X] satisfying E [1] uul²] 8² using an expected (LLV queries of quantum sampling oracle Ox as defined Definition] 3.2
Proof. According Proposition 3.1
the quantum 8-estimated stochastic gradient oracle given the
input x satisfies that
E g+
Vxx(x) and [ar[gs] 1
Using Theorem D.I with f. vdl., it requires only O(dTā])) queries of O Ks to construct the quantum estimator g such that E [ [f oî. According to Lemma 3.2
construct each Ogs by ((1) -queries of Fp. Thus, it only requires O(dLā])) queries of Up F to construct the mini-batch quantum estimator g-
Similarly, since we can construct the quantum estimator Ags by ((1) quurries of Up according to Corollary 3.4 with the following properties
E [Ag.] Vx((x) Vfa(y) and Var [ar[Ags] < ||| 12. |x yyl?
then, using Theorem D. with Ż dLO-1 yy directly leads to second statement.
E
The Proof of Theorem 4.1
Proof. According to the variance level we set, g: satisfies that
22
E | - vf(()))
According to Proposition 2.1 fs(.) is nonconvex function, with ) gradient, which implics that
Vdl.011
fa(x+11) s fx(.)) (V X1+1
xx)
1x(+1-X11
-[((x))-<\V/((() VdL8-1
||xe01
1
2
Taking expectation both sides of the above inequality, have
VdL5-
f6(x s -
[1
2
s fo(x)) - (x)///(x)))))) 1 + B (x(x))
$ fo(x)) - (aa))-(nnv-i (an-VaLo 11) +1(6))))( VOLo-
We 1) 2/5r.
then it holds that
2
E
svdds- ([a(xi) (((xx))((xx..)))))
Summing up the above inequality, we have
Σl [f(()))
2vdL8 2VdL8-'(((xo)) - 11) é 2V0Lo -f
+ +8L) 2
T <
T
4
T
15

---

By setting
T 2 +2vat5
and choosing Xout randomly from "Tr11) we have
2 $ 2 sc.
E [I
)1?}
s E Σ [xx))
Using Theorem 3.5 we require
b=
to achieve the desired variance level. Thus the total quantum query of Up can be bounded by
b. - δ
8/2
LA
L
38
e
The Proof of Theorem
Proof. We denote Lg = VaL We also denote g.. as the unbiased estimator of (f(((x,)) we have constructed in line and Agæ+ the unbiased estimator of ffa(x)+)) (xx;) we have constructed in line 8, We can see that gt+1 is equivalent to
g++1 g: + Ag-1
with probability Pt
gr+1
with probability 1 - Pt
According to the variance level set in Theorem have
2 01,41 2 so E [l v.fa(x())
and
L./3d
02,041 263 X1-1
x,||
-
8²
According to Proposition
2.1 V-a(+) Lgg-iipschitz continuous, which means
fo(x(11) S f6(x)) (V. Ls X xe|2
2
Lo
fs(x)) (V.s(x..) gr, xx) (gi, X Xgr, -x,)
Xt+1
-x,
(9)
2
f6(x)) " [xx))
- vf
" " 2
L8
|x++1 -x
2n
2
On the other hand, we track the variance of g++1 by
E El E[1g+11 v.f8
p [[ V 11
+ +(1-P: |g: (6(())) (Ag.+1 (Vf6(xx-1) -x)((x)))
(10)
2/33
=p:e2 + (1 (1-pt)
lg: p))
v=
X - x
82
16

---

We have Ps and can denote 4 = fx(x))
f
g: V.f((x,) I. Combining eq. 9 and
2p
eq. 10 we have
E
1+11
E
[0(X
Bi+1
V
2p
L8
fo(x))
- V
lgg vfo(x:)]1
Xx+11 - X 1
2
-
22
2
T,A/3 2e2
+ 2p
E
pc (1-p)lge -Vf(xx) 12 +11-1)
|x xel??
82
L
1 -p)
1,4/3
2/3
Xr+1 -x--xxp xx,12 D6
$ <E[..]
fo (x²
2n 2
p
82
2
(11)
We have chosen
1
2/3
17
and p=
(12)
2L
2
such that
VOL
2
L
de2/
2 2
0.
26
2/aL
2/3
82
Then, eq.
11 implies
2
E [[|V/[(x)|[]]
E
T.. ++++++
(13)
"
Since holds that
E
LT]
E
fo(x0) - fā
[00 V {xx))
7
2p
< 10
2
f(x)) -r* 28L
1
300 vf(xx)]1
1
2p
1 _2
$
(A + 25L.)
+ p
summing up eq.
13
from / = ", T - 1, we have
2
2 2
E [( [[
20
T
1/T
By choosing
= 8L5E -2 (A (A +8L) 4
(14)
p
we have
1 (x T
2 S
2
2
Σ
B [ (x;)
12] =
E [
Tr
+
2
1/7
4
4
2
Using Theorem 3.5 the expectation queries of UF to construct ği bo Ô (dLoj,)) - (dLe
and the expectation queries of UF to construct Age is b1 Ō L L||x xz _2 Ô (dL 1/3333
Thus, the total quantum queries of UF for finding the (6, c) stationary point of f() can be bounded by
O(T(bop + (1 (1-))) Ō Vdl.o 28T.
( 2/3 2/3 dI. /3 -113)
T d3/2 I 11
7
c7/88
_//3
which finishes the proof.
17

---

Algorithm Fast Quantum Gradient Method (QGM+)
1: Construct go as an unbiased estimator of Vx((x) with variance at most o7.0-
2: for t= I
3: Xt+1 X, 7/t
4: Flip a coin 0, {0,1) where P(0: 1) Pt
5: If 0, then
6: Construct g++1 an unbiased quantum estimator of vf((x+1)) with variance most
i.
7: else
8: Construct Ag++ as an unbiased quantum estimator of fx(+++1)) fx(x)) with variance
at most 02
9:
g++1= + Agæ11
10: end for
G Improved Results for Quantum Stochastic Smooth Non-convex Optimization
Sidford and Zhang (48) introduced Q-SPIDER for smooth non-convex optimization, with the query complexity of (5/22-5/)) in the quantum stochastic gradient oracle. Using the same framework QGEM+, propose the fast quantum gradient method (QGM+), which further improves the query complexity of Q-SPIDER.
We present QGM+ in Algorithm 3 The main difference between QGFM+ and QGM+ is that QGM constructs estimators for vx(x) and (x(x) - vy( instead their smoothed surrogates line 6 and line 8 by using the quantum stochastic gradient oracle directly (48, Definition 4]. We present the setting for Q- SPIDER as follows as being self-contained.
Assumption 2 48, Setting of Theorem 7D. We assuane that are able access the quantum stochastic oracle that outputs ())::)) which is stochastic gradient of f() that satisfies
BglvF(x: = vf(x). =
and
( 1 y/1
We also present the definition of the e-stationary point of a smooth function. Definition G.1. We say is c-stationary point of a smooth function f()). if satisfies |Vf(x))
We present the query complexity of QGM+ the following theorem.
Theorem G.1. Under the same setting of [48, Theorem 7] for Q-SPIDER, QGM+ (Algorithm 3 finds the e-stationary point of f(.) using expected de queries of quantum stochastic gradient oracle by setting
1
12213
Xt X
Pr 2/3
2/3
2
and
221
21'
2
2/3
Proof. According to the variance level we set in Theorem G. We have
2
E [l - -Vxx))))
2
and
12/2/3
E [[]A (VVS(X(11)
|x y
2,1+1
o2/3
18

---

fxx+1) s f(x)) (VI((x),, Xx+1 -x.) xx)++ 1 Xx+11 xx|2
=f(x:) + +VV((x):
gr,Xt+1 -xx) (Bi, Xe+1
-xi)
[|xx==1 xxel?
(15)
s - 7|B: -f(xx)1 - --
1
|x(+1 x11
211
22/
The variance of gi+1 can be traced by
g++ vf(xx+1)
R. [|l - V /x(x++))
(1 (1-p:) p.) [1] - Vx((x;) + (Ag++ - (Vf(x(+1) -VV((x::))V/((()))) -V(())))
(16)
p1 2 (1- g. [](x))] pt) 22
G213 ||x x
We let Pt = p and denote p, = f(xx)) f 2p g: ( )1 Combining eq. 15 and eq. (6).
we have
E p++11
E
[(x)+1)
11
ge+1
vf((x+1111
2p
1
$ E
f(xx)
(xx))1
11g - [[(x))]
|x+1 x+12
2
2
2n
2
1//2/3
!
E
pe + (1 11)ppll (-)))ll--V/( vx(x))] +(1
|x+1 xx1?
(17)
2p
02/3
s E [..
7
1 71 (1-p)
2222/3
X
xel1 17E"
2
21 2
o2/3
2
B
Since we have chosen 17 21
and p = 2/3 -2/3
2/3
holds that
1
2/3
B
2
1
2 0.
2
20
Thus we have:
-
2
E
p - 11
+
1/T
2
200
" lgo vx(o))] 62
B
[(xo) -((xT)
p
where the last inequality is by setting
T S 40 2/-3333-413
In the following, we bound the total queries of quantum stochastic gradient oracles. The expectation oracles construct gr is
bo - 0
and the expectation queries construct Ag, is
b = ò (V - x x = Ô (1ido
Thus, the total stochastic quantum gradient oracles for finding the c-stationary point of f()) can be bounded by
T(bop + (1 ()-))),) o (V +oe -/3))
Remark G.2. QGM+ (Algorithm improves the quantum stochastic gradient oracle of Q-SPIDER (188, Algorithm 7J) by a factor of 116
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed our limitations in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate" "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each thcoretical result, does the paper provide the full set of asssumptions and complete (and correct) proof?
Answer: [Yes]
Guidelines:
20

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question:
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided or not)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be a way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Guidelines:
21

---

The answer NA means that paper does not include experiments requiring code.
Please
see
the NeurlPS code and data submission guidelines for more de-
tails.
While we encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g,, for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines https://nips httpss///iisscccppbl.ii.e
cnniiisyyy for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
22

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[NA] This paper focus on the theory of solving nonlinear equations.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, Iet alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
23

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Answer: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA] We open access datasets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and tenms of use in the pack- age should be provided. For popular datasets, wwwpeetss.pppassattaiiii wwpppswithcooeeeeooppp...p.p com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of a dataset.
For existing datasets that are re- papakageed both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/cooeemmodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "ZjYizIVqwL", "reviewer": "Reviewer_KzCk", "summary": "This paper introduces new quantum algorithms for non-smooth non-convex optimization problems. The authors propose a quantum gradient estimator for smoothed objectives and develop the Quantum Gradient-Free Method (QGFM) and its enhanced version, QGFM+, which achieve better query complexities than their classical counterparts. These complexities demonstrate a marked quantum speedup over classical counterparts, indicating the potential of quantum computing in optimizing complex functions more efficiently. The paper also discusses the construction of quantum oracles and the application of variance reduction techniques, paving the way for future research in quantum optimization.", "questions": "Besides the questions raised in the weakness part, I have some minor issues with the submission as follows:\n\n- In line 89, the definition of the tensor product may be a little confusing.\n- In the explicit construction of quantum sampling oracles, it seems that the time complexity of the quantum algorithm may be much larger than the query complexity, due to the sampling on the unit sphere. However, for such optimization algorithms, time complexity may be more crucial in real-world applications. Could the authors state the actual time complexity of their algorithm in terms of gate counts?", "limitations": "The quantum complexity lower bound on this problem is not proved in this paper, which is mentioned in the conclusion part.  Also, as noted in remark 3.7, implementing quantum sample oracle may require the uses of QRAM, which is currently limited by the physical realizations.\nThis is a theoretical work, so there is no potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper proposed new zeroth order quantum optimization algorithms achieving better computational complexities compared to classical methods for non-smooth and non-convex optimization.\n- Technically, they construct efficient quantum gradient estimators and quantum superpositions over required distributions as a key subroutine.\n- They also proposed a quantum algorithm for non-convex smooth problems with an adaptive variance level, accelerating prior quantum algorithms to get more speedups.", "weaknesses": "- The assumptions of having a quantum stochastic function value oracle may be strong. Could the authors explain more about why it is reasonable and important to have such a function oracle?\n- The technical core for quantum speedups seems to be the quantum mean value estimation procedure, which is already used in many other optimization problems and scenarios. Could the authors explain more about the technical novelty of their work?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n **To Weakness 1**:\nWe think the assumption of having a quantum stochastic function value oracle is reasonable and not strong due to the following reasons:\n\n1. 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].\n\n2. 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].\n\nSuch quantum stochastic function value oracle is important to further design quantum algorithms.\n\n**To Weakness 2**: \nUtilizing the existing quantum mean value estimation procedure requires having a suitable quantum sampling oracle that returns a superposition over the desired distribution. \nThe closest work to ours is [42], which utilizes quantum mean estimation in non-convex optimization. We state below the technical novelty in our paper:\n\n1.  [42] requires the assumption of direct accesses of quantum stochastic gradient oracle. \nBut this is not applicable in our setting because instead, we are given only access to quantum stochastic function value oracle ${\\bf U}_F$. \nWe overcome this by providing the efficient procedure for constructing our wanted oracle from ${\\bf U}_F$ and sampling oracle \n${\\bf O}\\_{\\xi, {\\bf w}}$, which is summarized in Lemma 3.2. \n\n2. 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. \nWe fill this gap by giving an explicit and efficient construction on ${\\bf O}\\_{\\xi,{\\bf w}}$ for desired distribution in Section 3.3.\n\nIn 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.\n\n**To Question 1**:\nWe 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}$. \n\n**To Question 2**:\nWe want to first respectfully point out that it is inappropriate to compare computational complexity and query complexity. \nComputational 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. \nIn generally, this process can cause significant costs (including a large number of basic operations) or may not be efficiently computed locally.\n\nThis 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.\n\nSpecifically, 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:\n\n1. 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.\n\n2. 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$. \n\nHence, 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)$. \n\n**To Limitation 1**:\nWe 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:\n\n1. The main purpose of this paper is to show the quantum advantage on non-convex non-smooth optimization. \nWe 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, \nwhich cannot be achieved by ANY of the classical methods due to the classical lower bound $\\delta^{-1}\\epsilon^{-3}$ established by [14, 30].\n\n2. Even for non-convex smooth function, the quantum lower bound has not been fully investigated [42, 49]. \nThere are only negative results that show no quantum speed-up for non-convex smooth optimization when the dimension $d$ is large [49]. \nOn 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].\nHence, 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.\n\n**To Limitation 2**:\nOur algorithms **don't need** QRAM. \nRemark 3.7 serves as a discussion for general scenarios on the distribution of $\\xi$.\nMore 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pLsAcppKbZ", "reviewer": "Reviewer_hDMr", "summary": "This paper studies quantum algorithm for non-smooth non-convex stochastic optimization with zeroth-order oracle. It introduces an effective quantum estimator that reduces the variance compared to classical zeroth-order estimators. Upon substituting this estimator into known zeroth-order non-smooth optimizers, namely GFM and GDM+, the resulting quantum optimizer achieves improved rate $\\tilde O(d^{3/2}\\delta^{-1}\\epsilon^{-3})$ and $\\tilde O(d^{3/2}\\delta^{-1}\\epsilon^{-7/3})$ respectively for finding a $(\\delta,\\epsilon)$-Goldstein stationary point. Notably, quantum speedup improves upon the classical lower bound $\\delta^{-1}\\epsilon^{-3}$ by a factor of $\\epsilon^{2/3}$. Moreover, a modified algorithm achieves $O(\\sqrt{d}\\epsilon^{-7/3})$ for smooth optimization, improving upon the best known rate.", "questions": "- As someone unfamiliar with quantum computation, I have a general question: Is the proposed quantum oracle practically feasible to implement, or is it purely theoretical?\n\n- line 87: does state $|i\\rangle$ denote the $i$-th orthonormal basis of $\\mathcal{H}^m$?\n\n- line 100: what does it mean by $|\\mathbf{x}\\rangle |q\\rangle$? Is it a shorthand for tensor product?\n\n- Thm 3.4 part 1: should it be $Var(\\hat g) \\le \\hat\\sigma_1^2$ instead of $\\hat \\sigma_1$? part 2: number of queries should be $\\frac{d^{3/2}L\\\\|y-x\\\\|}{\\delta \\hat\\sigma_2}$ (i.e., currently it's missing $1/\\delta$)?  Since this theorem is the main result of the quantum oracle, I encourage the authors to carefully check its correctness.\n\n  also in the proof (line 471): $\\sigma_1^2$ => $\\hat\\sigma_1^2$?\n\nMinor comments:\n\n- line 98: $C_{f(x)} = f(x)$ => $C_f(x) = f(x)$?\n- Proposition 2.1: the properties of smooth surrogate $f_\\delta$ are known in [1] and [2], and Lin et. al. and Chen et. al. are restating these results in their papers. Hence, these should be more appropriate references.\n\n[1] Yousefian, F., Nedić, A., and Shanbhag, U. V., “On Stochastic Gradient and Subgradient Methods with Adaptive Steplength Sequences”, 2011. doi:10.48550/arXiv.1105.4549.\n\n[2] Duchi, J. C., Bartlett, P. L., and Wainwright, M. J., “Randomized Smoothing for Stochastic Optimization”, 2011. doi:10.48550/arXiv.1103.4296.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a new zeroth-order quantum estimator. This leads to new quantum algorithms that solves zeroth-order non-smooth non-convex optimization problem, which is not well studied in the literature. Moreover, the proposed algorithms show quantum speedup compared to their classical (non-quantum) counterparts. Notably, it improves over the classical lower bound of $\\Omega(\\delta^{-1}\\epsilon^{-3})$ by a factor of $\\epsilon^{2/3}$. Overall, these results represent a significant contribution to the understanding of optimization with quantum oracles. Given my expertise lies primarily in optimization and not in quantum computation, I am only able to assess the optimization-related aspects of this work.", "weaknesses": "Although the dependence on $\\delta,\\epsilon$ is improved, the dimension dependence is suboptimal. In particular, since GFM and GFM+ are known to have suboptimal dimension dependence $d^{3/2}$, so do QGFM and QGFM+. On the other hand, as observed by Kornowsky and Shamir [1], optimizing the random smoothing $f_\\delta$ with a non-smooth optimizer, such as online-to-non-convex (o2nc) [2], eliminates this $\\sqrt{d}$ factor and achieves $O(d)$ in dimension. Hence, my intuition suggests that upon substituting the quantum estimator into o2nc and following a similar approach to Kornowsky and Shamir, the authors might be able to recover $O(d)$ (or even better) dimension dependence. \n\n[1] Kornowski, G. and Shamir, O., “An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization”, 2023. doi:10.48550/arXiv.2307.04504.\n\n[2] Cutkosky, A., Mehta, H., and Orabona, F., “Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion”, 2023. doi:10.48550/arXiv.2302.03775.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n**To Weakness 1**:\nWe think such sub-optimal dependency on $d$ is reasonable due to the following reasons:\n\n1. 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.\n\n2. 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. \nHence, whether using their framework can recover the $\\mathcal{O}(d)$ dependency while still improve the dependency on $\\epsilon$ is not clear. \n\n**To Question 1**:\nWe answer this question from the following two aspects:\n\n1. The quantum oracles can be viewed as instances of quantum circuits. \n    Since the current hardware implementation of quantum computers is still in a relatively early stage, \n    the practical feasibility of implementing these quantum circuits depends on factors such as the size of the circuits and the types of gates used. \n\n2. 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]. \nTherefore, 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.\n    \n[A]. Groenland, Koen, et al. \"Signal processing techniques for efficient compilation of controlled rotations in trapped ions.\" New Journal of Physics, 2020.\n\n**To Question 2 and 3**:\nYes.  Your understanding is correct and we will make them clear in the revision.\n\n**To Question 4**:\nThanks for pointing out this. \nFor 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.\nFor 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$. \n\nThey do not impact the results of Theorem 4.1 and Theorem 4.3. \nPart 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\n$$\n    \\hat{\\sigma}\\_{2,t}^2 = \\epsilon^{-2/3}\\|\\|{\\bf x}\\_{t+1}-{\\bf x}\\_t\\|\\|^2 L^{4/3}d\\delta^{-1} \n$$\naccording to line 494, then we have\n\\begin{align}\n    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)\n     = \\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)\n     = \\tilde{\\mathcal{O}}\\left(dL^{1/3}\\epsilon^{-1/3}\\right),\n\\end{align}\nwhich means $b_1$ remains the same and it is independent of $\\delta$. \n\nWe will fix them in the revision.\n\n**To Question 5 and 6**:\nThanks for pointing out these, we will modify them in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8H1f3ExorZ", "reviewer": "Reviewer_mFHz", "summary": "This paper investigates quantum algorithms for finding the $(\\delta,\\epsilon)$-Goldstein stationary point of a potentially nonconvex and nonsmooth objective function $f$. Utilizing quantum variance reduction techniques as outlined in [42], the authors have developed a zeroth-order quantum estimator for the gradient of the smoothed surrogate of $f$. The stationary point of this smoothed surrogate is also the Goldstein stationary point of $f$ when using an appropriate smoothing parameter $\\delta$. Leveraging this zeroth-order quantum estimator, the authors propose two algorithms, QGFM and QGFM+, to find the Goldstein stationary point, achieving a quantum speedup on the order of $\\epsilon^{-2/3}$. Additionally, the QGFM+ framework adjusts the variance level during each variance reduction step, providing further acceleration to the Q-SPIDER algorithm described in [42] for smooth nonconvex optimization.", "questions": "Is it possible to improve the $\\delta$ dependence using quantum algorithms?\n\nMinor issues:\n\n1. Consistency of big-O notation. For example, $O$ is used in line 139 and $\\mathcal{O}$ in line 183. Similarly, there are consistency issues with the quantum oracle notation, where $\\mathcal{O}$ is used in line 168 and $\\mathbf{O}$ in line 184.\n\n2. Typo on the RHS of the inequality in line 125.\n\n3. The use of dashes '-' is a bit odd. For example, the dashes in line 139, line 210, and line 251 can be removed.\n\n4. The name initials in the citation format are not precise. For example, in entry [1], it should be 'G. Arfken' instead of 'G Arfken'.\n\n5. Line 310: \"adjust\" -> \"adjusts\". Line 311: \"fixed\" -> \"fixes\".", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper initiates the study of quantum algorithms for finding Goldstein stationary points, a significant problem in continuous optimization. Additionally, the authors present an explicit construction of the quantum sampling oracle using the quantum zeroth-order oracle, including a detailed discussion on the number of qubits required.", "weaknesses": "Despite the detailed implementation and calculations, the overall technical approach remains relatively straightforward. The zeroth-order quantum estimator combines the classical stochastic gradient estimator for the smoothed surrogate with the quantum variance reduction algorithm in [42]. The quantum algorithms for finding the Goldstein stationary point are obtained by replacing the classical estimators with quantum estimators. Moreover, the narrative is somewhat incomplete due to the absence of lower bound results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n**To Weakness 1 (discussion on the technical novelty):**\n\nWe appreciate the feedback. We highlight our technical novelty on the construction of zeroth-order estimator and the design of quantum algorithms as follow: \n\n* 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. \nWe fixed the following gaps between this paper and the one of [42]: \n   1. [42] requires the assumption of direct accesses of quantum stochastic gradient oracle. \nBut this is not applicable in our setting because instead, we are given only access to quantum stochastic function value oracle ${\\bf U}\\_F$. \nWe 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. \n\n   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.\n\n* 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.\n\n   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.\n    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].\n\n**To Weakness 2 (Discussion on the Lower Bound)**:\n\nWe 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:\n\n1. The main purpose of this paper is to show the quantum advantage on non-convex non-smooth optimization. \nWe 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, \nwhich cannot be achieved by ANY of the classical methods due to the classical lower bound $\\delta^{-1}\\epsilon^{-3}$ established by [14, 30].\n\n2. Even for non-convex smooth function, the quantum lower bound has not been fully investigated [42, 49]. \nThere are only negative results that show no quantum speed-up for non-convex smooth optimization when the dimension $d$ is large [49]. \nOn 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].\nHence, 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.\n\n**To Question 1**:\n\nExisting 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})$. \nHowever, 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.\n\nTherefore, we think the improvement on $\\delta$ dependency cannot be achieved by existing algorithm framework and leave it as an important future work.\n\n**To Minor Issues 1-5**:\nThanks for pointing out these. We will make the consistency of the big-O notation in the revision and fix the typos.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p1CBiZGVb4", "reviewer": "Reviewer_RNco", "summary": "This paper considers using quantum methods for stochastic optimization, using zeroth order queries. It looks like the main idea is that using quantum methods, one can summarize over finite difference calculations quickly and efficiently, to arrive at approximate subgradients efficiently; this would usually be very inefficient for classical methods. Overall, they are able to show speedup, from $O(\\epsilon^{-4})$ to $O(\\epsilon^{-3})$.", "questions": "(minor) Why do you say that finding a Clarke subdifferential is harder than finding a smooth differential? Generally speaking the complexities are comparable.", "limitations": "no societal limitations", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well contained and the premise is believable. \n\nThe classical optimization bits looks reasonable, and the results make sense. \n\nI skimmed through the appendix, and the classical optimization parts are reasonable.", "weaknesses": "Section 3 is a bit hard to follow. The specific speedup offered by the quantum method is not entirely clear, though it is likely coming from Theorem B1. Perhaps a deeper discussion of this, and why this quantum speedup exists (e.g. is it a consequence of Deusch Josza? Can you provide a more complete argument for where the speedup appears? )", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and helpful comments.\n\n**To Weakness 1 (the presentation of Section 3)**:\n\nThank you for this question. Hopefully, the following explanation will give you a better picture of the structure of Section 3.\n\nThe 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.\n\nThe 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. \nInstead, 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.\n\n A diagram showing the logic flow presented above is as follows:\n\\begin{align}\n\\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}}$}}\n\\end{align}\n\n\n**To Weakness 2 (discussion on the quantum speedup)**:\n\nThe 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). \nHowever, 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. \n\nIncorporating such better estimators in our quantum algorithm allows us to achieve better query complexities over the classical ones. \nMore 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.\n\nAs 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].\n\nWe will involve more discussion on this in the revision.\n\n[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.\n\n[B]. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. “Quantum Amplitude Amplification and Estimation”. In: Contemporary Mathematics 305, 2002.\n\n**To Quetsion 1**:\nThe complexities of finding Clarke differential and smooth differential are not comparable due to the following reasons:\n\n1. 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.\n\n2. 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].\nOn 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].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studied quantum algorithms for non-smooth non-convex optimization. Classical algorithms for such optimization problems have been relatively well-studied, but it is widely open in the setting of quantum computing and the paper initiated such studies.

The novelty and technical contribution are well-received by the reviews, and during the discussion period the authors addressed concerns raised from reviewers. The scores are unianimously positive and the decision is to accept this paper at NeurIPS 2024.

PS. For the final version, the authors should carefully incorporate all the points raised during rebuttal. In particular, the authors should take a close look at Review RNco, especially the complexity of subgradients of non-smooth function. It would be helpful to clarify that the objective of your paper is to explore algorithms with good worst-case bounds, but you could make a statement clarifying that for specific real-world problems, more efficient methods may (and often do) exist.
Decision: Accept (poster)