Quantum Optimization via Gradient-Based Hamiltonian Descent

We sincerely thank Reviewer 1Ka2 for their detailed comments and insightful suggestions. In particular, we appreciated the Reviewer's observation that our work could be beneficial to "understand the relationship between quantum dynamics and optimization".

We address each of the Reviewer's questions as follows:

1. Lack of experimental results on real devices: We thank the reviewer for checking the feasibility of gradient-based QHD on real quantum devices such as D-Wave. Unlike vanilla QHD, implementing gradient-based QHD using analog simulators (e.g., D-Wave’s quantum computer) requires an explicit hardware encoding of the Hamiltonian $H_{k,2}\propto$ {$\nabla$, $\nabla f$}. This can be done efficiently for quadratic functions (not necessarily convex). For more sophisticated problems, e.g., higher-order polynomials, the encoding of $H_{k,2}$ must be evaluated on a case-by-case basis but remains feasible. We will include a brief discussion on the feasibility of an analog implementation of gradient-based QHD in the camera-ready version if this paper is accepted.

2. Comparison with the original QHD paper: The convergence rate of the original QHD is formulated in a more general form (Theorem 1 on page 21, Leng et al., 2023). $\mathbb{E}[f(X_t)] - f(x^*) \le O(e^{-\beta_t}),$ where the time-dependent functions in QHD, i.e., $\alpha_t$, $\beta_t$, and $\gamma_t$, must satisfy the ideal scaling condition: $\dot{\beta}_t \le e^{\alpha_t}$, $\dot{\gamma}_t = e^{\alpha_t}$. Note that our choice of $\alpha, \beta,\gamma$ in this submission is irrelevant to the time-dependent functions in the original QHD paper. When we set $\alpha=\beta=\gamma=0$, our gradient-based QHD reduces to the vanilla QHD with $\alpha_t = -\log(t)$ and $\beta_t = \gamma_t = 2\log(t)$. In this case, they exhibit the same convergence rate $O(t^{-2})$. We will add this discussion to the camera-ready version if this paper is accepted.

We sincerely appreciate the Reviewer's thoughtful feedback and constructive suggestions. Given our clarifications and the additional insights provided, we hope the Reviewer might reconsider their evaluation and, if appropriate, adjust the score accordingly.

We sincerely thank Reviewer F84Z for their detailed comments and insightful suggestions.

First, we would like to clarify the primary contribution of this submission, as it appears to have been misinterpreted by Reviewer F84Z.

The primary objective of this work is to propose a novel quantum Hamiltonian-based algorithm (gradient-based QHD) for continuous optimization. While our Hamiltonian is inspired by the Bregman Lagrangian and the high-resolution ODE framework, it is neither equivalent to them nor a direct extension. Instead, it possesses unique structures and properties. In this work, we study the dynamical and algorithmic properties of gradient-based QHD independently using new mathematical tools. This distinction was made clear in the original submission:

In this work, we do not limit our choice of the parameters $\alpha$, $\beta$, and $\gamma$ ... explore a larger family of dynamical systems for continuous optimization problems.

We now address the Reviewer's major concerns: (minor points ignored due to page limit)

There are some claims that don’t seem to align ... are NOT chosen according to (9).

The Hamiltonian dynamics in (10) serve to formally illustrate the connection between gradient-based QHD and high-resolution ODEs. Gradient-based QHD does not reduce to high-resolution ODEs, and its convergence properties have been established independently (Theorems 1 & 4). We believe our claims are self-consistent and supported by both the theoretical and numerical evidence presented in the original submission.

In Section 6.1, the success probability is defined ... I'm not sure how to interpret the plot.

Figure 3(a) depicts the expectation value of the sub-optimality gap (caption: "function value"). It is important to note that the average sub-optimality gap is not equivalent to the success probability measure defined in Section 6.1: even if the initial average sub-optimality is below 1, this does not imply that all solutions achieve an optimality gap lower than 1. Additionally, we have identified a typo in the caption of Figure 3(b): "Success probability" should be corrected to "Gradient norm." We sincerely apologize for any confusion and will ensure that this typo is corrected in the camera-ready version if the paper is accepted.

... the gradient component of the Hamiltonian disappears ... what is the benefit of gradient-based QHD over vanilla QHD?

We thank the Reviewer for the question regarding the benefits of gradient-based QHD over vanilla QHD. By definition (Eqs. (12)–(13)), the gradient appears in both $\frac{1}{2}\sum^d_{j=1}A_j$ and $\beta t^3\|\nabla f\|^2$. Therefore, even if we set $\beta = 0$, gradient information remains present in $A_j$ as long as $\alpha \neq 0$. Theoretically, the inclusion of the gradient in the Hamiltonian results in a larger spectral gap compared to vanilla QHD. A sufficiently large spectral gap is crucial for the success of Hamiltonian-based optimization algorithms, as is well understood in the context of adiabatic algorithms and vanilla QHD.

... in numerical experiments, none of the "theoretically motivated" choices are made, including the step size, ...

As long as the parameters $\alpha, \beta, \gamma$ satisfy the conditions in Theorem 1, our result holds independent of specific step-size choices. Our choice of the parameters in the numerical experiment also aligns with the conditions discussed in Theorem 1.

...proof of Theorem 6 ... asserts $H_{k,3}$ can be implemented in constant time. What is the reasoning?

The Hamiltonian $H_{k,3}$ represents a point-wise multiplication of a function to the wave function, and its spatial discretization directly leads to a diagonal operator acting on the (discretized) wave function. Since all the diagonal elements of the discretized $H_{k,3}$ are efficiently computable via the query access to $f$ and $\nabla f$, we can simulate $e^{itH_{k,3}}$ using $O(\log(t))$ gates.

Executing all methods with the same step size of 0.2 does not tell much in terms of optimization, which is the aim of this work.

In our preliminary experiments, we implemented the test in Section 6.2 with a range of step sizes ($h \in [0.05, 0.5]$), and we always observed similar convergence behavior. Therefore, to maintain consistency, we fix $h = 0.2$ in the submission. We will add all these results in the camera-ready version if this paper is accepted.

Line 300: ... simulating $H_{k,1}$ will recover QHD? ... $H_{k,1}$ is fast forwardable. So vanilla QHD is fast forwardable?

When setting $\alpha=\beta=\gamma=0$, we have $H_{k,1} = -\Delta/(2t^3), \quad H_{k,3} = t^3 f,$ and $H_{k,1}+H_{k,3}$ recovers QHD. Clearly, $H_{k,3}$ does not vanish, and just simulating $H_{k,1}$ will not recover QHD. Moreover, since $H_{k,1}$ and $H_{k,3}$ can not be simultaneously diagonalized, QHD is not fast-forwardable.

We appreciate the Reviewer's time and consideration and hope this clarification helps in reassessing our submission.

We sincerely thank Reviewer NP8c for their detailed comments and insightful suggestions. In particular, we appreciate the Reviewer's observation that our submission "makes a solid contribution to quantum machine learning and optimization."

Below, we address each of the Reviewer's questions individually.

1. Lack of the convergence rate comparison with the original QHD: The convergence rate of the original QHD is formulated in a more general form (Theorem 1 on page 21, Leng et al., 2023). $\mathbb{E}[f(X_t)] - f(x^*) \le O(e^{-\beta_t}),$ where the time-dependent functions in QHD, i.e., $\alpha_t$, $\beta_t$, and $\gamma_t$, must satisfy the ideal scaling condition: $\dot{\beta}_t \le e^{\alpha_t}$, $\dot{\gamma}_t = e^{\alpha_t}$. Note that our choice of $\alpha, \beta,\gamma$ in this submission is irrelevant to the time-dependent functions in the original QHD paper. When we set $\alpha=\beta=\gamma=0$, our gradient-based QHD reduces to the vanilla QHD with $\alpha_t = -\log(t)$ and $\beta_t = \gamma_t = 2\log(t)$. In this case, they exhibit the same convergence rate $O(t^{-2})$. We will add this discussion to the camera-ready version if this paper is accepted.

2. classical QHD -> original QHD: We thank the Reviewer for this thoughtful suggestion and would be happy to incorporate this change in the camera-ready version if the submission is accepted.

3. Better quantum algorithms for time-dependent Hamiltonian simulation: We will include the reference arXiv:2410.14243, along with several other results on commutator scaling, in the camera-ready version.

4. The intuition of the Lagrangain function in Eq (5): Eq. (5) is our Lagrangian design that is inspired by both the Bregman Lagrangian and the high-resolution ODE. Specifically, the convergence analysis of the high-resolution ODE (Shi et. al.) leverages a Lyapunov function $\frac{d \mathcal{E}(t)}{d t} \le - \left[\sqrt{s}t^2 + \left(\frac{1}{L} + \frac{s}{2}\right)t + \frac{\sqrt{s}}{2L}\right]\|\nabla f(X)\|^2 < 0.$ The Lyapunov function can be interpreted as a form of system energy that includes $\nabla f$, which motivates our design of (5).

We sincerely appreciate the Reviewer's thoughtful feedback and constructive suggestions. Given our clarifications and the additional insights provided, we hope the Reviewer might reconsider their evaluation and, if appropriate, adjust the score accordingly.

We sincerely appreciate Reviewer Wa1N's thorough feedback and valuable insights. In particular, we thank the Reviewer for recognizing our techniques as "elegant" and acknowledging that this work "proposes a novel idea and enriches the literature on solving unbounded continuous optimization problems." We address each of the Reviewer's questions below:

1. Potential overhead hidden in the big-O notation: According to our proof of Theorem 1, the detailed convergence rate is (for some $0 < T_0 \le 1/\alpha$): $\mathbb{E}[f(X_t)] \le \frac{K_0 + D_0}{t^2 + (\gamma - 3\alpha) t},\quad 0 < T_0 \le t,$

• $K_0 = \langle \Psi(T_0)|(-\Delta)|\Psi(T_0)\rangle / T^4_0$: the initial kinetic energy. Independent of $f$ and typically scales as $O(d)$, e.g., for a standard Gaussian $\Psi_{0}$.
• $D_0 = \mathbb{E}\left[\|\nabla f(X_{T_0})\|^2+4\|X_{T_0}\|^2+(T^2_0+\omega T_0)f(X_{T_0})\right]$: generally scales as $O(d)$ due to $\|\nabla f\|^2$. Therefore, there might be an additional $O(d)$ overhead in our result. We will add this discussion to the camera-ready version if this paper is accepted.

2. NP-hardness of global minimization & justification for inverse-quadratic convergence:

• The inverse-quadratic convergence rate (Theorem 1) is established for general convex $f$. While finding the global optimum of a non-convex objective function is in general NP-hard, for the problem class of interest (i.e., general convex optimization), there exist polynomial-time classical algorithms with query complexity $O(n^2$) Lee et al., COLT '18. There is no ``super-polynomial overhead'' for the problem class we discussed in Theorem 1.
• The $O(t^{-2}$) rate is known to be optimal for classical first-order methods. Although a direct quantum counterpart has not yet been established, strong evidence suggests that there is no quantum speedup for generic convex optimization (e.g., Garg et al., 20). Our convergence rate may be already near optimal.
• Additionally, we emphasize that our numerical results demonstrate a significant advantage of gradient-based QHD for non-convex optimization. This observed performance extends beyond the scope of Theorem 1. To further clarify this distinction, we will explicitly highlight the convexity assumption in Theorems 1 & 4 in the camera-ready version.

3. Necessity of quantum first-order oracle in Theorem 6: We agree with the Reviewer that the requirement for a quantum first-order oracle $O_{\nabla f}$ can potentially be eliminated by Jordan's algorithm. However, the query complexity for obtaining an $\epsilon$-approximate gradient scales as $\mathcal{O}(\sqrt{d}/\epsilon)$ without a strong smoothness characterization of $f$ (Gilyen et al., SODA'19). In this work, we focus on the general convergence properties and leave the integration of quantum gradient estimation for future study.

4. Numerical experiments are low-dimensional & analog implementation of QHD: We thank the reviewer for highlighting the feasibility of gradient-based QHD on near-term quantum devices. Unlike vanilla QHD, implementing gradient-based QHD using analog simulators requires an explicit hardware encoding of the Hamiltonian $H_{k,2}\propto$ {$\nabla$, $\nabla f$}. This can be done efficiently for quadratic functions (not necessarily convex). For more sophisticated problems, e.g., higher-order polynomials, the encoding of $H_{k,2}$ must be evaluated on a case-by-case basis but remains feasible. We will include a brief discussion on this point in the camera-ready version if this paper is accepted.

5. Advantage of discretizing gradient-based QHD: The discretization method proposed in this submission utilizes the Trotter product formula, which can be viewed as a quantum simulation algorithm. Our approach, based on the product formula, has a simple structure and is potentially more straightforward to implement.

6. Fairness in comparing gradient-based QHD and NAG based on the same number of iterations: We agree with the Reviewer that the iteration steps in gradient-based QHD are more complicated. According to the proof of Lemma 9 and Theorem 6, the query and gate complexity of each iteration in gradient-based QHD scale as $\tilde{O}(d)$. In contrast, while each iteration of NAG requires only a single query to $\nabla f$, its time complexity remains $O(d)$. Therefore, in terms of actual runtime, gradient-based QHD is asymptotically comparable to NAG, making our comparison based on the same iteration count fair.

7. Typo in line 096: we have corrected the typo.

We sincerely appreciate the Reviewer's thoughtful feedback and constructive suggestions. Given our clarifications and the additional insights provided, we hope the Reviewer might reconsider their evaluation and, if appropriate, adjust the score accordingly.