Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods

Dear Reviewer 7YDD,

Thank you for your constructive comments and feedback. We appreciate your positive comments on the rigor, significance, and theoretical value of our work. In the following, we address your suggestions and questions in detail.

White-box results exhibit slightly worse dimensionality dependence compared to other algorithms. Though such phenomena are common in recent works of quantum optimization, the authors are suggested to briefly explain the source of the additional dimensionality dependence.

Thank you for the suggestion, and we will include a longer explanation in an updated manuscript. Indeed, our white-box results indicate a worse dimensionality dependence compared to other quantum algorithms, yet, the comparison requires more subtlety since these other quantum algorithms also have worse dependence on the error and other problem-dependent parameters. As a consequence our white box results present a complimentary paradigm to these other quantum algorithms which are often based on quantum matrix multiplicative weight updates. The source of our increased dimension dependence is largely due to the fact that our black-box results require highly accurate function evaluations, and so the subroutines we use to instantiate white-box versions of these black-box algorithms cannot tolerate $\text{poly} (1/\varepsilon)$ scaling (we need $\text{polylog} (1/\varepsilon)$ scaling). Though this results in a higher dimension dependence, our dependence on the scale-invariant error term $r_p r_d/ \varepsilon$ is significantly better. This is crucial, since both $r_p$ and $r_d$ can scale polynomially with $n$ and $m$, respectively. On the other hand, we also show that even for applications in which $r_p$ and $r_d$ are of size $\tilde{O} (1)$, there exist regimes in which our algorithms outperform the quantum algorithms that appear to have superior scaling with respect to $m$ and $n$.

Theorem D.3 and Corollary D.1, the authors are advised to explicitly specify the form of the error rather than solely referring to it as "additive error".

We thank the reviewer for their suggestion to improve the clarity of our results. In an updated version of the manuscript, we will replace the closing sentence of Theorem D.3, which originally read "The output is an $\varepsilon$-precise solution to the dual LP problem." with "The output is a classical description of a vector $y \in \mathbb{R}^{m}_{\geq 0}$ satisfying $A^{\top} y - c \leq 0$ and $b^{\top} y \leq \text{OPT} + \varepsilon$." We will also update the statement found in Corollary D.1 in a similar fashion.

The caption of the result table is suggested to include the meaning of symbols and explicitly highlight which factors demonstrate quantum advantage.

Thank you for the suggestion. We will change the main text accordingly to improve the clarity of our results.

The statement about dimension independence may not be entirely rigorous. Under the error function value black-box setting, the quantum gradient estimation method still exhibits a logarithmic dependence on the dimension in its query complexity. Based on my knowledge, the quantum community only proved that in the error-free black-box setting, the bounded error quantum gradient estimation can achieve a query complexity of complete dimension independence.

Thank you for the suggestion. Indeed the gradient estimates incur a logarithmic dependence, which is reflected in the theorems of the paper. We will make sure to say (near) dimension-dependence instead of dimension-dependence in updated versions of the manuscript.

• If I understand right, the "domain" in Table 1 refers to a normed space, not the feasible domain. The authors are suggested to add a brief clarification to avoid potential confusion.

In an updated version of the manuscript, we will replace "domain'' with "ambient space.''

Regarding SDP problems, the quantum algorithms in this work output a dual solution under additive error, is it possible to derive error bounds for primal solutions?

Under standard assumptions, strong duality holds, and so the output of our dual-only algorithm can be used to estimate the optimal objective value of the primal problem up to additive error $\varepsilon$. If one is interested in using this dual output to compute an approximately optimal primal solution, the dual solution can be given as input for a simplex-spectraplex saddle point problem. Note however, that this still requires solving another optimization problem.

Selecting an appropriate mirror map is one of the crucial steps in implementing quantum mirror descent. Note that the authors provided several examples (e.g., for feasible domains like the probability simplex and Schatten-1 norm). For other feasible domains, are there general methodologies for choosing the mirror map and the Bregman divergence?

The choice of mirror map is indeed crucial, as i) the query complexity of the mirror descent algorithm depends polynomially on the strong convexity parameter of the mirror map; and ii) we need to be able to efficiently compute the Bregman projection induced by the mirror map in order to update the solution in each iterate. Broadly, the mirror maps we discuss in the manuscript are the standard ones found in the literature, because i) they are all 1- or 2-strongly convex with respect to their applicable domains and ii) the Bregman projection associated to these maps admits a closed form expression. We also point out that optimization problems over more complicated problem domains can be reduced to the domains we consider. For example, one can reduce SDP problem whose feasible set is defined by the intersection of an affine space with the cone of positive semidefinite matrices, to mirror descent over the spectraplex through a well-known reformulation as a saddle point problem.

Regarding the result in Table 1, is there any classical or quantum lower bound?

Thank you for the question. Indeed, classical lower bound exists: for the first-order methods (last column of Table 1), when the objective function is $L$-smooth, one can have quadratic improvements via Nesterov's accelerated gradient methods [Nes83]. Intuitively, these "accelerated" methods use not only the gradient information in the current iterate, but also the past information. In short, the classical first-order methods constitue the update of the form $x_{t+1} \in x_0 + \text{span}\{ \nabla f(x_0), \dots, \nabla f(x_t) \}$.

However, we want to emphasize that the main message we wanted to convey in this work is that zeroth-order quantum gradient methods can match the classical first-order query complexity of gradient descent-type of algorithms. That is, nothing prevents us from analyzing zeroth-order quantum accelerated gradient methods in the similar manner that we presented our current work. As we replied to Reviewer fZUu, this constitutes a natural future direction.\ Quantumly, there exists lower bounds that illustrate there is no quantum advantage with first or higher order oracle [GKNS20, GKNS21]---this is exactly why we considered the zeroth-order setting, and showed exponential separation in terms of the dimension.

Thank you again for your time and efforts in reviewing our paper. We hope the above clarification addresses any outstanding questions or concerns. Please do not hesitate to ask follow up questions during the discussion period.

[GKNS20] A. Garg, R. Kothari, P. Netrapalli, & S. Sherif, (2021). No quantum speedup over gradient descent for non-smooth convex optimization. arXiv preprint arXiv:2010.01801.

[GKNS21] A. Garg, R. Kothari, P. Netrapalli, & S. Sherif, (2021). Near-optimal lower bounds for convex optimization for all orders of smoothness. Advances in Neural Information Processing Systems, 34, 29874-29884.}

[Nes83] Y. E. Nesterov, 1983 "A method for solving the convex programming problem with convergence rate $O(1/k^2)$"

Thank you for your constructive comments and feedback. We are glad that you find our work to exhibit key positive results in a unified and complete manner across various settings. Below, we address your concerns in detail.

Are there genuinely new technical challenges in adapting classical convergence guarantees to the quantum zeroth-order setting, beyond tracking bias and variance from oracle errors?

Thank you for the question. While the framework of our analysis appears to follow classical convergence analysis closely, there are some subtle but fundamental challenges posed by the guarantees of quantum gradient estimators. The primary difference from typical classical gradient estimators is that the quantum gradient estimators exhibit non-zero bias, resulting from the phase estimation, a subroutine used in the original quantum gradient estimation [Jor05]. Most classical convergence proofs are specific to unbiased estimators and thus extending them to handle bias is a non-trivial challenge. These extensions are more technically complicated in the case of arbitrary normed spaces. In fact, the gradient estimation algorithms of [Jor05, GAW19] would not in fact be sufficient for most of our results and we must use instead a modified version of the improved gradient estimation from [vACGN23], which utilizes suppressed-bias phase estimation, such that we can also control the variance (c.f., Corollary A.1 and Theorem A.2). As an illustration of this challenge, a recent paper [CSW25] (Theorem 47) considers the optimization of a smooth and strongly convex function with condition number $\kappa$, and achieves an oracle complexity of $(1/\varepsilon)^\kappa$, exactly due to the complication of existing bias in quantum gradient estimation.

The quantum subgradient methods pose similar challenges, with the estimate obeying the subgradient guarantee at a point that is shifted from the input point, again with a biased error term.

We note that quantum gradient estimation algorithms have been studied for nearly two decades at this point, and quantum algorithms for zeroth-order convex optimization (in the regime $d \ll 1/\epsilon$) are also nearly 5 years old. However, despite the naturalness of the question, an exponential speedup in $d$ for the regime $1/\epsilon \ll d$ has not been demonstrated. We believe this gap in the literature, which is first addressed by this work, illustrates the non-triviality of the technical challenge.

Does any part of the analysis fundamentally rely on quantum-specific insights, or could the results be derived by combining known quantum gradient estimation techniques with standard optimization proofs?

Thank you for the question. If by ``quantum-specific insights", you mean an entirely new quantum subroutine that directly uses low level tools such as phase estimation or singular value transforms, then the answer is no. We use a minor modification of suppressed bias gradient estimation from [vACGN23] and the quantum subgradient methods from [CCLW20,vAGGdW20] as our building blocks. However, as discussed in the section above, the optimization proofs are not standard since care needs to be taken to incorporate the quantum estimators into the analysis.

We note that this style of analysis, where known quantum subroutines must be carefully integrated into classical frameworks, is common in the field of quantum machine learning, including several recent papers at NeurIPS/ICML.

Finally, we note that our whitebox results present a new paradigm for quantum algorithms for SDPs/LPs whose performance dominates all known algorithms in some parameter regimes. The fundamental building block for these results are the gradient methods in normed spaces, which is constructed for the first time in this work.

We thank the reviewer for pushing us to be more precise about the technical significance of our contribution, and we hope this clarification addresses the concern raised. If so, we kindly request the reviewer to reflect it in the score. Thank you again for your time and efforts in reviewing our paper.

[Jor05] S. P. Jordan, 2005 "Fast quantum algorithm for numerical gradient estimation."

[GAW19] A. Gilyén, S. Arunachalam, N. Wiebe, 2019 "Optimizing quantum optimization algorithms via faster quantum gradient computation."

[vACGN23] J. van Apeldoorn, A. Cornelissen, A. Gilyén, G. Nannicini, 2023 "Quantum tomography using state-preparation unitaries."

[CSW25] A. B. Catli, S. Simon, N. Wiebe, 2025 "Exponentially better bounds for quantum optimization via dynamical simulation."

[CCLW20] S. Chakrabarti, A. M. Childs, T. Li, X. Wu, 2020 "Quantum algorithms and lower bounds for convex optimization."

[vAGdW20] J. van Apeldoorn, A. Gilyén, S. Gribling, R. de Wolf, 2020 "Convex optimization using quantum oracles."

Dear Reviewer fZUu,

Thank you for your constructive comments and feedback. We are glad that you find our work to be a good contribution to the field of quantum optimization. Below, we address your primary concerns and questions in detail.

What happens if the oracles are a bit noisy?

We already consider noisy oracles, as shown in Definition 1 and the noise tolerance of each algorithm is reflected in the corresponding theorem. If you mean what happens if oracles are noisier than what our theorems require, then in general the final sub-optimality guarantee will not hold.

We note that this is also the situation for classical algorithms, and each gradient method has a maximum noise tolerance (which is at most $\max\left(\frac{\epsilon^2}{d},\frac{\epsilon}{d}\right)$ for any algorithm with polynomially many queries [RL16]. We also note that the classical algorithms with the highest robustness are generally slower than gradient methods. The situation is the same for quantum algorithms, and while we provide noise thresholds for all our algorithms for reasons of concreteness, developing the most robust algorithm is a somewhat orthogonal endeavor.

Finally, we emphasize that in the classical setting, even with infinitely-accurate (i.e., noiseless) zeroth-order oracles, the query complexity remains linear in $d$ [JNR12], and therefore our methods listed in Table 1 exhibit an exponential query speedup in the whole noise regime for which the guarantees hold.

Is Nesterov-type acceleration possible?

Thank you for the thoughtful comment. Indeed, Nesterov-type acceleration should be possible. The complication, though, is the well-known error accumulation on using erroneous oracle, for the accelerated methods [DGN14]. As a result, we expect the noise tolerance $\theta$ might be more stringent than the non-accelerated results we provided in the current work. Looking into the accelerated scenario definitely is an interesting future step.

Can you relax the precision requirements?

The main message we wanted to convey in this work is that zeroth-order quantum gradient methods can match the classical first-order query complexity of gradient descent-type of algorithms. That being said, it is possible that the precision requirement can be relaxed to a certain degree, e.g., improving polynomial dependence on the $\varepsilon$ and $d$ for $\theta$ required in Theorem 2.1, for instance. This may necessitate further development in the underlying quantum gradient and subgradient computation subroutines.

Thank you again for your time and efforts in reviewing our paper. We hope the above clarification addresses any outstanding questions or concerns. Please do not hesitate to ask follow up questions during the discussion period.

[JNR12] K. G. Jamieson, R. D. Nowak, B. Recht, 2012 "Query Complexity of Derivative-Free Optimization".

[RL16] A. Risteski, Y. Li, 2016 "Algorithms and matching lower bounds for approximately-convex optimization."

[DGN14] O. Devolder, Y. Nesterov, 2014 "First-order methods of smooth convex optimization with inexact oracle."

Dear reviewer Xxvf,

Thank you for your detailed comments and feedback. We appreciate your positive comments regarding the significance of the results, and the clarity of the presentation. You raise important technical points in your review, however, we feel that there is some misunderstanding regarding the most important ones. Below, we address each of your questions and concerns in detail.

Definition 1 assumes that the quantum oracle has a zeroth order measurement error of theta which is conventionally presumed to be constant. But through a careful investigation, the achievability results presented in this work in fact requires the measurement error theta to be polynomially smaller than the targeting estimation error epsilon (e.g., see Thm 2.1). Knowing that under such vanishing error condition, the classical zeroth order oracle can in fact achieve rates that are orderwise better than the rates in e.g. Table 1 that was used in the comparison.

Thank you for this thoughtful comment. It is indeed important to compare the classical and quantum settings under similar noise assumptions. However, as we clarify below, the speedup demonstrated in our paper persists under our noise assumptions.

• Firstly, we note that the noise $\theta$ in the oracle cannot be chosen to be a constant independent of $d,\epsilon$ even in the classical case, since if the noise is asymptotically polynomially larger than $\max\left(\frac{\epsilon^2}{d},\frac{\epsilon}{d}\right)$, no classical algorithm can output an $\epsilon$-approximate minimum using $\mathrm{poly}(d,\epsilon)$ queries (see Theorem~3.1 in [RL16]). Therefore any polynomial query classical algorithms also tolerate noise that is falling polynomially with the target error and the dimension.
• Furthermore, the last column in Table 1, we state the classical first-order query complexity, not zeroth-order. If we instead choose to write classical zeroth-order, every row in the classical column is multiplied by $d$; importantly, this holds even when the function evaluation oracle has perfect precision (i.e., completely noiseless) [JNR12]. Thus the quantum algorithm exhibits an exponential speedup in terms of $d$ even if the classical oracles are completely noiseless, and the following statement is not accurate.

Knowing that under such vanishing error condition, the classical zeroth order oracle can in fact achieve rates that are orderwise better than the rates in e.g. Table 1 that was used in the comparison.

Finally, we are aware that the classical methods can be accelerated by using Nesterov's accelerated gradient methods, for instance in the smooth setting. However, this is an orthogonal discussion to our claim of exponential speedup in terms of the dimension $d$. In principle, nothing prevents us from considering accelerated zeroth-order quantum gradient methods. Indeed, as we reflected in our response to reviewer fZUu02, analyzing Nesterov's accelerated gradient method within our framework constitutes a natural future direction.

Particularly, the bound on the gradient estimation error this manuscript relies on (Lemma 2.1) is weaker than the guarantees of the classical zeroth order two point gradient estimator under the same regime of theta used in the main theorems. Therefore, if we apply the same analysis under the same error conditions, the rates achievable for classical algorithms would outperform the rates of quantum algorithms presented in this work, which is the opposite of what is claimed in the abstract.

Thank you for this thoughtful comment. By the "classical two point gradient estimator," we believe you are referring to the work by [DJW15] (otherwise, please let us know which reference you have in mind). Their lower bound result clearly exhibits dimension dependence: at least $\Omega(d/\varepsilon^2)$ observations are necessary using two function evaluations, and at least $\Omega(d^2/\varepsilon^2)$ using a single function evaluation. Note that these results are in the noiseless function evaluation setting. To sum up, we are unsure how to interpret your comment "classical algorithms would outperform the rates of quantum algorithms presented in this work." We note that classically, even for (strongly convex) quadratics, a tight bound of $\Theta (d^2/ T)$ exists [Sha13]. Based on these observations, the claim of speedup in the abstract is indeed accurate.

The abstract claims an exponential separation between quantum and classical optimization but this is not clearly elaborated in the main text.

We appreciate the opportunity to clarify this point. As we mention in the main text (e.g., line 74), we achieve exponential separations in terms of the dimension $d$ for convex optimization using zeroth-order oracle. This is evident in Table 1, where we state the classical first-order query complexity to highlight that they match our results on zeroth-order quantum gradient methods. In future versions, we will make an effort to highlight the separation even more clearly. We can change the last column of Table 1 to classical (0th order) query complexity, in which case every row is multiplied by the dimension $d$, to present the exponential separation in a more explicit way.

The quantum oracle considered in this work assumes a pure state access which is well known to be algorithmically easier than its classical counterpart. Therefore, it is not a generalization of the classical access. However, this distinction is not made clear in the abstract, which could potentially mislead the readers into thinking the proposed result is a quantum speedup.

We appreciate this comment and agree that it is very important to be careful about the nature of quantum oracle access that is assumed. However, we note that the oracle access assumed in our manuscript does not return the function value encoded in the amplitudes of a pure state (which is indeed incomparable to a standard oracle), but rather simply allows the classical oracle to be queried in superposition. Given a classical circuit implementing the classical oracle, we can construct a quantum circuit for our oracle by replacing each gate with a reversible equivalent using Toffoli gates. Using such a construction, the gate complexity of the quantum oracle is within a constant factor of that of the classical oracle. A speedup that assumes this sort of oracle access is the standard assumption for almost all quantum speedups in query complexity, including well-known algorithms such as Simon's algorithm [Sim97], and most previous works on quantum speedups for convex optimization [CCLW20, vAGdW20, GKNS21, GAW19, Jor05]. Therefore, the algorithms presented in this work do in fact constitute a quantum query speedup in the usual sense.

Section 2 mentioned that one main benefit of first-order methods vs newton's approach is the convergence of global optimum irrespective of the starting point (line 103-107 on page 3), however we would point out that this global convergence is achievable with a modified newton's method with second-order smoothness condition.

Thank you for the suggestion. We will reflect this in the text in future versions.

We thank the reviewer for very specific technical comments and giving us the opportunity to clarify some important points. Please do not hesitate to ask follow up questions during the discussion period, and if your concerns are adequately addressed, we kindly request you to reflect it in the score. Thank you again for your time and effort in reviewing our paper.

[JNR12] K. G. Jamieson, R. D. Nowak, B. Recht, 2012 "Query Complexity of Derivative-Free Optimization".

[DJW15] J. C. Duchi, M. I. Jordan, M. J. Wainwright, A. Wibisono, 2015 "Optimal rates for zero-order convex optimization: the power of two function evaluations".

[Sha13] O. Shamir, 2013 "On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization".

[RL16] A. Risteski, Y. Li, 2016 "Algorithms and matching lower bounds for approximately-convex optimization."

[CCLW20] S. Chakrabarti, A. M. Childs, T. Li, X. Wu, 2020 "Quantum algorithms and lower bounds for convex optimization."

[vAGdW20] J. van Apeldoorn, A. Gilyén, S. Gribling, R. de Wolf, 2020 "Convex optimization using quantum oracles."

[GKNS21] A. Garg, R. Kothari, P. Netrapalli, S. Sherif, 2021 "No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization."

[GAW19] A. Gilyén, S. Arunachalam, N. Wiebe, 2019 "Optimizing quantum optimization algorithms via faster quantum gradient computation."

[Jor05] S. P. Jordan, 2005 "Fast quantum algorithm for numerical gradient estimation."

[Sim97] D. R. Simon, 1997 "On the Power of Quantum Computation."