Quantum Optimization via Gradient-Based Hamiltonian Descent
Authors: Jiaqi Leng
Bin Shi
Venue: ICML 2025 poster (2025)
Keywords: Quantum Algorithms
Non-Convex Optimization
Gradient-Based Methods
Hamiltonian Dynamics
Primary area: optimization->nonconvex

Abstract: With rapid advancements in machine learning, first-order algorithms have emerged as the backbone of modern optimization techniques, owing to their computational efficiency and low memory requirements. Recently, the connection between accelerated gradient methods and damped heavy-ball motion, particularly within the framework of Hamiltonian dynamics, has inspired the development of innovative quantum algorithms for continuous optimization. One such algorithm, Quantum Hamiltonian Descent (QHD), leverages quantum tunneling to escape saddle points and local minima, facilitating the discovery of global solutions in complex optimization landscapes. However, QHD faces several challenges, including slower convergence rates compared to classical gradient methods and limited robustness in highly non-convex problems due to the non-local nature of quantum states. Furthermore, the original QHD formulation primarily relies on function value information, which limits its effectiveness. Inspired by insights from high-resolution differential equations that have elucidated the acceleration mechanisms in classical methods, we propose an enhancement to QHD by incorporating gradient information, leading to what we call gradient-based QHD. This gradient-based QHD achieves faster convergence and significantly increases the likelihood of identifying global solutions. Numerical simulations on challenging problem instances demonstrate that this gradient-based QHD outperforms existing quantum and classical methods by at least an order of magnitude.

Quantum Optimization via Gradient-Based Hamiltonian Descent
Jiaqi Leng"
Bin Shi
Abstract
1. Introduction
With rapid advancements in machine learning. first-order algorithms have emerged as the back- bone of modern optimization techniques, owing to their computational efficiency and low memory requirements. Recently, the connection between accelerated gradient methods and damped heavy- ball motion, particularly within the framework Hamiltonian dynamics, has inspired the develop- ment of innovative quantum algorithms for contin- uous optimization. One such algorithm, Quantum Hamiltonian Descent (QHD), leverages quantum tunneling to escape saddle points and local min- ima, facilitating the discovery of global solutions in complex optimization landscapes. However, QHD faces several challenges, including slower convergence rates compared classical gradient methods and limited robustness in highly non- convex problems due to the non-local nature of quantum states. Furthermore, the original QHD formulation primarily relies on function value in- formation, which limits its effectiveness. Inspired by insights from high-resolution differential equa- tions that have elucidated the acceleration mech- anisms in classical methods, propose en- hancement to QHD by incorporating gradient in- formation, leading to what we call gradient- based QHD. Gradient-based QHD achieves faster con- vergence and significantly increases the likelihood of identifying global solutions. Numerical simu- lations on challenging problem instances demon- strate that gradient-based based QHD outperforms exist- ing quantum and classical methods by at least an order of magnitude.
In modern machine learning, a central challenge lies un- constrained optimization, particularly the task of minimiz- ing continuous objective function without any constraints. Mathematically, this problem is formulated as:
min f(x). #ER
Efficiently solving such optimization problems is funda- mental to wide range of machine learning applications. First-order optimization algorithms have emerged as the cornerstone of this endeavor due to their computational effi- ciency and low memory requirements. One of the simplest yet most widely used first-order methods the vanilla gra- dient descent, which updates iteratively according to:
Tk+1 = II. fxx);
where 0 denotes the step size. This method, though simple, serves the foundation for many modern opti- mization techniques. In the early 1980s, groundbreaking advancement was introduced by Nesterov (1983): the accel- erated gradient method, now widely known as Nesterov's 's accelerated gradient descent method (NAG). This method revolutionized first-order optimization by achieving a faster convergence rate compared vanilla gradient descent. The iterative update rules for NAG are as follows:
2y = Vk-1 - sV
yk = 3% +
(ak - Fk 1k-1),
1: k
where 8 >> 0 is the step size. The key innovation of NAG lies in the introduction of momentum, which effectively reduces oscillations in the optimization trajectory and speeds up progress towards the optimal solution.
Simons Institute for the Theory of Computing, University of California, Berkeley, USA 'Department of Mathematics, Univer- sity of California, Berkeley, USA 'Center for Mathematics and Interdisciplinary Sciences, Fudan University, Shanghai, China "Shanghai Institute for Mathematies and Interdisciplinary Sci- ences, Shanghai, China. Correspondence to: Jiaqi Leng <ji- aqil @ berkeley.edu>.
Recent advancements have shed light on the mechanisms un- derlying the acceleration of NAG, thereby effectively bridg- ing the gap between its discrete updates and the continuous dynamics of damped heavy-ball motion. One pivotal contri- bution in this area is the introduction of the low-resolution ordinary differential equation (ODE) by Su et al. (2016), which characterizes the continuous limit of NAG as:
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
X + = Vf(X) 0.

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
QHD
A- 72 0.01
100 0.05
170
k 200
0.17
0.24
Gradins: Bused QHD
À 50
8 1001
& 150 0.33
A 200 0.40
0.02
6:15
Figure 1. Numerical comparison of successful probability across iterations for both QHD and gradient- based QHD applied the Styblinski-Tann function. Ps denotes the success prohability at iteration k.
where the first derivative represents velocity in classical mechanics. By transforming this equation into its canonical form, we obtain:
Let =), [0, oo) x Rd - C denote a quantum wave function, whose squared modulus [V, 2:) represents the probability distribution of hypothetical quantum particle in R at any time O. For sufficiently large evolution time t, the probability distribution expected to concentrate near the low-energy configurations of the potential f. particularly around its global minimum. Measuring the quantum state in the computational basis at such times yields random vector (t, xt) ?, which is likely to lie close to the global minimizer of f. thereby approximately solving the associated optimization problem.
V. V - - VXX).
This canonical form establishes the foundation for varia- tional perspective on the acceleration phenomenon, which is articulated through the Bregman Lagrangian,
1 C(X, - -(x))
(1)
As quantum algorithm, QHI is implemented by simulat- ing the time-dependent Hamiltonian (4), which relies only oracle access to the function values of ʃ. Thus, QHD can be viewed as quantum zeroth-order method. A natural extension of QHD to develop its higher-order variants that leverage additional information such as the gradient of f. and analyze whether such extensions can enhance QHD's efficiency on various continuous optimization problems.
as introduced by Wibisono al. (2016). Furthermore, em- ploying the Legendre transformation, Lagrangian into its Hamiltonian form:
convert this
T(X, = 2/3 1P 1
which paves the way for extending the analysis from classi- cal dynamics to quantum dynamics.
Inspired by the high-resolution ODE framework introduced by Shi et al. (2022), where the Lyapunov function is con- ceptualized as a form of energy or Hamiltonian involving the interplay of kinetic energy and gradient, we propose a novel time-dependent Hamiltonian as
By transforming the classical momentum variable P to the quantum momentum operator -iV within the Hamilto- nian (2), Leng al. (2023a) have pioneered a groundbreak- ing algorithm, known as Quantum Hamiltonian Descent (QHD), which defines the quantum dynamics through the following Schrödinger equation as
1 (t) = (-/22 + at//2ff
8 2
|1 + (13 + +x))((a).
(5)
a, V (t, x) (t)
(3)
where the time denendennddnnt Hamiltonian is articulated as
In this paper, we mainly investigate the Schrödinger equa- tion (3) with the gradient-based Hamtiltonian (5), termed as gradient-based QHD.
A()) = --))
(4)
1.1. Warm-up: gradient-based QHD v.s. QHD
'The original formulation of QHD allows a more general Hamil- tonian: A (t) = _ (-A/)) + + f(x), where the Laplacian A = V V. as given in Eq. (A.24) of (Leng et al., specialize to the parameter choices
We provide a numerical example to illustrate the differ- ences between gradient- based QHD and standard QHD, both qualitatively and quantitatively. Figure visualizes the probability distribution across iterations for both QHD and
2023a). For simplicity, corresponding the classical NAG, namely a log(t) and 9: 7 = ==1g())t
2

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
gradient-basee QHD, applied to the non-convex Styblinski- Tang function, which features three local minima alongside global minimum.
yields solutions that an order of magnitude better than those obtained by other methods.
This work is structured as follows. First, we survey related classical and quantum optimization al- gorithms in Section 2. Next, we formulate gradient-bar bbased QHD in Section 3, with several continuous- conver- gence results established in Section 4. In the subsequent Sec- tion 5, we show that gradient-hased QHD can be efficiently implemented using quantum computer. Finally, in Sec- tion 6, we present the numerical experiments comparing gradient- -bssed QHD with several other quantum and clas- sical optimization algorithms. We conclude this paper in Section
Organization.
QID
Gealler-loael QFID
SUDM
QUID
Goalass-bead QED
Berrstone:
(a) Function value
(b) Success probability
Figure 2. Numerical performance comparison of various algo- rithms on the Styblinski-Tang function.
2. Related work
demonstrates the numerical perfor- mance involving functtinn values and success probability. While QHD does not depict an obvious advantage against stochastic gradient descent with momentum (SGDM) (Shi, 2024; Shi et al., 2023) and NAG, gradient-based QHD demonstrates a much more concentrated solution distri- bution as the iterations progress, leading to an improved global convergence. These findings motivate us to conduct a detailed investigation into gradient- based QHD and its potential in continuous optimization.
Furthermore, Figure 2
NAG-related algorithms and ODEs. There has been long history of analyzing NAG-related optimization algo- rithms (Giselsson & Boyd, 2014; O' o'donoghue & Candes, 2015). Su et al. (2016) sheds new light on the understanding and design of NAG using an ODE perspective. tancourt et al., 2018; Wibisono et al., 2016; Wilson et al., 2021), a Lagrangian (or Hamiltonian) framework is used to describe a larger class of ODEs that provides unified perspective for the acceleration phenomenon in first-order optimization. Notably, accelerated gradient descent has been investigated in non-Fuctidean settings, including mir- ror descent (Krichene et al., 2015; Lin et al., 2019) and more generally, Riemannian manifolds (Ahn Sra, 2020; Han et al., 2023; Kong & Tao, 2024; Siegel, 2019).
(Be-
1.2. Overview of contributions
Our contributions are listed as follows:
We propose gradient-based QHD for continuous opti- mization problems. With novel Lyapunov function approach involving quantum operators, we provide a convergence analysis of gradient-based QHD in contin- uous time. In particular, we establish the convergence rate of gradient-based QHD in both function values (Theorem 1) and gradient norms (Theorem 4).
Quantum algorithms for unconstrained optimization. Using quantum computers to accelerate bottleneck steps in classical optimization algorithms has shown promise in achieving quantum advantage (Kerenidis & Prakash, 2020; Liu al., 2024: Rebentrost et al., 2019). However, their practical performance requires further investigation due to the non-trivial overhead involved in extracting classical in- formation from quantum states (Yuen, 2023). Motivated by the interplay between NAG and ODEs, another line of re- search proposes leveraging quantum Hamiltonian dynamics as an algorithmic surrogate for addressing unconstrained optimization problems (Leng et al., 2023a; Liu et al., 2023; Zhang et al., 2021), with recent extensions open quantum systems (Chen et al., 2023), constrained optimization (Au- gustino et al., 2023), and discrete optimization (Cheng et al., 2024). This approach is particularly effective for highly non-convex problems (Leng et al., 2023b) and well-suited for hardware implementation (Kushnir et al., 2024; Leng et al., 2024). More discussions are available in Appendix
We develop a quantum algorithm that simulates discrete-time gradient-bart based QHD to solve optimiza- tion problems (Algorithm 1). With a gate complexity linear in problem dimension d, this quantum algorithm is readily scalable to handle large-scale problems in practice.
In addition the theoretical analysis, we conduct numerical study to evaluate the performance of gradient-based QHD in both convex and non-convex optimization. Our results show that gradient- based QHD achieves an enhanced performance compared to standard QHD and other prominent classical optimiza- tion algorithms. In some cases, gradient- based QHD
3

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
3. Gradient-based Hamiltonian dynamics
The right-hand side of (11) is asymptoti- cally vanishing as the momentum P eventually decays to 0. Therefore, we expect the Hamiltonian dynamics to exhibit long-term behavior similar to that of high-resolutin ODEs; however, we leave a detailed analysis for future research.
see Appendix A).
3.1. Classical Hamiltonian flows with gradient
Inspired by the Bregman Lagrangian (Wibisono et al., 2016) and the high-resolution ODE framework (Shi et al., 2022),
we propose to study the following Lagrangian function:
Due to its distinctive properties, the proposed Lagrangian function is of independent theoretical interest. In this work, we deliberately do not restrict the parameters a, B, and ry to the specific values associated with the high-resolution ODE case (10). This flexibility allows us to explore a broader class of dynamical systems, potentially leading to novel insights and improved algorithms for continuous optimiza- tion.
X(t, 1 xVfXX(VVXX)))
(6)
3t3
| (t + f(X)
where at 3, 7 E R are real-valued parameters that will be specified later. Compared with the standard Bregman La- grangian (1), our new Lagrangian function explicitly incor- porates the gradient f into the Lagrangian. This design is motivated by the convergence analysis in the high-resolution ODE, where the Lyapunov function can be interpreted as generalized energy functional that includes gradient infor- mation. More details are provided in Appendix A.2.
3.2. Canonical quantization
We introduce canonical quantization, a standard procedure that maps a classical Hamiltonian function to a quantum Hamiltonian operator. The Hamiltonian operator serves as an infinitesimal generator of a quantum evolution, which will be the core of our quantum optimization algorithms.
By applying the Legendre transformation, we obtain the Hamiltonian function associated with (6):
A clessical-mechanicaa system is described by a Hamil- tonian function mechanical system is governed by a quantum Hamiltonian operator A: I. + L'a (R."). The canonical quanti- zation procedure allows us to translate a known classical Hamiltonian function to a corresponding quantum Hamilto- nian by the mapping:
H(t, X, P) sup ( [(t, x, Y))
P) In contrast, a quantum-
Y
2 8/2p + // fl
3t3
+ 2
[((())| + (1. + (8)
Thus, we derive the Hamiltonian dynamics:
Ty H EJ. Pj Pイ == -i 0x,
(12)
0H
x
243 P()++V((XX(1)
(8)
OP
Here, xy and pj are the position and momentum variables describing a classical object living in a d-dimensional space Rd, respectively, with the dimension indices i E [d]. Corre- spondingly, 4ty and βy are the quantum position and momen- tum operators acting on wave functions (xxx)= E I.2(RR))
0H Ox
p
f(x(x) (aP (a² (x))
(t' (f(
(z) = 22)(2,, (f)))()) = -i -ar," ((x).
Connection with high-resolution ODEs. is worth not- ing that while our Lagrangian function shares certain simi- larities with high-resolution ODEs, they are not equivalent. By substituting (9) into (8), and choosing
da,,"
Using this dictionary, we obtain the quantum Hamiltonian operator corresponding to the Hamiltonian function (7):
3/a= = Vs, - 3a = 33/8/2,
(10)
d (l( = Σ A3 1=1
P + (t3 + + (13)
2
we can transform the Hamiltonian dynamics to a second- order ODE:
where for j = ......dd. d, the operator A, is defined by
(t) + 3 (t) VVV+
as A₁ = 1. 3/2 + at 2/2 6g = dx,"
1b.
(14)
(11)
[ (1+ 3/5 vf(x())) 2/3
V v ((((t))..
21
with 0 a multiplicative operator acting on a wave function R. Due to the non-commutativity of quantum operators, the
Formally, the left-hand side corresponds to the high- resolution ODE derived by Shi al. (2022) (for details,
Details are available Section 4.

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
square of the operator A, is expressed as
Remark 1. Ho represents the initial kinetic energy (rescaled by To Its value is independent of f and typi- cally does not depend on the dimension d, e.g., when the initial state Vo is a standard Gaussian wave. In general, Z can scale linearly in d due to the presence of |//l
A3= =t t Pj + a(p, 8,} + o3
where B) = AB + BA denotes the anti-commutator of operators.
Given a quantum Hamiltonian operator (t), the quantum evolution generated by the Hamiltonian operator is governed by the Schrödinger equation:
The convergence rate is proved by constructing a Lyapunov function (t) that is non-increasing in time. The Lyapunov function defined by
E()) =((())))))))))))>>))))) = (V()))(1))(()))
10, (t, x)- (t,,,
(15)
d Σ (t + atē; - =2²,)² + (t + wt) f.
O(t) 2 j=1
for time 0 < To S t S T, subject to an initial condi- tion (To. x) = (z) The quantum wave function (t) complex-valued, and its modulus squared (t) corre- sponds a probability density that characterizes the distri- bution of the quantum particle in the real space Rd.
Here, w = 7 - 3a 2 0 because y 2 max 0).
Lemma 2. Let B 0 and y 2 max(3a, 0). For any 0.
we have E() < O.
Connection with the original QHD. In Leng et al. (2023a), the Hamiltonian was derived from the Bregman Lagrangian via Feymann's path integral technique. Our derivation relying on canonical quantization takes a differ- ent yet complementary approach. The resulting Hamiltonian operator A (t) naturally encompasses the original QHD as a special case by choosing the parameters a = 3 = = O.
In Lemma 2, we prove that the function E(t is non- increasing in time, as a result,
(f) S E(T) < = (f) S E(TO)
Moreover, we note that
E(Tb) S (t) T
(- a +||=|/
4| (())
4. Convergence analysis
+ (T8 + (V)))))))
In this section, we focus on the convergence results of the newly derived quantum dynamics. Throughout this section, we assume fx=)) = 0 and x² = 0. This can always be achieved by considering the translated objective function f(x) < f( + x²)- - fxx")
which proves Theorem 1.
The details of Lemma 2 is presented in Appendix C.2. The technical proof heavily relies on the commutation relations between various non-commuting quantum operators that appeared in the Lyapunov function. We summarize the com- mon commutation relations used in this work in Lemma 3, which might be of independent interest in future work.
4.1. Case 1: convergence to global minimum
First, we consider a simple case where no gradient norm appears in the Hamiltonian (13), i.e. B O. In this case, we can prove that the dynamics converge to the global minimum of f.
Lemma 3 (Commutation relations). Let Aj. Pj. and az be the same as above. For any 1 < j. k I d, we have the following identities:
Theorem Let B = 0 and 2 max(3a, for any a E IR.
For any 1 1/o: 2 To > 0, we denote v1) as the solution to the PDE (15) fort t 2 To. Let X, be random variable distributed according to the probability density (t). Then, for convex and continuously differentiable f. we have
1. i[43, fl = [1 [.j} + 2007
2. ilf, [Ay. = -2t 2t- 3/2 2,
3. 1[A3, = = =100 [pp. + 4a0
(j = k)
(j x k))
Xo + 2o E[f(X)]
<
w= 3a 2 0,
12 wt
A2 (j= k) (j k)
4
4. i[A3, [A
where No = TT- ||| A) (Ta)) and
20- E [I] + 4 X 12 + (To + (T))((
5. 1/13, (Ae,
-4 4t
3/2
Un. Te,01
B
In other words,
S = ((1-2)
For the proof, please refer to Appendix C.I.
5

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
4.2. Case 2: convergence to first-order stationary point
5. Quantum algorithms and complexity analysis
We denote the function G(xx) the square of the gradient norm of f. i.e.,
In this section, we study the time discretization of gradient- based QHD, which facilitates the simulation of the quantum dynamics in a (fault-tolerant) quantum computer.
of(x)
G(z) = Vf(a) Vf(z)) Σ
dx; (16)
5.1. Time discretization of the quantum Hamiltonian dynamics
Theorem 4. Let y 2 max 0) and B > 0. For any min(1/a, v 2/3) 2 To > O. we denote x) as the solution to the PDE (15). Let X2 be a random variable distributed according to the probability density (t,,x))² Then, for a convex and continuously differentiable f such that its gradient norm satisfies the following identity:
Recall that the gradient-based QHD dynamics are governed by the differential equation (15). Let (t) be the time- evolution operator that maps an initial state (Vo) to the solution state (t)) at time t E [0, T0,T,.i. i.e.
U( = (I) 1I E [0.
((x)~VG(x) x50
(17)
Formally, the time-cvolution operator can be obtained by a sequence of infinitesimal time evolution of the quantum Hamiltonian fI):
we have
2 ( + %)
[X)V)( <
3t3
Utt) lim e --sh ...e- e (th K-+00
where Mo is the same as in Theorem and
where K is a positive integer, h = t/ and t2 = kh for S k S N. Note that the gradient-based QHD Hamiltonian can be decomposed in the form (tx) Hy.1 Hx. + H3.3. where
% = E [2 )1 + 4| + (TO + ((xo)(
where w = 30. In other words, [XIVI(())II) & Ot--
Remark 2. A sufficient condition for the identity (17) is that G(z) is convex. In this case, the global minimizer of G(x) must be x² and (17) holds. However, this does not always require the objective function f to be convex. For example, consider f(x) /r for x > 0. While f is a concave function, G(x) 2 4z
HR.1
A,
Hx = a 2 V-V,,
21
(a² + B)
H3,3
| (t +z
2
I is a convex function
Therefore, we can further decompose short-time evolution step using the product formula (i.e., operator splitting):
for x >0 O.
Similarly, the proof of Theorem 4 exploits a Lyapunov func- tion approach. We define
E -ihfillte xe e -ihHaa e M
(18)
Since all the Hamiltonians HA.1. Ha.2, and Ha,3 can be efficiently simulated using quantum computer, we obtain a quantum algorithm that implements gradient-based QHD to solve large-scale optimization problems, as summarized in Algorithm 1.
F(t) (J(t): = (V()))
1 E (1 -0, + ato + 22,)² + 2 P. + (12 + wt
(1) 2 j=1
with w 7 3a > O. Due to the positivity of (t (t-
On the choice of step size h. It shown in Childs et al. (2021) that the product formula will introduce "simulation error" such that
alvy + 2x,)) 2 and J. we have
2 BC
2
V /V <
J(DS F(O),
31
e sh sh - --- -ihili e -hiBaa2 thhHr.s
where the last step follows from Lemma 5. This proves The- orem 4.
2
Σ [[ Hkllll-
15145E3
Lemma 5. Let 7 > 0 and a 2 max(3,0). 0). (17) holds, we have F(t) < 0 for any > O.
A formal calculation shows that the commutator norm scales as O(t)), which suggests h ~ tx control the simulation error each time step. However, in
-3/2 may be needed to
The proof is left in Appendix C.3.
6

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
Algorithm 1 Gradient-based QHD with fixed step size
typically scales as O(va/e) (Gilyén et al., 2019a). In this work, we focus on the convergence properties of gradient- based QHD, leaving the incorporation of quantum gradient estimation techniques for future research.
Classical Input: Hamiltonian parameters a, 8, 7/ step size h, number of iterations K.
Quantum Input: an initial guess state (o)
Output: a classical point & E Rd.
A crucial step in Algorithm 1 is to implement the quan- tum unitary operator Us based on the operator splitting formula (18). We note that the sub-Hamiltonians Ha,1 and 3 are fast-forwardable, and the operator Hx.2 can be sim- ulated by invoking Quantum Singular Value Transformation (QSVT). Combining these technical results together, we end up with the overall complexity of the quantum algorithm, as summarized in Theorem 6.
Initialize the quantum register Vo) for k 1 to K do Determine i = kh.
Implement a quantum circuit Us as described in (18).
Compute x = Us -
end for
Measure the final quantum state (vx) with the position observable è to obtain a sample point E Rd.
Theorem 6. Let be L-Lipschitz and (o) be sufficiently smooth function, Then, we can implement Algorithm I for K iterations using O(K) queries to the quantum zeroth- order oracle Oj and Ô (odhKL) queries to the quantum first-order oracle o and its inverses."
the numerical experiments, we observe that a much larger step size & can still result in the convergence of the discrete- time gradient-base based QHD. This observation aligns with our experience with the NAG method, where convergence is achieved with a step size proportional to L, irrespective dynamics. As a result, we treat the
The details proof of Theorem 6, including the efficient sim- ulation of Ha.2 via QSVT, is presented in Appendix D.
of the continuous- step size as an independent parameter in the complexity analysis. A complete understanding of the convergence of the discrete-time algorithm, however, is left for future study.
6. Numerical experiments
In this section, we conduct extensive numerical experiments to evaluate the performance of gradient- QHD and compare it with other prominent optimization algorithms.
Remark 3. Quantum simulations of time-dependent Hamil- tonians constitute an active research area, with growing body of literature addressing this topic (e.g., (An et al., 2021; 2022; Berry et al., 2020; Childs et al., 2022; Mizuta et al., 2024)). These developments pave the way for more advanced implementations of gradient-based QHD, poten- tially offering improved asymptotic complexity. A detailed exploration of such implementations is left for future work.
6.1. Experiment setup and implementation details
Let f: Rd - R be an objective function with gradient / Given optimization algorithm initialized with random sample drawn from a fixed distribution Pa. the algorithm's output after k iterations can be represented by a random variable X₁ E Rd. We denote Bff(Xx) as the ex- pectation value of the objective function and [ ((xx)) as expected gradient norm at iteration k. To assess the algo- rithm's 's performance, we define the success probability after k iterations
5.2. Complexity analysis
Now, we analyze the computational cost of Algorithm 1. In our analysis, we assume the quantum computer has access to the function f and its gradient via the following quantum circuits:
P& = P[F(X)) f(x*) s 8).
+ (x) [f()) + +2), Owy: [z) + |z) (z))) +
Oy: [x)
where > 0 is a pre-defined error threshold. For all the subsequent experiments, we set 8 1.
The quantum circuits O, and O are often called quan- tum zeroth- and first-order oracles. They can be efficiently constructed by quantum arithmetic circuits when the expres- sions of ff and f are known.
We remark that the iteration steps in gradient- baadee QHD (as shown in Algorithm 1) are more intricate than those in clas- sical methods such as SGDM and NAG. As demonstrated in the proof of Lemma 9, the query and gate complexity per iteration of gradient- based QHD scales as Odd). In contrast, each iteration of SGDM/NAG involves only a single query to f.f, with time complexity of Od). Therefore, terms
Remark 4. The requirement for quantum first-order oracle O can potentially be eliminated by leveraging Jordan's ss algorithm (Jordan, 2005), which estimates gradients using only a zeroth-order oracle O,. However, without astrong smoothness ussumptions on the objective function f, the query complexity of obtaining an e-approximate gradient
'Here, the O notation suppresses poly-logarithmic factors in the error parameter The parameter > 0 represents the error budget the Hamiltonian simulation, as detailed I Lemma 9.
7

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
of overall runtime, gradient-based QHD remains asymptoti- cally comparable to NAG, which justifies our comparison based on the iteration count.
Gladlica QII
To evaluate the classical methods such as SGDM and NAG, we estimate the expectation values and success probabilities using a sample of 1000 independent runs, Each run begins with a uniformly random initial guess and proceeds for k iterations, For the quantum methods, since the probability density function can be explicitly derived from the quantum state vector, expectation values and success probabilities are computed via numerical integration.
Bentloss
(a) Function value
(b) Gradient norm
Figure 3. Numerical comparison of various optimization algo-
rithms on the convex objective function (19), including function values and success probability.
The numerical simulations of the quantum algorithms, in- cluding QHD and gradient-based QHD, are performed on MacBook equipped with an M4 chip. Additional de- tails on the numerical methods employed are provided Ap- pendix E.I.
6.3. Non-convex optimization
More details these test problems are available in Ap- pendix E.2.
We now turn our attention to the numerical comparison of gradient-based QHD against three baseline algorithms,, including SGDM, NAG, and QHD, in non-convex optimiza- tion settings. Non-convexity introduces significant chal- lenges for classical first-order methods, as local gradient information alone is often insufficient distinguish the global minimum from other spurious local optima.
6.2. Convex optimization
To evaluate performance, we conduct numerical com- parison of gradient-based QHD against three baseline al- gorithms, including SGDM, NAG, and QHD, for convex optimization. The test function used is
(x + y) f(
y1) y)
(19)
To illustrate these challenges, we evaluate variety of non- convex optimization problem instances characterized by diverse landscape features:
256
128
which is a convex yet non-strongly convex function, with singular Hessian at its unique minimum (0, 0). Notably, the gradient of this function does not satisfy the Lipschitz continuity condition. This flat geometry presents signifi- cant challenges for classical methods that rely heavily on curvature information. making it suitable benchmark for comparative evaluation. All methods
(i) Michalewiez function (Figure 4): This function fea- tures flat plateau and unique global minimum hid- den within sharp valley, posing difficult search problem.
executed with fixed step size h 0.2.4 For the quantum variants, the initial evolution time is set to 4 1. The parameters of gradient-based QHD are configured as a = -0.1, 3 = O, and 7 = 5.
(ii) Cube-Wave function (Figure 5): With over ten local minima (four of which are global minima) concentrated within the cube [-2, 2]2, this function exemplifies a rugged landscape.
The performance of these optimization algorithms is visu-
(iii) Rastrigin function (Figure 6): This function presents a highly oscillatory landscape with global minimum the origin, making it notoriously challenging for optimization algorithms.
alized in Figure 3, where two key metrics are employed to access convergence: the average function values [Xx)] (depicted in the left subplot) and the average gradient norm B[IV / (Xx)) (depicted in the right subplot). Both quan- tities are tracked over iterations 1 < k < 25. The results reveal distinct convergence behaviors. While the (classi- cal) QHD exhibits a slower convergence rate compared to NAG, the gradient-basee QHD stands out by achieving a remarkably faster convergence rate, outperforming all other algorithms. This superior performance highlights the ef- fectiveness of incorporating gradient-bar based techniques into QHD, particularly for challenging optimization landscapes.
Due to these intricate characteristics, all three problems are recognized as particularly difficult for classical first-order methods. Additional details about these test functions are provided in Appendix E.2.
For the two quantum algorithms. the evolution time starts from to 0. In gradient-based QHD, the parameters are set to - 0.05, B O. and 5.
Despite the diversity of non-convex test problems, gradient- based QHD consistently delivers robust and favorable per- formance. Compared to both QHD and the classical algo- rithms, it achieves a significantly faster convergence rate
"We have tested various step sizes (h. E [0.05, 0.5) for gradient-based QHD and observed similar convergence behavior. To maintain consistency, we fix = 0.2 in all comparisons.
8

---

Quantum Optimization via Gradient-Basce Hamiltonian Descent
25
14
13
88
044
00
0.5
31
3.0
0.5
10
1.5
35
0.5
[XX)) f(x")
0.1
KAO
1211
Gieiaass-ood QHD
3x 01"1
Gnudeer-loasl QHD
QRD
Grallent-lood QID
0.1
Iterations:
1000
4.00
1060
Figure 4. Numerical comparison of various optimization algo- rithms the Michalewicz function, including function values and success probability.
Iterations:
Iverations: 8
Figure 6. Numerical comparison of various optimization algo- rithms on the Rastrigin function, including function values and success probability.
13
13-
41-
framework, gradient- QHD demonstrates enhanced global convergence properties, outperforming QHD and classical optimization methods.
-15
7. Conclusion and Future Work
-23
In this paper, we propose gradient- based QHD for continu- ous optimization problems without constraints. We prove the convergence of the gradient-based QHD dynamics in both function values and gradient norms via Lyapunov function approach. We also discuss an efficient implemen- tation of discrete-time gradient- based QHD using fault- tolerant quantum computer. Our numerical results show that gradient- QHD achieves improved convergence with a higher chance of identifying the global minimum in sophisticated optimization landscape.
17
1.3
06-
NAR
Blr(Xail
QII
SCDM
QHD
02-
10
Geadina-leood Q3D
200
Iterations:
Itcrations:
1:
Figure 5. Numerical comparison of various optimization algo- rithms on the Cube-Wart Wave function, including function values and success probability.
Our theoretical analysis has primarily focused on the conver- gence of gradient-based QHD in continuous time, while the long-term behavior of the discrete-time algorithm deserves further investigation. The numerical experiments are limited to 2D problems due to the exponential growth of compu- tational overhead. Developing new numerical techniques could help evaluate the advantages quantum Hamiltonian- based algorithms for high-dimensional optimization.
and yields notably lower terminal objective function values. In the Cube- Wave function, for instance, the final objective value obtained by gradient-based QHD is nearly an order of magnitude lower than that of QHD and orders of magnitude lower than those achieved SGDM and NAG.
Further numerical analysis highlights that gradient-based based QHD attains a higher success probability across all problem instances, indicating that its final states are tightly concen- trated around the global minimizer. In summary, by leverag- ing gradient information within the quantum Hamiltonian
Software and Data
The source code of the experiments is avail- able at https:// com/ jiaqileng/ Gradient- -aseett---addHH..

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
Acknowledgements
Gilyén, A., Arunachalam, S., and Wiebe, N. Optimizing quantum optimization algorithms via faster quantum gra- dient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1425- 1444. SIAM, 2019a.
L. partially supported by the Simons Quantum Post- doctoral Fellowship and Simons Investigator Award in Mathematics through Grant No. 825053. B. S. is par- tially supported by startup fund from SIMIS and Grant No.1224 2241 105 from NSFC. Most of this work was completed at the University of California, Berkeley, during B.S.'s visit in the fall of 2024.
Gilyén, A., Su, Y., Low, G. H., and Wiebe, N. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Pro- ceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193-204, 2019b.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be
Giselsson, P. and Boyd, S. Monotonicity and restart in fast gradient methods. In 53rd IEEE Conference on Decision and Control, pp. 5058-5063. IEEE, 2014.
specifically highlighted here.
Han, A., Mishra, B., Jawanpuria, P., and Gao, J. Rieman- nian accelerated gradient methods via extrapolation. In International Conference on Artificial Intelligence and Statistics, pp. 1554-1585. PMLR, 2023.
References
Ahn, K. and Sra, S. From nesterov's estimate sequence to riemannian acceleration. In Conference on Learning Theory, pp. 84-118. PMLR, 2020.
Jordan, S. P. Fast quantum algorithm for numerical gradient estimation. Physical review letters, 95(5):05050,, 2005.
An, D., Fang, D., and Lin, L. denendenn unbounded hamiltonian simulation with vector norm scaling. Quan- fum, 5:459, 2021.
Kerenidis, and Prakash, A. Quantum gradient descent for linear systems and least squares, Physical Review A, 101 (2):022316 16, 2020.
An, D., Fang, D., and Lin, L. Time-dependent hamilto- nian simulation of highly oscillatory dynamics and super- convergence for schrödinger equation. Quantum, 6:690, 2022.
Kong, and Tao, M. Quantitative convergences of lie group momentum optimizers. arXiv preprint arXiv:2405.20390 2024.
Augustino, B., Leng, J., Nannicini, G., Terlaky, T., and Wu, X. A quantum central path algorithm linear optimization. arXiv preprint arXiv:2311.00 1.03977, 2023.
Krichene, W., Bayen, A., and Bartlett, P. Accelerated mirror descent in continuous and discrete time. Advances in neural information processing systems, 28, 2015.
Berry, D. W., Childs, A. M., Su, Y., Wang, X., and Wiebe, N. Time-dependent hamiltonian simulation with I.-mmorm scaling. Quantum, 4:254, 2020.
Kushnir, S., LLng. J., Peng, Y., Fan, L., and Wu, X. Qh- dopt: A software for nonlinear optimization with quantum hamiltonian descent. INFORMS Journal on Computing, 2024.
Betancourt, M., Jordan, M. I., and Wilson, A. C. On sym- plectic optimization. arXiv preprint arXiv.1802.03653, 2018.
Leng, J., Hickman, E., Li, J., and Wu, X. Quantum Hamilto- nian Descent. arXiv preprint arXiv:2303.0147. 2023a.
Chen, Z., Lu, Y., Wang, H., Liu, Y., and Li, T. Quan- tum langevin dynamics for optimization. arXiv preprint arXiv:2311.15587, 2023.
Leng, J., Zheng, Y., and Wu, X. A quantum-classical per- formance separation in nonconvex optimization. arXiv preprint arXiv:231 1.00811, 2023b.
Cheng, J., Zhou, R., Gan, Y., Qian, C., and Liu, J. Quantum hamiltonian descent for graph partition. arXiv preprint TmXiv:2411.14666 2024.
Leng. J., Li, J., Peng, Y., and Wu, X. Expanding hardware- efficiently manipulable hilbert space via hamiltonian em- bedding, arXiv preprint arXiv:2401.0853 2024.
Childs, A. M., Su, Y., Tran, M. C., Wiebe, N., and Zhu, S. Theory of trotter error with commutator scaling. Physical Review X, 11(1):01 1020, 2021.
Lessard, L., Recht, B., and Packard, A. Analysis and de- sign of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95 2016.
Childs, A. M., Leng, J., Li, T., Liu, J.PP. and Zhang, C. Quantum simulation of real-space dynamics. Quantum, 6:860, 2022.
10

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
Li, H., Ni, H., and Ying. L. On efficient quantum block encoding of pseudo-differential operators. Quantum, 7: 1031, 2023.
Wibisono, A., Wilson, A. C., and Jordan, M. I. A variational perspective accelerated methods in optimization. pro- ceedings of the National Academy of Sciences, 113(47);
E7351-E753 2016.
Lin, T., Ho, N., and Jordan, M. On efficient optimal trans- port: An analysis of greedy and accelerated mirror de- scent algorithms. In International Conference on Ma- chine Learning, pp. 3982-3991. PMLR, 2019.
Wilson, A. C., Recht, B., and Jordan, M. I. A Iyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(1 13):1-34, 2021.
Yuen, H. improved sample complexity lower bound for (fidelity) quantum state tomography. Quantum, 7:890, 2023.
Liu, J., Liu, M., Liu, J.-P., Ye, Z.,, Wang, Y., Alexeev, Y., Eisert, J., and Jiang. L. Towards provably efficient quan- tum algorithms for large-scale machine-learning models. Nature Communications, 15(1):434, 2024.
Zhang, C., LLng. J., and Li, T. Quantum algorithms for escaping from saddle points. Quantum, 5:529, 2021.
Liu, Y., Su, W. J., and Li, T. On quantum speedups for nonconvex optimization via quantum tunneling walks. Quantum, 7:1030, 2023.
Mizuta, K., Ikeda, N., and Fujii, K. Explicit error bounds with commutator scaling for time-dependent product and multi-product formulas. arXiv preprint arXiv:2410.142: 14243, 2024.
Nesterov, A method for solving the convex programming problem with convergence rate (1/k2). In Dokl akad nauk Sssr, volume 269, pp. 543, 1983.
O'donoghue, B. and Candes, E. Adaptive restart for accel- erated gradient schemes. Foundations of computational mathematics, 15:715-732, 2015.
Rebentrost, P. Schuld, M., Wossnig, L., Petruccione, F., and Lloyd, S. Quantum gradient descent and newton's method for constrained polynomial optimization. New Journal of Physics, 21(7):073033, 2019.
Shi, B. On the hyperparameters in stochastic gradient de- scent with momentum. Journal of Machine Leurning Research, 25(236):1 2024.
Shi, B., Du, S. S., Jordan, M. I., and Su, W. J. Understanding the acceleration phenomenon via high-resolution differ- ential equations. Mathematical Programmiing, pp. 1-70, 2022.
Shi, B., Su, W., and Jordan, M. I. On learning rates and schrödinger operators. Journal of Machine Learning Research, 24(379):1-53, 2023.
Siegel, J. W. Accelerated optimization with orthogonality constraints. arXiv preprint arXiv: 2019.
Su. W., Boyd, S., and Candes. E. J. A differential equa- tion for modeling nesterov's 's accelerated gradient method: Theory and insights. Journal of Machine Learning Re- search, 17(153):1 2016.

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
A. Review of accelerated gradient descent
A.1. Accelerated gradient descent as differential equations
Accelerated gradient descent methods are fundamental in both theory and practice. Nesterov (Nesterov, 1983) proposed the first accelerated gradient method that has the following update rules (where $ > 0 the step size):
Fk yk-1 vV (ykk))))))
(20a)
k- yk 2b k: + Ih
Ik-1); 1);
(20b)
known that Nesterov's gradient descent achieves the optimal convergence rate among gradient- based methods.
On the other hand, there has been long-lasting research attempting relate madieettbbased optimization algorithms with differential equations. A seminal work by Su et al. (Shi et al., 2022) proposed second-order differential equation to capture the acceleration phenomenon in Nesterov's algorithm. For sufficiently small step size 8, the continuous-time limit of (20) is given by the following ordinary differential equation,
X + x + Vf(X) = =0,
(21)
for f > O, with initial conditions x())= = 2o and (0) = 0. The convergence rate of the ODE is ?), which matches
that the discrete-time algorithm (20).
The ODE framework of accelerated gradient descent was later generalized via a variational formulation of the underlying dynamics. Wibisono, Wilson, and Jordan (Wibisono al., 2016) proposed consider the Bregman Lagrangian,
C(X,V,t)=a t (1) Be-av Vv a
- s(x))
(22)
where 2 is the time, X Rd is the state vector, and V Rdd is the velocity. Given the Lagrangian function C(X, V,t). can consider the following variational problem:
min ((x)) 10² C(X, Xex
(23)
where ((x)) is functional defined on smooth curves {X,: t E [0, oo)}. From the calculus of variations, a curve that minimizes the functional J(x)) necessarily satisfies the Fuler-Lagrange equation:
d ( @c dt av (X,, (x.)
OL ox (X,, X,,t).
(24)
Specifically, if we choose a log(t), , 3r 7 2log(t), the resulting Euler-Langrage equation exactly the continuous-time limit of Nesterov's accelerated gradient descent (21). It is also shown that, if ot, Br, and 7 satisfies the following ideal scaling conditions,
S =
(25)
the solutions to the Euler-Lagrange equation satisfy
f(X,) - f(x')()=)>))))))))) s O ")
(26)
which gives convergence rate of the dynamical system in continuous time.
'Here, give simplified version of the Bregman Lagrangian which the Bregman divergence is given by the standard Euclidean distance; for details, see (Wibisono et al., 2016).
12

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
A.2. Understanding acceleration via high-resolution ODEs
While the continuous-time formulations of accelerated gradient descent provide more transparent perspective on the acceleration phenomenon and allow us introduce the rich toolbox from ODE theory, they offer little understanding of different accelerated gradient descent algorithms with the same continuous-time limit. For example, Polyak's 's heavy-ball method and NAG have the same mattinuous-time limit, however, they exhibit strikingly different behaviors in practice: the heavy-ball method generally only achieves local acceleration, while NAG is an acceleration method applicable to all initial values of the iterate (Lessard et al., 2016).
The difference between the two algorithms lies in a gradient correction step that only exists in NAG. Inspired by the dimensional-analysi strategies in fluid mechanics, Shi al. (2022) developed high-resolution ODE framework reflect the gradient correction effect in different algorithms with the same low-resolution continuous-time limit. The high-resolution ODEs for NAG are follows.
3 X(t) + (XV + (1+ (x)((t)) = 0, (t) +
3
(27)
2t
for 2 3/8/2, with ((3// xo. = x -
In contrast, the high-resolution ODE for the heavy-ball method does not have the higher-order correction term V (t) which explains how the gradient correction step improves the overall convergence performance of NAG over the heavy-ball method. The high-resolution ODE framework also motivates the design of a new family of accelerated gradient descent algorithms that maintain the convergence rate of NAG.
To prove the convergence of the high-resolution ODEs, Shi et al. (2022) employs the following Lyapunov function (see Shi al. (2022, Eq. (4.36))):
E(t) = 1 V$ 2
(F(X) - f(x))) 11x -(x-=x))+++ (WVV(()())
(28)
Let (t) be the solution to (27), it is proven in Shi et al. (2022, Lemma 5) that for all t 2 3/5/2
dE(()
S -5-( /vie + (t+ ++, 2
<-[vat
$ t 2))=
v
|V 1 <..
(29)
dt
2L
As a direct consequence, for any t 2 3/5/2, we have
((X(1) f(x)) S (4 + 1+43s))11 11:00 - x1
(30)
t(2t + vs)
B. Two paradigms of quantum optimization
Based on how the solution is encoded in a quantum state, there are two major paradigms in designing quantum algorithms for continuous optimization problems. In this section, we briefly discuss the two paradigms and compare their respective pros and cons.
Solution vector quantum state. The first paradigm uses amplitude encoding, where n-dimensional vector is encoded into q-qubit state with g [logg (n)]:
(V)
1i),
where (1)))3-~ is the set of computational basis. This approach encompasses a vast majority of works in quantum optimization, including (Kerenidis & Prakash, 2020; Liu et al., 2024; Rebentrost et al., 2019). In this encoding scheme, the solution vector can be represented using (llg(nn) qubits and it allows us to exploit the rich quantum numerical linear algebra toolbox to accelerate existing classical algorithms. Nevertheless, the downside is that the recovery of the classical vector v from its amplitude-encode state [v), a task known as quantum state tomography, would inevitably incur a (nn/e) overhead due to the Heisenberg limit, where e is the readout precision (Yuen, 2023). Therefore, the quantum state tomography can nullify the potential exponential quantum speedup in the computation.
13

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
Superposition of all possible solutions. Another paradigm uses basis encoding, where n-dimensional vector corresponds unique computational basis (b.)). To see how this works, assume that each element in the real-valued vector is represented by fixed-point number 2; with bit length q. Therefore, solutions (corresponding to all possible fixed-point numbers) in the n-dimensional space using (29)" computational basis, or equivalently, nq qubits. This encoding scheme is similar to how modern computers store an array with fixed/floating-poni arrays. Nevertheless, the difference is that quantum computers can produce a superposition of basis states, i.c.,
uniquely enumerate all possible
(V) = Σ (x))x))
where p is a probability distribution over the whole space. this case, measuring the quantum state (V] is equivalent to sampling point from the distribution p. Solving an optimization problem amounts to preparing an approximation of the Dirac-delta distribution at the minimizer x², i.e., the state (x*). Compared to the first paradigm, there are two major advantages of this approach: First, there is obvious fundamental limitation extracting information from the quantum register, as we can prepare a Dirac-delta-like state for which the probability of obtaining fixed solution can be arbitrarily close to 1. Second, the superposition of solutions | is natural quantum wave function, so we can design a solution path by exploiting the toolbox of continuous-space quantum mechanics, which historically less explored the quantum computation literature. The draw back, however, is that we will not have exponentially improved space/qubit complexity to represent the solution. The first approach in principle only uses (logg(n)) qubits represent a solution vector, while representing the superposition state ()) requires (nn) qubits for an n-dimensional vector.
C. Technical details of convergence analysis
C.1. Commutation relations in gradient-based QHD
This section proves the commutation relations in Lemma 3. Lemma 7. Let g: R2d + IR be smooth function. We have
( = (,, 0zg}.
Proof. Let tp be a test function. Note that
0² (gp) (0,004 + 20,90,. + {00))) (op)) = (-oz.-0) (
02
(p)))(0) dz²
-90
Therefore,
ib03.000 -i 20,90,p).
Meanwhile, we find that
+ (-10gp) = - -000000 + 20,g0,pp),
which concludes the proof.
Lemma 8. Let g: Idd + R, h: Rd + IR be two smooth smooth,fucctonn functions. We have
il H[ 22h(0)))
Proof. Let jp be function. Direct calculation shows that
ikg h/. [[pph + hp,) (op) + hp,) pl (pg(h))) hPpg)< gp;(hup gb(p))
2ih(p,g) = 2h(0,g)4.
which implies (({p,, h] = 2h(0,g). This operator is again a multiplicative operator that commutes with both g and
h.
14

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
Now, we ready prove Lemma 3.
Proof. 1. Recall that
01 Ozj"
A, = 3/2 + att 0j =
A3 =t = + 2
Therefore,
[[ = i(1 23 + a v. = (pg. +2x07.
The last identity invokes Lemma and Lemma
2. Since the by part in A, commutates with x and f, we can drop it from the commutator:
f {AA, 2, ilf. {t 3/2 -tt (p, -t-3/22,000
where use Lemma in the last step.
3. By dropping the of part in AJ. we get
|| [4 x = " + aa,, "3 = Mb3 + allos, o.
By Lemma 7 and Lemma 8, we obtain the following:
0
(j + k:) (j = k).
x[A3.a7]
2t (p, + 4a
4. It can be readily verified that [A,. Ax] and [A,, mxl for any + k. Therefore, if j + we will have
i[A3, [A =.
When j = k, first observe that
i[Ay, my] :11-3/22 Pj, xrg 1/3//2 m. 3-2/2
due the canonical commutation relation e/p,, = 1. By leveraging the commutation relation between Aj and æy.
i|A3, xA,, = +3 - AA A3)
A, (Ajz, it 3t-2)
(1)) 2A 2/2
= 3/2
5. This commutation relation is direct consequence of Lemma 8. By dropping the ex part in As, we have
82f
E[03, (Ak, x+3Il it 1/23//((p,, xxh, 03] -4t 3/2 (x = -4t
332
3/2 -3/2
JbUy.
15

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
C.2. Proof of Lemma 2
Proof. By the definition of the Lyapunov function, have
(1) - (0,00) O()),,
(31)
dt
where [] == AB - BA denotes the commutator of operators. In the following calculation, we omit the hat over quantum
operators to simplify the notation.
First, we calculate the (,)(1) part. Direct calculations yield that
(,) = Σ
2 [3 + a2tr + 24
a 20 tps, 8,} 13 (p), + (2t + w)f
(32)
1=1
As for the commutator part, it is worth noting that
d
(
1/2 A₁ + 22,2}² + (12 + wt) f
2 1=1
(33)
1
H(t) + Σ
2x + f1/2 (15, -3aff.
1
t
5=1
Therefore, we have
{A5,
(H()), (()) =i H(t); Σ
2x +
-3ats 30tf
(34)
12
j=1
Invoking the commutation relations 1-4 in Lemma to simplify (34) and combining with (32), we obtain the following identity:
0,0 + -0++ ())))) vVf(xx) 22f(x))
(35)
Since f is convex, we have - Vv((x) s for any x Rdd Since w = - 2 0, it follows that 8,0+i(H1,0 0| < 0
and (x) 2 0 for all IRd, which implies that
J E(t) - (8,0 + (11(), O.
d
C.3. Proof of Lemma 5
Proof. Similar to the proof of Lemma 2, we have
d
F(t) =
(36)
dt
Direct calculation shows that
at)(t)+ + +()
=
(37)
where
[t) = - 2wx Vf(x) + +2(ff(x))))))) - -x) -vf(()) I 0.
(38)
I2(t) = 3t
Σ
d
+ _ 1// 5/2
3
10 (A HTH
2
1kk=
d
8
(39)
= 31
Σ
2
2
1-1
k===
= 3t (G(z) - T VG(x)) 0.
16

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
The second equation commutation relation 5 in Lemma 3, and the last inequality is deduced from the convexity of ((x)). Combining (38) and (39), we prove the lemma.
D. Technical details of complexity analysis
Lemma 9. Assume that f: Rd -> IR is a I-Liipschitz For sufficiently smooth wave function (+), we can prepare a
quantum state (V) such that
V e 21 S
using
Ô (adhL)
queries to the first-order oracle ov Here, the O-) notation suppressed poly-lgaarithiiccc terms in 1/c.
Proof. Recall that
HR. 2 1 Vf) Σ
(p,, By}.
Note that this operator is independent of time and thus of k. To simulate the Hamiltonian Hx,2, we need to perform spatial discretization for the operators Pj and vy. The standard approach is to consider d-dimensional regular mesh with N grid points on each dimension, e.g., (An et al., 2022: Childs et al., 2022). The momentum operators can be implemented by applying Quantum Fourier Transform 2 times (with overall gate complexity d poly log(N)). as discussed in (Li et al., 2023). The discretized Hamiltonian operator takes the following form:
HR. = a d 2
(40)
where ||py]| S O(N), and ||V]|| S L, with L the Lipschitz constant of f. By using ((1) queries to the first-order oracle Ov we can implement a block-encoding of the matrix Нa with normalization factor a S O(adN L), and additional O(d) ancilla qubits Gilyén et al. (2019b, Lemma 29,30). With the block-encoded operator Ha,2. we can perform optimal Hamiltonian simulation by QSVT Gilyén et al. (2019b, Corollary 32). The total number of queries to the block-encoding is
O (ah + +ah log(L/e)),
with an additional Od(ahh + log(1/c))) elementary gates. Given that the input wave function T is sufficiently smooth, the discretization number N can be chosen as N = poly (og(1/e) since the spatial discretization can be regarded as a pseudo-spectral method. It turns out that the overall query complexity of the Hamiltonian simulation reads Ô (dahL), where the (-) notation suppresses poly-logarithmic terms in 1/e.
Now, we are ready prove Theorem 6.
Proof. In Algorithm 1, each iteration requires the implementation of the quantum circuit
Up = e -ihHe, -
Note that Hy,1 = - and the Laplacian operator A can be diagonalized by Fourier transform, so we can implement ei using Oddlog (N)) elementary gates. The Hamiltonian HA.3 is a multiplicative operator with two commuting terms, i.e.
Hh =e th(aa + // /2 +
Since the functions f and [ are multiplicative operators and reduce to diagonal matrices after spatial discretization. Therefore, the Hamiltonian HA.3 is fast-forwardable and can be implemented using (11) uses of the zeroth- and first-order oracle of respectively. Finally, by Lemma 9, the Hamiltonian Fk be simulated using OoadhL)) queries to the first-order oracle O By iterating these steps for K times, we can implement the quantum algorithm using O(K) queries the zeroth-order oracle O, and O(adh (T)) queries to the first-order oracle Ovy.
17

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
E. Details of numerical experiments
E.1. Numerical implementations of optimization algorithms
In the numerical experiments, we test four optimization algorithms: Stochastic Gradient Descent with momentum (SGDM), Nesterov's accelerated gradient descent (NAG), Quantum Hamiltonian Descent (QHD), and Gradient-bass QHD. Our Python implementation of the numerical algorithms can be found in the supplementary materials.
SGDM. The iterative update rules for SGDM are as follows:
0k = 1]k Vk-1 - (1 (7).))8k. ]8k9kk
Fg 2 + Uk:
where 1 2 k S K is the iteration number, ?) is the momentum coefficient, 85. is the step size, I an unbiased gradient estimator Zg. We use
0.4k: K
80
7 = 0.5 +
Sk
with = 0.01. 0 = O, and uniformly random initial guess The gradient estimator is obtained by adding a unit Gaussian random noise to the exact gradient V f (xx).
NAG. The update rules of NAG are as follows:
vk-1 sV fikk-i) -),
Th + k
[T
Ig x2-
h: +
for 1 1 k k
K. We choose yo and uniformly random initial guess Tu- The step size is chosen 0.01.
QHD and gradient-based QHD. Both QHD and muddient-based QHD are simulated following Algorithm 1. Note that QHD is special case of gradient-based QHD with 8 y = O. The simulation is performed in a mesh grid with N = 128 grid points per dimension, with the momentum and kinetic operators implemented using FFT, discussed in Appendix D. The step size varies with the test problems: We use h = 0.01 for the Styblinski-Tang and Michalewicz function, = 0.02 for the Cube- Wave function, and 0.005 for the Rastrigin function.
E.2. Non-conved test problems
The test problems used in this paper are defined as follows:
1. Styblinski- Tang function:
f(x,8) 0.2 (x* 16x22 + 5x + -16y + 5y)
where introduce normalization factor of 0.2 for better illustration. This function has unique global minimizer at (x", v²) = (-2.9, 2.9), with the minimal function value f(x",y" ~ -31.33. The numerical algorithms are implemented over the square region (-5 < x, < 5).
2. Michalewicz function:
f(z, v) sin(2) sin (x²/r) (²)) sin(y) sin 22²2/m)²
This function has a unique global minimizer at (x* y/") (2.2, 1.57). with the minimal function value f(x", yy)
1.8.. The numerical algorithms implemented over square region {0 < 2, 2. < m).
3. Cube-Ware function:
f(x, y) = 2 + 0.25x + c + 0.25y
This function has 4 global minima, namely, (x*,y") = (=0.5, +0.5). The minimal function value is f(x*) = 0.03.
The numerical algorithms are implemented over square region {-2 < x, 2. 2).
18

---

Quantum Optimization via Gradient-Based Hamiltonian Descent
4. Rastrigin function:
[(x, v) - c00c + y² 10 cos(2 + 20.
This function has unique global minimizer at [<".v" = (0. 0), with the minimal function value f("", = 0. The numerical algorithms are implemented over square region { { S S 3}.
19


Reviews:
[{"review_id": "M6vVIdd9Iw", "reviewer": "Reviewer_Wa1N", "summary": "This paper explores quantum algorithms for solving unconstrained optimization problems. Given that Nesterov's accelerated gradient descent admits a classical Hamiltonian dynamics interpretation, it is natural to consider leveraging quantum Hamiltonian dynamics for algorithm design. In particular, Leng et al. proposed the Quantum Hamiltonian Descent (QHD) algorithm, which defines a quantum evolution via a time-dependent Schrödinger equation. In QHD, the potential term is proportional to the objective function $f$ and increases with time $t$, while the kinetic energy term decreases with $t$.\n\nBuilding on the intuition from the high-resolution ODE framework by Shi et al., this work extends QHD by incorporating a gradient term of the objective function $f$ into the potential. The resulting algorithm is called gradient-based QHD. The authors then proved a convergence guarantee of gradient-based QHD, developed a quantum algorithm that simulates discrete-time gradient-based QHD, and conducted numerical experiments testing the performance of gradient-based QHD.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n1. **Potential overhead hidden in the big-O notation**:\nAccording to our proof of Theorem 1, the detailed convergence rate is (for some $0 < T_0 \\le 1/\\alpha$):\n$$\\mathbb{E}[f(X_t)] \\le \\frac{K_0 + D_0}{t^2 + (\\gamma - 3\\alpha) t},\\quad 0 < T_0 \\le t,$$\n  - $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}$.\n  - $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$.\nTherefore, 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.\n\n2. **NP-hardness of global minimization & justification for inverse-quadratic convergence**:\n  - 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]( https://proceedings.mlr.press/v75/lee18a/lee18a.pdf). There is no ``super-polynomial overhead'' for the problem class we discussed in Theorem 1.\n  - 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](https://arxiv.org/abs/2010.01801)). Our convergence rate may be already near optimal.\n  - 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.\n\n3. **Necessity of quantum first-order oracle in Theorem 6**: \nWe 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](https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.87)). In this work, we focus on the general convergence properties and leave the integration of quantum gradient estimation for future study.\n\n4. **Numerical experiments are low-dimensional & analog implementation of QHD**:\nWe 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.\n\n5. **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.\n\n6. **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.\nAccording 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)$.\nTherefore, in terms of actual runtime, gradient-based QHD is asymptotically comparable to NAG, making our comparison based on the same iteration count fair.\n\n7. **Typo in line 096**: we have corrected the typo.\n\nWe 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.**", "claims_and_evidence": "1. Gradient-based QHD converges to a global minima of the objective function $f$ with an inverse quadratic convergence rate, and converges to a stationary point with the same convergence rate.\n2. In some cases, gradient-based QHD yields solution that are an order of magnitude better than those obtained by other methods.\n\nBoth claims appear to be correct; however, I have some concerns about their implications. Please find them below.", "methods_and_evaluation_criteria": "Please refer to the following two parts.", "theoretical_claims": "The proofs for the convergence rates appear correct to me, and the techniques are quite elegant. However, I am concerned about potential overhead hidden in the big-O notation—possibly involving factors related to the dimension of the objective function or the mass of the initial wave function in regions where the function value is small. Given that, in the worst case, finding the global optimum is NP-hard, assuming P$ \\neq$NP, such overhead could be superpolynomially large, making an inverse-quadratic convergence rate insufficient. While a similar issue exists in the convergence analysis of QHD by Leng et al., their convergence rate for convex functions is inverse-exponential, which strongly suggests that the required simulation time remains polynomially bounded in the worst case. Therefore, I believe the authors need to provide further justification for why an inverse-quadratic convergence rate is meaningful.\n\nMinor question: In Theorem 6, why is a separate quantum first-order oracle necessary, given that Jordan's gradient estimation algorithm allows us to compute the gradient using a constant number of queries to a quantum function value oracle?", "experimental_designs_or_analyses": "The experimental setups and results are generally well-presented. However, the scale of these examples, particularly the dimension of the objective function, appears relatively small compared to the instances studied in the QHD paper by Leng et al. Additionally, Leng et al. demonstrated an analog implementation of QHD on the D-Wave system, which can be more efficiently executed on near-term quantum devices than digital implementations. In contrast, this paper does not provide an analogous implementation for gradient-based QHD. \n\nMoreover, I have the following questions regarding the setups:\n1. What is the advantage of discretizing gradient-based QHD rather than approximating its continuous dynamics using Hamiltonian simulation algorithms, as done in the QHD paper?\n2. The computation in each iteration of gradient-based QHD appears significantly more complicated than in NAG, particularly due to the presence of the Laplacian operator. Is it fair to compare their performance based on the same number of iterations?", "relation_to_broader_scientific_literature": "This paper proposes a novel idea and enriches the literature on solving unbounded continuous optimization problems using quantum Hamiltonian dynamics.", "essential_references_not_discussed": "Not anything in particular I can think of", "other_strengths_and_weaknesses": "I don't have further comments", "other_comments_or_suggestions": "Typo in line 096: quantum Hamiton descent -> quantum Hamiltonian descent", "questions_for_authors": "I don't have further questions other than the existing ones above.", "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": "7Ni0W11kfc", "reviewer": "Reviewer_NP8c", "summary": "In this submission, the authors presented a variant of the prominent quantum Hamiltonian descent (QHD) algorithm by adding the help of the gradient information. More specifically, the authors proposed a new time-dependent Hamiltonian as in Eq (4) which, unlike the original QHD, contains the gradient information. The authors proved the convergence of the new method. More surprisingly, the authors presented numerical results showing the gradient-based QHD outperforms the original QHD in many different settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\"\n\nBelow, we address each of the Reviewer's questions individually.\n\n1. **Lack of the convergence rate comparison with the original QHD**: \nThe convergence rate of the original QHD is formulated in a more general form (Theorem 1 on page 21, [Leng et al., 2023](https://arxiv.org/abs/2303.01471)).\n$$\\mathbb{E}[f(X_t)] - f(x^*) \\le O(e^{-\\beta_t}),$$\nwhere 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}$. \nNote 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.\n\n2. **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.\n\n3. **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.\n\n4. **The intuition of the Lagrangain function in Eq (5)**: \nEq. (5) is our Lagrangian design that is inspired by both the Bregman Lagrangian and the high-resolution ODE. \nSpecifically, the convergence analysis of the high-resolution ODE (Shi et. al.) leverages a Lyapunov function\n$$\\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.$$\nThe Lyapunov function can be interpreted as a form of system energy that includes $\\nabla f$, which motivates our design of (5).  \n\nWe 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.**", "claims_and_evidence": "Theoretical proofs and numerical evidence are provided for the claims.", "methods_and_evaluation_criteria": "The results are backed by numerical evaluation.", "theoretical_claims": "I checked the proofs and they appear to be correct.", "experimental_designs_or_analyses": "The numerical experiments are sound and valid.", "relation_to_broader_scientific_literature": "The problems this submission studies may find applications in quantum machine learning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I think this submission has made a solid contribution to quantum machine learning and optimization. It is a nice extension of the original QHD. The only weakness I can see is the lack of the convergence rate comparison with the original QHD.", "other_comments_or_suggestions": "1. Page 4: classical QHD -> original QHD. The term \"classical QHD\" might be misleading since readers might think it is referring to a classical algorithm.\n\n2. The paper arXiv:2410.14243 might prove a better algorithm for simulating time-dependence Hamiltonians.", "questions_for_authors": "What is the intuition of the Lagrangain function in Eq (5)?", "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": "IyikGoPVwO", "reviewer": "Reviewer_F84Z", "summary": "This work proposes a gradient-based quantum hamiltonian descent (QHD), which generalizes the previously proposed based on function values. Theoretical and simulation results are also provided.\n\n## After rebuttal\n\nThe authors clarified most of my concerns during the rebuttal. Hence, I increased my score. However, I still believe the clarity of the paper should be further improved. If the paper gets accepted as a final decision, I hope the authors can incorporate many aspects of the discussion in to the final version.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer F84Z for their detailed comments and insightful suggestions.\n\nFirst, we would like to clarify the primary contribution of this submission, as it appears to have been misinterpreted by Reviewer F84Z.\n\nThe 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:\n> 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.\n\n**We now address the Reviewer's major concerns:** (minor points ignored due to page limit)\n\n> There are some claims that don’t seem to align ... are NOT chosen according to (9).\n\nThe 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.**\n\n> In Section 6.1, the success probability is defined ... I'm not sure how to interpret the plot.\n\nFigure 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.\nAdditionally, 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.\n\n> ... the gradient component of the Hamiltonian disappears ... what is the benefit of gradient-based QHD over vanilla QHD?\n\nWe 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.\n\n> ... in numerical experiments, none of the \"theoretically motivated\" choices are made, including the step size, ...\n\nAs 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.\n\n> ...proof of Theorem 6 ... asserts $H_{k,3}$ can be implemented in constant time. What is the reasoning?\n\nThe 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.\n\n> 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.\n\nIn 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.\n\n> Line 300: ... simulating $H_{k,1}$ will recover QHD? ... $H_{k,1}$ is fast forwardable. So vanilla QHD is fast forwardable?\n\nWhen setting $\\alpha=\\beta=\\gamma=0$, we have\n$$H_{k,1} = -\\Delta/(2t^3), \\quad H_{k,3} = t^3 f,$$\nand $H_{k,1}+H_{k,3}$ recovers QHD.\nClearly, $H_{k,3}$ does not vanish, and just simulating $H_{k,1}$ will not recover QHD.\nMoreover, since $H_{k,1}$ and $H_{k,3}$ can not be simultaneously diagonalized, QHD is not fast-forwardable.\n\n**We appreciate the Reviewer's time and consideration and hope this clarification helps in reassessing our submission.**", "claims_and_evidence": "There are some claims that don’t' seem to align. For instance, (10) is only obtainable by assuming (9), in which case the RHS of (10) decays to 0. The next sentence reads: \"Therefore, we expect the Hamiltonian dynamics … similar to that of high-resolution ODE.\" Then, in the next sentence, $\\alpha, \\beta, \\gamma$ are NOT chosen according to (9). Please refer to the below sections for more details.", "methods_and_evaluation_criteria": "Not necessarily. For instance, in Section 6.1, the success probability is defined and is mentioned that the suboptimality measure ($\\delta$) is set to 1. However, in Figure (3), all methods seem to start from (at k=0) initial suboptimality less than 1. I'm not sure how to interpret the plot.", "theoretical_claims": "While theoretical results are presented, they do not seem to align with the algorithm. For global convergence, for instance, $\\beta=0$ in which case the gradient component of the Hamiltonian disappears. Theoretically, what is the benefit of gradient-based QHD over vanilla QHD?", "experimental_designs_or_analyses": "This work requires simulating quantum dynamics with time dependent hamiltonian, which itself is not trivial. Moreover, in numerical experiments, none of the \"theoretically motivated\" choices are made, including the step size, the choice of $\\alpha, \\beta, \\gamma$. I do not think the experimental results support the claim sufficiently.", "relation_to_broader_scientific_literature": "Given my above points, I am not sure what is the key contribution of this paper to the broader scientific literature.", "essential_references_not_discussed": "This work is in a fairly niche area, and I do not believe there is essential references to be discussed, other than the original QHD framework that the authors extensively refer to.", "other_strengths_and_weaknesses": "- Classical optimization algorithms are quite sensitive to the step size. 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. \n- It is hard to extract the main message of the paper. Theories appeal to high-resolution ODE, but then a lot of relaxations are made such that the theory the main text appeals to simply does not hold any more (e.g., $\\beta=0$). Empirical evaluations are also not done rigorously (e.g., using the same step size of $0.2$ for all cases). I do not think, in the current form, this paper asserts something scientifically concrete to the readers.", "other_comments_or_suggestions": "Given that this is a machine learning conference, it would be nice to at least introduce some technical terms like \"fast forwardable.\"", "questions_for_authors": "- What do you mean by NAG reduces oscillations in the optimization trajectory?  NAG is known to be more sensitive to noise, and actually oscillates more than gradient descent.\n- What do you mean by \"damped heavy ball motion\"? (line 49)\n- What is \"iteration\" for QHD in Fig 2? What/ is \"success probability\" of SGDM or NAG in Fig 2? \n- Why do you start with (5)? Does (5) recover the Hamiltonian for original QHD with $\\alpha = \\beta = \\gamma =0$? Or does this claim only hold for $\\hat{H}(t)$? \n- Line 300: gradient-based QHD Hamiltonian can be decomposed to three terms, where $H_{k,2}$ and $H_{k,3}$ vanishes with $\\alpha = \\beta = \\gamma  = 0$. So just simulating $H_{k,1}$ will recover QHD? Then why simulate the other two terms? Wouldn't that necessarily incur higher qubit/gate complexity? \n- Moreover, in Sec 5.2, it's mentioned that $H_{k,1}$ is fast forwardable. So vanilla QHD is fast forwardable? \n- In Section 6.1, the success probability is defined and is mentioned that the suboptimality measure (\\delta) is set to 1. However, in Figure (3), all methods seem to start from (at k=0) initial suboptimality less than 1. What is going on?\n- Why is $\\beta=0$ in Sec 6.2? Based on (12), that removes the gradient component, which seems to directly contradict what the paper asserts.", "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": "fx7LTrVF0b", "reviewer": "Reviewer_1Ka2", "summary": "This paper proposed gradient-based Quantum Hamiltonian descent, which is motivated by insights from high-resolution differential equations and based on quantum Hamiltonian descent. They proved a faster convergence rate of gb-qhd under some reasonable assumptions and conduct numerical simulations that demonstrated the advantage of gb-qhd over original qhd.\n\n-----\nUpdate: I have read all the comments and rebuttals, and will take them into account for my evaluation of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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\". \n\nWe address each of the Reviewer's questions as follows:\n\n1. **Lack of experimental results on real devices**: \nWe 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.\n\n2. **Comparison with the original QHD paper**: \nThe convergence rate of the original QHD is formulated in a more general form (Theorem 1 on page 21, [Leng et al., 2023](https://arxiv.org/abs/2303.01471)).\n$$\\mathbb{E}[f(X_t)] - f(x^*) \\le O(e^{-\\beta_t}),$$\nwhere 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}$. \nNote 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})$. \nWe will add this discussion to the camera-ready version if this paper is accepted.\n\nWe 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.**", "claims_and_evidence": "Yes, the theoretical claims in the submission are supported by formal proofs, and performance claims are supported by numerical simulations.", "methods_and_evaluation_criteria": "Yes. For the theoretical part, the authors proved the convergence rate of their algorithms, which makes sense.\nFor the simulation part, the authors judged the performance by the function value with respect to iteration rounds, which also makes sense.", "theoretical_claims": "I do not check the proofs for the theoretical claims in detail, but I went through their proof ideas. They adopted a similar method (Lyapunov function) as the in the proof of QHD convergence. Therefore, I thought the claims are likely to be correct.", "experimental_designs_or_analyses": "Yes, I have checked the validity of the numerical simulation results. They have provided details about experiments demonstrating gd-QHD's ability, which is a standard and fair comparison.", "relation_to_broader_scientific_literature": "QHD opens a new quantum algorithm paradigm for designing quantum algorithms for optimization from a. physical viewpoint, and this work goes further on this direction. This could be beneficial for us to understand the relationship between quantum dynamics and optimization.", "essential_references_not_discussed": "There are not missing references.", "other_strengths_and_weaknesses": "Strengths:\n- Novel improvements for QHD in both theoretical and practical perspectives. They proposed a novel method called gd-QHD, and proved its convergence with better simulation results.\n- The paper is well written in general, with tables and figures clearly demonstrating their results.\n\nWeakness:\n- A potential weakness is that the paper lacks experimental results on real devices. Besides numerical simulations, QHD provides further experiments on D-Waves and compared their experiment results with more classical algorithms, in many setups. Compared with that, this submission may be a little insufficient in this aspect. But I think the numerical simulations results in this paper is already convincing.", "other_comments_or_suggestions": "No more comments. The writing is very good.", "questions_for_authors": "- It seems that the authors have used a different notation from the original QHD paper, and this makes the comparison about the convergence rate (in the theoretical part) not so direct. Could the authors explain more about the convergence rates about both methods and make a comparison?", "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 proposes a quantum algorithm for minimizing differentiable functions. The algorithm is a direct time discretization of quantum Hamiltonian dynamics associated with a novel Hamiltonian. While the convergence of the continuous-time dynamics has been established, the proposed algorithm is a relatively straightforward discretization, and its step size selection rule and corresponding convergence have not been rigorously discussed. Experimental results demonstrate the superiority of the proposed algorithm.

Although there are several obvious gaps, the ideas and some of the results in this paper, such as the proposed Lagrangian and the condition in Theorem 4, appear interesting and worthy of discussion. Moreover, the remaining concerns of Reviewer F84Z, who gave the lowest score, pertain to the presentation, which can be easily addressed. Therefore, I recommend accepting this paper.

In the revision, please discuss the advantages over quantum Hamiltonian descent and provide an interpretation of the Lagrangian. Additionally, please make it explicit that Theorem 1 assumes convexity of the objective function; the current presentation is confusing. Please also address Reviewer Wa1N’s concerns, as done in the author rebuttal, in the revised version.
Decision: Accept (poster)