Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent
arXiv:2604.13022v1 [quant-ph] 14 Apr 2026
Yihang Sun∗ Stanford University
Huaijin Wang∗ Stanford University
Patrick Hayden Stanford University, Google DeepMind
Jose Blanchet Stanford University
April 15, 2026
Abstract The Energy Conserving Descent (ECD) algorithm was recently proposed by [DLS22] as a global non-convex optimization method. Unlike gradient descent, appropriately configured ECD dynamics escape strict local minima and converge to a global minimum, making it appealing for machine learning optimization. We present the first analytical study of ECD, focusing on the one-dimensional setting for this first installment. We formalize a stochastic ECD dynamics (sECD) with energy-preserving noise, as well as a quantum analog of the ECD Hamiltonian (qECD), providing the foundation for a quantum algorithm through Hamiltonian simulation. For positive double-well objectives, we compute the expected hitting time from a local to the global minimum. We prove that both sECD and qECD yield exponential speedup over respective gradient descent baselines– stochastic gradient descent and its quantization. For objectives with tall barriers, qECD achieves a further speedup over sECD. Keywords. non-convex optimization; energy conserving descent; stochastic gradient descent; quantum tunneling walk; quantum Hamiltonian simulation; semiclassical analysis ∗
These authors contributed equally to this work.
1
Introduction
1.1
Background
Gradient descent methods are the dominant approach for large-scale non-convex optimization due to their scalability. The recently proposed Energy Conserving Descent (ECD) framework [DLS22, LGS23] has been reported to achieve competitive—and in some settings improved—performance relative to widely used gradient descent based optimizers such as stochastic gradient descent (SGD), Adam [KB15] and SGD with momentum (SGDM) [SMDH13]. These results are given across a range of small to medium-scale benchmarks, including ImageNet-1K finetuning and Open Graph Benchmark node-classification tasks. ECD is a physics-inspired dynamical system governed by a Hamiltonian with a purely kinetic term, where the particle’s position-dependent mass is inversely proportional to the potential function that encodes the objective. ECD preserves an energy invariant, which prevents the dynamics from converging to strict local minima in the absence of explicit stopping criteria [LGS23]. In contrast, rigorous guarantees for SGD to avoid or escape strict local minima typically require additional structural assumptions, such as smoothing or one-point convexity [KLY18]. Moreover, in small-stepsize regimes relative to the height of escape barriers, diffusion-approximation theory predicts that escape times from local minima scale exponentially in an inverse-noise or inverse-stepsize parameter [HLLL19, MZLU22]. The existence of a Hamiltonian description also motivates a natural extension of the classical optimization dynamics into a quantum problem. An analogous quantization of SGD called quantum tunneling walk (QTW) has previously been studied where a quantum advantage over SGD driven by quantum tunneling effects has been observed when the objective function has tall barriers [LSL23]. Our contribution is the first formulation and analytical study of a continuous stochastic ECD dynamics (sECD) and a quantum analog of the ECD Hamiltonian (qECD). We evaluate their theoretical performance via expected hitting times from a local minimum to the global minimum on positive double-well potentials. We show that both sECD and qECD achieve exponential improvements over respective gradient descent baselines SGD and QTW, and a further hittingtime improvement of qECD over sECD for objectives with tall barriers, mirroring the speedup of QTW over SGD.
1.2
Main Results and Organization
In non-convex optimization, we seek to minimize an objective function 𝐹 (Θ) over Θ ∈ R𝑑 . ECD requires an a priori guess 𝐹0 for the global minimum min 𝐹 , which defines the potential 𝑉 (Θ) := 𝐹 (Θ) − 𝐹0 , and simulates a classical or quantum dynamics that conserves a total energy 𝐸 (classical) or an energy distribution 𝜔(𝐸) (quantum).
2
Table 1: We study general one-dimensional positive double-well objectives, but instantiate our results to the symmetric case 𝑉 (Θ) = 𝜔 2 (Θ2 − 𝑎2 )2 /8𝑎2 + 𝑉0 with 𝑉0 > 0. Here, 𝛽 := 𝑉 (0) = 𝑎2 𝜔 2 /8 is the barrier height (see figure in Section 5.1). We compare expected hitting times from local minimum at −𝑎 to global minimum at +𝑎 for standard gradient descent methods (SGD [SSJ23] and QTW [LSL23]) and for sECD and qECD dynamics. The parameters 𝑠, ℎ, 𝐸, 𝜆𝑐 , 𝜆𝑞 are tunable in the respective dynamics and treated here as constants. Our results are asymptotic as 𝛽 → ∞.
Classical
Quantum
(︀ )︀ ≍ 𝑎𝜔𝑠3 exp 𝜔 2 𝑎2 /𝑠
1√ ≍ 𝑎𝜔3/2 exp 𝑎2 𝜔/ℎ ℎ
√ 1/4 𝜆𝑐 𝑎3/2 𝑉0 𝑎√ 𝐸 √ + 𝜔 √ )︁ (︁ (︁𝑉0 )︁ ≍ 𝜆𝑐 𝑎2 + 𝜔𝐸 log 𝑉𝛽0
𝜆𝑞 𝑎2 𝑉0 (︁ )︁ 𝜆 ≲ 𝜔𝑞2 log2 𝑉𝛽0
√
Gradient Descent ECD (𝑉0 ≳ 𝛽 Case) ECD (𝑉0 ≲ 𝛽 Case)
≍
(︀
)︀
≲
In Section 2.1, we describe the qualitative regimes of ECD determined by comparing 𝐹0 and min 𝐹 . This work focuses on one-dimensional double-well objectives in the under-guessing regime where 𝑉0 := min 𝐹 − 𝐹0 > 0. Our primary performance metric is the expected hitting time for the dynamics from the local minimum to the global minimum. In Sections 2.2 and 2.3, we formalize the sECD and qECD dynamics: to make sECD a viable optimizer, we introduce energy-preserving noise with tunable rate 𝜆𝑐 > 0 and hitting time is defined for this dynamics; in the quantum setting where continuous monitoring is unavailable without algorithmic overhead, the hitting time is defined via a quantum-walk-like protocol. Although Planck’s constant ℏ sets an overall energy scale for the semiclassical limit, we isolate the dynamical structure of the Hamiltonian via nondimensionalization, so that the dependence on physical constants is absorbed into a tunable rate 𝜆𝑞 > 0 analogous to 𝜆𝑐 . In Sections 3 and 4, we compute expected hitting times for sECD and qECD on general one-dimensional positive double-well potentials. Our assumptions on 𝑉 and the main results are stated in Section 2.4 and Theorems 3.2 and 4.1. For concreteness, Table 1 instantiates these results for 𝑉 (Θ) =
𝜔2 (Θ2 − 𝑎2 )2 + 𝑉0 , 8𝑎2
𝑉0 > 0.
(1.1)
The tunable parameters in ECD are the energy 𝐸 (classical) and the learning rates 𝜆𝑐 (classical) and 𝜆𝑞 (quantum); the latter are morally analogous to learning rates 𝑠 and ℎ in SGD and QTW. Let 𝛽 := 𝑉 (0) = 𝑎2 𝜔 2 /8 denote the barrier height; [LSL23] observes a quantum improvement in expected hitting time for QTW over SGD as 𝛽 → ∞. We compare the expected time for dynamics initialized at −𝑎 to reach +𝑎, separated by how under-guessing error 𝑉0 compares to barrier height 𝛽. In both regimes, we show that • sECD and qECD achieve exponential improvements in expected hitting time 3
over their respective baselines, SGD and QTW; this corresponds to a transition from exponential to low-degree polynomial scaling. Moreover, sECD exponentially improves relative to QTW. • As conserved energy 𝐸 is a tunable parameter for sECD but not for qECD, we compare qECD to the energy-independent lower bound on the sECD hitting time. As barrier height 𝛽 → ∞, qECD attains a further Ω(𝛽/ log 𝛽) improvement over sECD, mirroring the separation between QTW and SGD in [LSL23]. We expand and justify these comparisons in Section 5, and conclude with a discussion of future directions in Section 7. Most of the proofs are deferred to Section 6.
2
Preliminaries
2.1
Deterministic ECD in any Dimension
The deterministic ECD algorithm in R𝑑 was proposed by [DLS22,LGS23,DLNSZ25] as the first-order discretization of the coupled differential equations of position Θ𝑡 and momentum Π𝑡 , i.e. 𝑑Θ𝑡 2Π𝑡 = 𝑑𝑡 ‖Π𝑡 ‖2
𝑑Π𝑡 ∇𝑉 (Θ𝑡 ) =− . 𝑑𝑡 𝑉 (Θ𝑡 )
and
(2.1)
The equations have a time-independent Lagrangian formulation and, therefore, a conserved energy, giving ECD its name. We view it as a tunable parameter 𝐸. Lemma 2.1 ( [LGS23]). Let 𝐸 := ‖Π0 ‖2 𝑉 (Θ0 ). Then, 𝐸 = ‖Π𝑡 ‖2 𝑉 (Θ𝑡 ) for all 𝑡 ⩾ 0. We decouple the momentum Π𝑡 : its norm is given by √︃
‖Π𝑡 ‖ = 𝑝(Θ𝑡 )
where
𝐸 > 0. 𝑉 (𝜃)
(2.2)
Π𝑡 ∈ S𝑑−1 ‖Π𝑡 ‖
(2.3)
𝑝(𝜃) :=
Hence, for direction 𝑢𝑡 of Π𝑡 , (2.1) simplifies to 𝑑Θ𝑡 2𝑢𝑡 = 𝑑𝑡 𝑝(Θ𝑡 )
where
𝑢𝑡 :=
To define the algorithm, we set 𝑉 (Θ) = 𝐹 (Θ) − 𝐹0 where 𝐹 (Θ) is the objective function to minimize and 𝐹0 is the guess for the true minimum min 𝐹 of 𝐹 . We qualitatively describe the three regimes, depending on how they compare: • Exact-Guessing: if 𝐹0 = min 𝐹 , then min 𝑉 = 0. As we approach the global minimizer, 𝑉 → 0 and 𝑝 → ∞. Hence, 𝑑Θ𝑡 /𝑑𝑡 → 0 by (2.2) and we slow to a stop. • Over-Guessing: if 𝐹0 > min 𝐹 , then the same slow-down mechanism means we approach some Θ where 𝑉 (Θ) = 0 and so 𝐹 (Θ) = 𝐹0 , not the true minimizer. 4
• Under-Guessing: if 𝐹0 < min 𝐹 , then 𝑉 is bounded above zero everywhere, so 𝑝 is bounded above. Hence, Θ𝑡 never stationary, and the dynamics is recurrent. ECD behaves fundamentally differently than gradient descent methods like SGD: ECD slows down due to a diverging effective mass, while SGD slows down due to energy dissipation. It also has different failure modes: ECD is sensitive to the guess 𝐹0 , but it does not get stuck in local minima as long as 𝑉 is positive. These mechanisms are counterintuitive and are the key drivers of the exponential speedup of ECD over gradient descent methods. In this paper, we focus on the under-guessing regime that is the simplest theoretically, and study the exponential speedup.
2.2
One-Dimensional Stochastic ECD (sECD)
Fix energy 𝐸 > 0 and recall the decoupling Π𝑡 = 𝑝(Θ𝑡 )𝑢𝑡 . In one-dimension, direction 𝑢𝑡 ∈ {−1, 1}. By Theorem 2.1, Π𝑡 is never zero, so sign 𝑢𝑡 ≡ 𝑢0 never flips. In the under-guessing regime, 𝑝(Θ𝑡 ) is bounded above, so in fact Θ𝑡 moves in direction 𝑢0 forever and never returns. Unlike gradient descent, if ECD starts climbing up a potential barrier, it will continue to do so forever, and at increasing speed; although momentum decreases, effective mass vanishes. This is the negative counterpart of the miraculous slowdown mechanism in the exactly-guessing discussion. To mitigate this, noise must be introduced while conserving energy. For the discrete algorithm in R𝑑 , [LGS23] proposes a random rotation of momentum after every time-step 𝑡: pick 𝜈 > 0, sample 𝑧 ∼ 𝑁 (0, 𝐼𝑑 ), and update Π𝑡 ← (Π𝑡 + 𝜈𝑧)
‖Π𝑡 ‖ ‖Π𝑡 + 𝜈𝑧‖
(2.4)
which is observed empirically to induce turnarounds. Definition 2.2. In a forthcoming paper, we derive the continuum limit as time√ step Δ → 0 and 𝜈 ∼ 𝜂 Δ to get (︂ 𝑑𝑢𝑡 =
)︂ (𝐼𝑑 − 𝑢𝑡 𝑢⊤ 𝜂 2 (𝑑 − 1) 𝑡 )∇𝑉 (Θ𝑡 ) − 𝑢 𝑡 𝑑𝑡 ‖Π𝑡 ‖𝑉 (Θ𝑡 ) 2‖Π𝑡 ‖2 𝜂 (𝐼𝑑 − 𝑢𝑡 𝑢⊤ + 𝑡 )𝑑𝐵𝑡 ‖Π𝑡 ‖
−
(2.5)
and (2.3) as the sECD dynamics in R𝑑 for 𝑑 > 1. In one-dimension however, rotation are sign-flips of 𝑢𝑡 ∈ {−1, 1} and does not admit a continuous stochastic analog: flipping probability decays to 0 exponentially quickly as step-size Δ → 0, and we also see that (2.5) degenerates to 𝑑𝑢𝑡 = 0 for 𝑑 = 1. To recover something meaningful in the spirit of Theorem 2.3, we define the time-change 𝑑𝑠 2 𝑑Θ𝑠 = = 𝑢𝑠 𝑝(Θ𝑠 ). =⇒ 𝑑𝑡 𝑝(Θ𝑡 )2 𝑑𝑠 5
(2.6)
It turns out that this is the intrinsic time of sECD for 𝑑 > 1 and that 𝑢𝑠 ∈ S𝑑−1 is a diffusion with time and momentum independent parameters, so it flips at some constant rate 𝜆𝑑 > 0. Motivated by this, we introduce noise via a Poisson clock of constant rate 𝜆𝑐 in 𝑠-time that flips 𝑢𝑠 . Definition 2.3. The one-dimensional sECD dynamics is (2.6) where 𝑢𝑠 := 𝑢0 (−1)𝑃𝑠 for a Poisson process 𝑃𝑠 with constant rate 𝜆𝑐 > 0 in 𝑠-time, and initial conditions (Θ0 , 𝑢0 ). Our goal is to analyze the escape time of sECD from a local minimum to the global minimum in the one dimension under-guessing regime for double-well potential 𝑉 satisfying the assumptions in Section 2.4. We initialize Θ0 = −𝑎 at a local minimum, and compute the expected hitting time 𝑇hit := inf{𝑡 > 0 : Θ𝑡 = 𝑎}
(2.7)
in real time to the global minimum at 𝑎.
2.3
Quantum ECD (qECD)
For the quantum dynamics, we employ Dirac notation. A (pure) quantum state is a unit vector |𝜑⟩ in a complex Hilbert space ℋ = 𝐿2 (R𝑑 ), with a dual vector ⟨𝜑| = (|𝜑⟩)† and inner product ⟨𝜓|𝜑⟩. A Hamiltonian 𝐻 is a self-adjoint operator that generates unitary time evolution of the quantum system. Over ℋ, position basis {|𝑥⟩ : 𝑥 ∈ R𝑑 } yields the coordinate representation of the wavefunction 𝜑(𝑥) := ⟨𝑥|𝜑⟩. The quantum ECD dynamics simulates the Schrödinger equation: for imaginary unit 𝑖 and Planck’s constant ℏ 𝑖ℏ
𝜕 |Φ(𝑡)⟩ = 𝐻|Φ(𝑡)⟩, 𝜕𝑡
(2.8)
𝐻 is the Hamiltonian describing the quantized ECD dynamics. There is some freedom in defining a quantum mechanical version of classical deterministic ECD, which requires promoting the classical variables to quantum operators while preserving self-adjointness. In this work, we consider the simplest quantization, addressing the ambiguity in operator ordering by using the symmetric ordering. Definition 2.4. Given a potential function 𝑉 (Θ), starting from an initial quantum state 𝜓0 (Θ), the one-dimensional qECD dynamics is a continuous simulation of the unitary evolution 𝑈 (𝑡) = 𝑒−𝑖𝐻𝑡 with the Hamiltonian 𝐻 given by 𝐻 = −ℏ2 𝜕Θ (𝑉 (Θ)𝜕Θ ).
(2.9)
To employ standard semiclassical analysis, we perform asymptotic expansion as ℏ → 0. However, in Hamiltonian simulation, we can rescale 𝐻 which is effectively equivalent to tuning the value of ℏ; such scalings do not affect the validity 6
of the semiclassical analysis and have no impact on the simulation complexity which only tracks ‖𝐻𝑡/ℏ‖. To focus on the optimization dynamics comparison, we isolate this freedom in scaling into a dimensionless, tunable constant 𝜆𝑞 > 0 in analogy with 𝜆𝑐 in sECD via ˜ := 𝐻
1 𝜆2𝑞 ℏ2
1 𝐻 = − 2 𝜕𝑥 (𝑉 (𝑥)𝜕𝑥 ), 𝜆𝑞
(2.10)
˜ with that of sECD. We note the and compare the expected hitting time for 𝐻 following features in qECD, which introduces further complexity in performance analysis. While sECD initializes with position Θ0 and conserved energy 𝐸, qECD initializes with a quantum wavefunction 𝜓0 (Θ) which prescribes an energy spectral measure 𝜔(𝐸). This subtle difference is further discussed in Section 5.1. Since the quantum algorithm cannot be continuously monitored without affecting the state of the system, we choose the standard randomized protocol from quantum walks literature [CCD+ 03], which evolves the quantum system for a randomly chosen time 𝑡 ∈ [0, 𝜏 ]. At time 𝑡, we denote the amplitude of the quantum state by 𝜓(Θ, 𝑡), so the probability density of the wavefunction is Θ ↦→ |𝜓(Θ, 𝑡)|2 . Then, the probability of successfully detecting the state within a 𝜎neighborhood around the global minimum 𝑎 at time 𝑡 is ∫︁ 𝑎+𝜎
𝑝𝜎 (𝑡) =
(2.11)
𝑑𝜃|𝜓(𝜃, 𝑡)|2 ,
𝑎−𝜎
√ for some small 𝜎 = 𝑂( ℏ) we choose. Physically, this is a natural choice of length scale set by the ground state of a harmonic potential. This protocol is then repeated independently to ensure at least one successful detection. Based on this protocol, we introduce the notion of hitting time for comparison with classical results. Definition 2.5. The expected hitting time of the qECD dynamics starting from 𝜓0 (Θ) to an 𝜎-neighborhood of 𝑎 is 𝜏 𝑇𝜖 (𝜓0 |𝑎) := inf 𝜏 >0 𝑝𝜎 (𝜏 )
where
𝑝𝜎 (𝜏 ) :=
∫︁ 𝜏 0
𝑑𝑡 𝑝𝜎 (𝑡) 𝜏
(2.12)
is the averaged success probability for one trial.
2.4
Assumptions and Notations
We focus on a one-dimensional double-well objective 𝐹 : R → R in the underguessing regime (𝐹0 < min 𝐹 ) and make two assumptions on potential function 𝑉 = 𝐹 − 𝐹0 : • 𝑉 is a 𝐶 1 -function with exactly two local minima that we without loss of generality assume to be {−𝑎, 𝑎} for 𝑎 > 0. Let 𝑉0 := 𝑉 (𝑎) > 0 be the global minimum and let 𝑉1 := 𝑉 (−𝑎) > 𝑉0 be the local minimum. 7
• Tail condition: 𝑉 (𝜃) → ∞ as |𝜃| → ∞, and ∫︁ |𝜃|>𝑎
√︀
𝑑𝜃 < ∞. 𝑉 (𝜃)
(2.13)
A sufficient condition is super-quadratic growth: there exist 𝑐 > 2 such that 𝑉 (𝜃) ≳ |𝜃|𝑐 as |𝜃| → ∞. We adopt standard asymptotic notation, with the limiting regime clear from context: 𝑓 ≲ 𝑔 denotes 𝑓 = 𝑂(𝑔), 𝑓 ≪ 𝑔 denotes 𝑓 = 𝑜(𝑔), 𝑓 ≍ 𝑔 denotes 𝑓 = Θ(𝑔), and 𝑓 ∼ 𝑔 denotes 𝑓 /𝑔 = 1 + 𝑜(1). For a Markov process 𝑋𝑡 , we adopt standard notation E𝑥 and P𝑥 as expectation and probability conditioned on 𝑋0 = 𝑥.
3
Analyzing Stochasic ECD
3.1
Setup and Main Result
We begin with a coordinate-change: let 𝑥𝑡 := 𝜑(Θ𝑡 ) where ∫︁ 𝜃
𝑑𝜉 1 𝜑(𝜃) := =√ 𝐸 −𝑎 𝑝(𝜉)
∫︁ 𝜃 √︁
𝑉 (𝜉) 𝑑𝜉.
−𝑎
(3.1)
Then, local minima 𝜃 = ±𝑎 maps to 𝑥 = 0 and 𝑥 = 𝐿 := 𝜑(𝑎). By (2.6), the 𝑥-dynamics is 𝑑𝑥𝑠 /𝑑𝑠 = 𝑢𝑠 ∈ {±1}, and for any 𝑠-time stopping 𝑆, the corresponding real time is 1 𝑇 (𝑆) := 2
∫︁ 𝑆
𝑝(𝜑−1 (𝑥𝑠 ))2 𝑑𝑠.
0
(3.2)
We can compute the hitting time for the noiseless dynamics. Proposition 3.1. If 𝑢𝑠 ≡ 1 is constant, and initially Θ0 = −𝑎, then the deterministic real time to hit 𝑎 is 𝑇det =
1 2
∫︁ 𝐿
𝑝(𝜑−1 (𝑥))2 𝑑𝑥 =
0
1 2
∫︁ 𝑎
𝑝(𝜃) 𝑑𝜃. −𝑎
(3.3)
Our main result for the classical case is the following analog for double-wells when we inject noise as in Section 2.2. Theorem 3.2. For 𝑉 satisfying assumptions in Section 2.4, and the stochastic ECD (sECD) dynamics in Theorem 2.3 with Θ0 = −𝑎, the expected hitting time to 𝑎 is given by )︂ ∫︁ 𝑎 (︂∫︁ 𝑎 𝑑𝜉 𝑇det + 𝜆𝑐 𝑝(𝜃) 𝑑𝜃 −𝑎 𝜃 𝑝(𝜉) (3.4) )︁ ∫︁ −𝑎 (︁ + 𝜆𝑐 𝐿 + 1{𝑢0 =−1} 𝑝(𝜃)𝑑𝜃 −∞
with 𝑇det from (3.3), 𝐿 = 𝜑(𝑎) from (3.1), and 𝑝 from (2.2). 8
We observe that the first line corresponds to the time we spend exploring [−𝑎, 𝑎] and it converges to the deterministic hitting time as noise 𝜆𝑐 → 0; the second line corresponds to we spend exploring the tail [−∞, −𝑎], and there is an extra term if we initialize towards the tail, i.e. 𝑢0 = −1. We now simplify if 𝑉 is symmetric, i.e. 𝑉 (𝜉) = 𝑉 (−𝜉) for all 𝜉. Corollary 3.3. If 𝑉 is a symmetric double-well, then the expected hitting time to 𝑎 of sECD with Θ0 = −𝑎 is ∫︁ ∞
(1 + 𝜆𝑐 𝐿) 0
3.2
𝑝(𝜃)𝑑𝜃 − 1{𝑢0 =1}
∫︁ ∞
𝑝(𝜃)𝑑𝜃. 𝑎
(3.5)
Embedded Four-State Markov Chain
Under the space-change in (3.1), let 𝑆𝑛 be the 𝑠-time of the 𝑛-th visit to minima {−𝑎, 𝑎}, and let 𝑍𝑛 := (𝑋𝑛 , 𝑈𝑛 ) := (𝑥𝑆𝑛 , 𝑢𝑆𝑛 ). Then (𝑍𝑛 ) is a Markov chain on four states 𝒵 := {(0, −), (0, +), (𝐿, −), (𝐿, +)}. (3.6) We call (0, +) and (𝐿, −) inwards states, while (0, +) and (𝐿, −) are outwards states, relative to the interval [0, 𝐿]. The transitions (0, −) → (0, +) and (𝐿, +) → (𝐿, −) from outward states are deterministic: we must return to the inward state at the same well before hitting the other well. Starting at an inwards state, we could either cross the barrier and preserve signs, or return to the starting position and reverse signs. Let 𝑞 be the crossing probability. These notions are spelled out in Section 3.3 via the telegraph process. The transition matrix with states listed in order as (3.6) is ⎛
0 ⎜1 − 𝑞 ⎜ 𝑃 := ⎜ ⎝ 𝑞 0
1 0 0 0
⎞
0 0 0 𝑞 ⎟ ⎟ ⎟. 0 1 − 𝑞⎠ 1 0
(3.7)
Let 𝐷hit be the number of discrete steps until first arrival to the global well 𝑎, i.e. the smallest 𝑛 such that 𝑥𝑛 = 𝐿. Without computing 𝑞, we make the following observation. Proposition 3.4. The stationary distribution of 𝑃 is uniform on 𝒵, and the expected hitting time is E(0,+) [𝐷hit ] =
3.3
2 − 1, 𝑞
2 E(0,−) [𝐷hit ] = . 𝑞
(3.8)
The Telegraph Process
We now isolate and analyze the key process governing 𝑞 and barrier crossing, which will allow as to compute transition times of 𝑍𝑛 and hitting times of Θ𝑡 and 𝑥𝑠 . 9
Let (𝑋𝑠 , 𝑈𝑠 ) be the telegraph process with 𝑋0 = 0, 𝑈0 = 1, and 𝑑𝑋𝑠 /𝑑𝑠 = 𝑈𝑠 which flips with rate 𝜆𝑐 > 0. Define 𝑆 := inf{𝑠 > 0 : 𝑋𝑠 ∈ {0, 𝐿}}.
(3.9)
as the exit time on [0, 𝐿]. All results below are proved by solving the corresponding boundary value problems ℒℎ = 0 (harmonic) or ℒ𝑔 = −𝑤 (Poisson) for generator ℒ. They are standard exercises deferred to Section 6.1. Proposition 3.5. Define 𝑞 := P(0,+) (𝑋𝑆 = 𝐿). Then, 𝑞=
1 . 1 + 𝜆𝑐 𝐿
(3.10)
For an integrable running cost 𝑤 : R → [0, ∞) define 𝐺± (𝑥) := E(𝑥,±)
[︃∫︁
]︃
𝑆
𝑤(𝑋𝑠 ) 𝑑𝑠 . 0
(3.11)
Lemma 3.6. Assume 𝐺− (0) = 0 and 𝐺+ (𝐿) = 0. Then ∫︁ 𝐿
𝐺+ (0) = 𝑞
(1 + 2𝜆𝑐 (𝐿 − 𝑥))𝑤(𝑥) 𝑑𝑥, (3.12)
0
∫︁ 𝐿
(1 + 2𝜆𝑐 𝑥)𝑤(𝑥) 𝑑𝑥.
𝐺− (𝐿) = 𝑞 0
We also need the analogous statement on a half-line R± instead of an interval. The computation follows the interval [0, 𝐿] case upon taking 𝐿 → ∞. We record this formally. Lemma 3.7. For stopping time 𝜎 := inf{𝑠 > 0 : 𝑋𝑠 = 0} and integrable 𝑤, then 𝜎 < ∞ almost surely and [︂∫︁ 𝜎
E(𝑥,±)
]︂
∫︁
𝑤(𝑋𝑠 ) 𝑑𝑠 = 2 0
𝑤(𝑥) 𝑑𝑥.
(3.13)
R±
We will apply this to the ECD running cost 𝑤 to the tails of 𝑉 , so the tail condition gives integrability of 𝑤.
3.4
Transition and Hitting Times
Consider the semi-Markov process given by 𝑍𝑛 = (𝑋𝑛 , 𝑈𝑛 ) and real time 𝑇𝑛 associated with 𝑍𝑛 . Let Δ𝑡 the real time associated with one transition step of 𝑍𝑛 , analogous to 𝑇det from (3.3). We compute Δ𝑡 by Theorems 3.6 and 3.7 with 𝑤(𝑥) :=
𝑑𝑡 1 = 𝑝(𝜑−1 (𝑥))2 . 𝑑𝑠 2 10
(3.14)
Proposition 3.8. For outwards states 𝑧 ∈ {(0, −), (𝐿, +)} ∫︁ −𝑎
E(0,−) [Δ𝑡] =
𝑝(𝜃) 𝑑𝜃, −∞ ∫︁ ∞
(3.15) 𝑝(𝜃) 𝑑𝜃,
E(𝐿,+) [Δ𝑡] =
𝑎
are finite by (2.13). For inwards state 𝑧 ∈ {(0, +), (𝐿, −)} E𝑧 [Δ𝑡] = (𝑇det + 𝜆𝑐 𝐵𝑧 )𝑞,
(3.16)
where 𝑞 and 𝑇det are defined in (3.3) and (3.10), as well as 𝐵(0,+) := 𝐵(𝐿,−) :=
∫︁ 𝑎 (︂∫︁ 𝑎 −𝑎
𝜃
∫︁ 𝑎 (︃∫︁ 𝜃 −𝑎
𝑑𝜉 𝑝(𝜃) 𝑑𝜃, 𝑝(𝜉) )︂
)︃
𝑑𝜉 𝑝(𝜃) 𝑑𝜃. −𝑎 𝑝(𝜉)
(3.17)
Let 𝑇hit and 𝑆hit be the real time and 𝑠-time to first hit the global well 𝑎, analogous to 𝐷hit . With 𝑞 in (3.10), we now compute their the expectations, similar to Theorem 3.4. Proposition 3.9. Under (2.13), the stationary distribution of the semi-Markov process is proportional to E𝑧 [Δ𝑡], and E(0,+) [Δ𝑡] + (1 − 𝑞)E(0,−) [Δ𝑡] , 𝑞 E(0,+) [Δ𝑡] + E(0,−) [Δ𝑡] E(0,−) [𝑇hit ] = . 𝑞 E(0,+) [𝑇hit ] =
(3.18)
Combining Theorems 3.8 and 3.9 gives Theorem 3.2. We remark that the key simplification via symmetry in Theorem 3.3 is 𝐵(0,+) = 𝐵(𝐿,−) and they sum to 2𝐿𝑇det .
4
Analyzing Quantum ECD
4.1
Setup and Main Result
A quantum state evolving under the qECD dynamics has a position-dependent local momentum 𝑝 given by (2.2). Analogous to (3.1), we define the Liouville coordinates ∫︁ Θ 𝑑𝑥 √︀ 𝑦(Θ) := . (4.1) 𝑉 (𝑥) 0 To simplify notation, we also define the distance integral 𝐼(Θ1 , Θ2 ) := 𝑦(Θ2 ) − 𝑦(Θ1 ). 11
(4.2)
We fix objective function 𝑉 satisfying Section 2.4 and take the semiclassical limit ℏ → 0 to compute the expected hitting time (Theorem 2.5) from 𝜓0 to 𝑎 for qECD and a general positive double-well 𝑉 . Before stating our main results on hitting times of qECD, we formalize parameter choices for the qECD dynamics. • The initial √ quantum state is a zero-momentum Gaussian wavefunction of width 𝜎 = 𝑂( ℏ) centered at the local minimum −𝑎, i.e. {︃
}︃
(Θ + 𝑎)2 1 exp − . 𝜓0 (Θ) := 4𝜎 2 (2𝜋𝜎 2 )1/4
(4.3)
• The detection window [𝑎 − 𝜎, 𝑎 + 𝜎] around global minimum 𝑎 has the same width, following (2.11). Heuristically, the choice of 𝜎 guarantees that as ℏ → 0, the potential function in the respective windows is 𝑂(ℏ) away from 𝑉 (𝑎) = 𝑉0 and 𝑉 (−𝑎) = 𝑉1 , respectively. Theorem 4.1√(Quantum Hitting Time). For 𝑉 satisfying assumptions in Section 2.4 and 𝜎 = 𝑂( ℏ), there exists an absolute numerical constant 𝑐 > 0 such that the expected hitting time of the qECD dynamics (Theorem 2.4) with Hamiltonian 𝐻 and as ℏ → 0 is at most √︃ 𝐼(−𝑎, 𝑎)2 𝑉0 [𝑐 + 𝑂(ℏ)]. (4.4) ℏ 𝑉1 As discussed in Section 2.3, we compare the expected hitting time for sECD ˜ in (2.10) for suffiwith that of qECD under the time-evolution of the rescaled 𝐻 ciently small ℏ to obtain Corollary 4.2. In the setting of Theorem 4.1, the expected hitting time for the qECD ˜ is with rescaled Hamiltonian 𝐻 √︃
𝑇ℎ𝑖𝑡 (𝜓0 |𝑎) ⩽ 2𝑐𝜆𝑞 𝐼(−𝑎, 𝑎)2
4.2
𝑉0 . 𝑉1
(4.5)
Energy-domain Analysis
The energy eigenstates of the Hamiltonian 𝐻 can be derived from the time-independent Schrödinger equation −ℏ2 (𝜕Θ 𝑉 𝜕Θ )𝜓 = 𝐸𝜓. (4.6) Naively, the absence of "turning points" in the under-guessed landscape suggests a continuous spectrum. Upon closer inspection, the super-quadratic tails assumed in 𝑆𝑒𝑐𝑡𝑖𝑜𝑛 2.4 enforces a discrete, quantized spectrum due to domain compaction in Liouville coordinates.
12
Lemma 4.3. Under assumptions in Section 2.4, the qECD Hamiltonian has a discrete energy spectrum bounded below by 0, and a finite effective domain length given by 𝐿 = 𝐼(−∞, ∞) < ∞.
(4.7)
We separate the low energy (non-semiclassical) and high energy (semiclassical) contributions according to the WKB approximation. Define the WKB energy cut-off }︃ {︃ ⃒ ⃒ ′′ |𝑉 ′ (𝑥)|2 2 ⃒ ⃒ (4.8) 𝑉 (𝑥) . 𝐸𝑐𝑢𝑡 := ℏ max sup , sup 𝑥∈[−2𝑎,2𝑎] 𝑉 (𝑥) 𝑥∈[−2𝑎,2𝑎] Within the semiclassical regime where 𝐸 ≫ 𝐸𝑐𝑢𝑡 , we take the asymptotic expansion of the plane wave ansatz 𝜓(Θ) = exp[𝑖𝜑(Θ)/ℏ] as ℏ → 0 to obtain the following approximate solution to the Schrödinger equation (4.6). Lemma 4.4. For 𝐸 ≫ 𝐸𝑐𝑢𝑡 , the qECD Hamiltonian as ℏ → 0 has quantized energy eigenstates (indexed by 𝑛) (︃ )︃ √ ∫︁ 𝑛𝜋 Θ 1 2 √︀ 𝜓𝑛 (Θ) = √ sin 𝑑𝑥 + 𝑂(ℏ) (4.9) 𝐿 −∞ 𝑉 (𝑥) 𝐿𝑉 (Θ)1/4
4.3
Time-domain Analysis
Given the time-propagator kernel 𝐾(Θ2 , 𝑡; Θ1 , 0) := ⟨Θ2 |𝑒−𝑖𝐻𝑡/ℏ |Θ1 ⟩, and an initial wave packet 𝜓0 (Θ), its amplitude at time 𝑡 under the Hamiltonian evolution is ∫︁ 𝜓(Θ, 𝑡) := 𝑑Θ′ 𝐾(Θ, 𝑡; Θ′ , 0)𝜓0 (Θ′ ), (4.10) and the time-propagator kernel admits expansion ∑︁
𝐾(Θ2 , 𝑡; Θ1 , 0) =
𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝜓𝑛 (Θ2 )𝜓𝑛* (Θ1 ).
(4.11)
𝐸𝑛
We analyze the semiclassical (𝐸 ≫ 𝐸𝑐𝑢𝑡 ) and low-energy (𝐸 ≲ 𝐸𝑐𝑢𝑡 ) contributions to 𝐾 separately as follows. Lemma 4.5. Asymptotically as ℏ → 0, the low-energy contribution to the timepropagator is 𝐾𝑙𝑜𝑤 :=
𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝜓𝑛 (Θ2 )𝜓𝑛 (Θ1 ) ≲ 1.
∑︁
(4.12)
𝑛:𝐸𝑛 ≲𝐸𝑐𝑢𝑡
Lemma 4.6. There exists constant 𝛿 > 0 depending only on potential 𝑉 such that asymptotically as ℏ → 0, for any 𝑡<
𝛿𝐼(Θ1 , Θ2 ) , ℏ 13
(4.13)
the semiclassical contribution to the time-propagator is 𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝜓𝑛 (Θ2 )𝜓𝑛* (Θ1 )
∑︁
𝐾𝑤𝑘𝑏 :=
𝑛:𝐸𝑛 ≫𝐸𝑐𝑢𝑡 2
{︁ [︁
(4.14)
]︁}︁
1 ,Θ2 ) − 𝜋4 + 𝑂(ℏ) exp 𝑖 𝐼(Θ4ℏ𝑡 √ = 2 𝜋ℏ𝑡(𝑉 (Θ1 )𝑉 (Θ2 ))1/4
.
Up to the time scale (4.13) that will cover our hitting time (see Theorem 4.9), the phase saddle point lies in the semiclassical region, so the integral in (4.14) can be evaluated using a quadratic stationary-phase approximation. We now note that 𝐾𝑙𝑜𝑤 is asymptotically smaller than 𝐾𝑤𝑘𝑏 as ℏ → 0. Corollary 4.7. For any time 𝑡 satisfying (4.13), asymptotically as ℏ → 0, the timepropagator of the qECD dynamics is 2
{︁ [︁
]︁}︁
1 ,Θ2 ) exp 𝑖 𝐼(Θ4ℏ𝑡 − 𝜋4 𝐾(Θ2 , 𝑡; Θ1 , 0) = √ + 𝑂(1). 2 𝜋ℏ𝑡(𝑉 (Θ1 )𝑉 (Θ2 ))1/4
4.4
(4.15)
Hitting Time
Using the qECD time-propagator, we analyze the time-evolved quantum state (4.10) via a saddle-point expansion of the integral. Lemma 4.8. Starting with an initial state (4.3) and evolving under qECD dynamics for time 𝑡 satisfying (4.13), the probability density of the quantum state is given by }︁
{︁
|𝜓(Θ, 𝑡)|2 =
2 ′ ℏ Re{Φ(Θ* )} √︀ , 2𝑡 2𝜋𝛼2 ℏ𝑉1 |𝑉 (Θ′* )||Φ′′ (Θ′* )|
[1 + 𝑂(ℏ)] exp
(4.16)
√ where 𝛼 = 𝜎/ ℏ ≲ 1 and Θ′* is a complex saddle point of Φ(Θ) := −
(Θ + 𝑎)2 𝐼(Θ′ , Θ)2 + 𝑖 . 4𝛼2 4𝑡
(4.17)
With measurement window [𝑎 − 𝜎, 𝑎 + 𝜎], the instantaneous transition probability 𝑝𝜎 is given in (2.11). This allows us to derive the following result for its time-averaged counterpart. Lemma 4.9. For 𝑡 satisfying (4.13) with (Θ1 , Θ2 ) = (−𝑎, 𝑎), the average transition probability 𝑝𝜖 (𝜏 ) in (2.12) is given by 𝐴 𝑝𝜎 (𝜏 ) = [1 + 𝑂(ℏ)] 2𝜏 asymptotically as ℏ → 0, where √ 2 2𝛼 𝐴 := √ 𝜋𝑉1 𝑉0
and 14
𝑒−𝑧 𝑑𝑧, 𝐵/𝜏 2 𝑧
(4.18)
𝛼2 𝐼02 . ℏ𝑉1
(4.19)
∫︁ ∞
𝐵 :=
Now, we upper bound the expected hitting time in (2.12) by choosing 𝜏 to √ be a numerical constant times 𝐼(−𝑎, 𝑎)/ ℏ𝑉1 . In the appendix, we check that this satisfies (4.13) and recovers the upper bound in Theorem 4.1 on the expected hitting time. We remark that we believe a matching lower bound up to numerical constants hold; an analysis of 𝐾𝑤𝑘𝑏 for time 𝑡 beyond (4.13) is required.
5
Case Study Comparison
5.1
Setup and Configuration
Recall from (1.1) the particular symmetrical double-well potential in the underguessing regime, corresponding to objective 𝐹 (Θ) = 𝜔 2 (Θ2 − 𝑎2 )2 /8𝑎2 and under-guess 𝐹0 = −𝑉0 < 0. Note that 𝑉 satisfies assumptions in Section 2.4. We define the barrier height of 𝑉 as 1 𝛽 := 𝑉 (0) = 𝑎2 𝜔 2 . 8
(5.1)
Figure 1: Figure of symmetrical double well in the under-guessing regime.
We further specify sECD and qECD configuration beyond Section 2 to enable a fair expected hitting time comparison. 1. In qECD, we assume the initial Gaussian wavepacket 𝜓0 centered at −𝑎 and the√detection neighborhood at +𝑎 to both have sufficiently small width 𝜎 = 𝑂( ℏ). Our results in the classical setting has no window, but the corresponding expected hitting times for sECD with sufficiently small nonzero initialization and hitting window width 𝜎 recover E[𝑇hit ] asymptotically. 2. In qECD, direction 𝑢0 and energy 𝐸 are fixed by 𝜓0 . To guarantee a quantum advantage, we lower bound the classical hitting time by terms independent of 𝐸 and 𝑢0 , and show that the qECD hitting time is asymptotically smaller. In 15
particular, this lower bound corresponds to the favorable initialization with 𝑢0 = 1 and 𝐸 small. 3. We treat tunable learning rates 𝑠, ℎ, 𝜆𝑐 , 𝜆𝑞 for the respective dynamics as constants in the 𝛽 → ∞ limit. Next, we justify Table 1 and conclusions in Section 1.2. We compute the expected hitting times for 𝑉 in (1.1) to observe exponential speedup from gradient descent baselines in [SSJ23, LSL23], before specializing to the configuration assumptions above to demonstrate a quantum advantage as 𝛽 → ∞, thereby extending the separation between QTW and SGD observed in [LSL23] to the setting of qECD versus sECD. Our results in this section are asymptotically as 𝛽 → ∞ and separate into cases according to how the under-guessing error 𝑉0 compares with 𝛽.
5.2
Small Under-Guessing Error: 𝑉0 ≲ 𝛽
We compute via Theorem 3.3 and Theorem 4.1 polynomial expected hitting times of the sECD and qECD dynamics, in contrast with SGD and QTW baselines in [SSJ23, LSL23]. This justifies the exponential speedup of ECD dynamics over gradient descent based dynamics. Theorem 5.1. For potential 𝑉 in (1.1) with 𝑉0 ≲ 𝛽, the expected hitting time of sECD is asymptotically (︃ √ )︃ (︂ )︂ 𝐸 𝛽 2 𝑇𝑐 := 𝜆𝑐 𝑎 + log (5.2) 𝜔 𝑉0 for both 𝑢0 ∈ {±1}; the expected hitting time of qECD is 𝜆𝑞 𝛽 𝑇𝑞 ≲ 2 log2 . 𝜔 𝑉0 (︂
)︂
(5.3)
We lower bound 𝑇𝑐 uniformly over 𝐸 > 0 by its first term to see a Ω(𝛽/ log 𝛽) factor quantum advantage as 𝛽 → ∞. Corollary 5.2. Under configuration assumptions in Section 5.1, if 𝑒−𝑂(𝛽) ⩽ 𝑉0 ≲ 𝛽 as barrier 𝛽 → ∞, then 𝛽 𝑇𝑐 ≳ 𝑎 log 𝑉0 2
(︂
)︂
1 𝛽 ≫ 2 log2 𝜔 𝑉0 (︂
)︂
≳ 𝑇𝑞 .
(5.4)
The lower bound on under-guessing error 𝑉0 ensures the log-term does not dominate; when 𝑉0 is exponentially smaller than 𝛽, we are essentially in the exactguessing regime. Moreover, a natural algorithmic design is to run ECD iteratively in a bisection-style search so 𝐹0 converges to min 𝐹 from below. Then, quantum speedups persists when 𝑉0 is halved for Ω(𝛽) iterations, starting from 𝑉0 ≍ 𝛽. 16
5.3
Large Under-Guessing Error: 𝑉0 ≳ 𝛽
Here, in Theorem 3.3, the tail integral dominates, so most of the running time classically is exploring (−∞, −𝑎]. Theorem 5.3. For potential 𝑉 in (1.1) with 𝑉0 ≳ 𝛽, the expected hitting time of sECD is asymptotically ⎛
√︃
𝑇𝑐 := ⎝1{𝑢0 =−1} + 𝜆𝑐 𝑎
√ ⎞√︃ 𝑉0 𝑎𝜔 𝑎𝐸 −1/4 , + 1/4 ⎠ 𝑉 𝐸 𝜔 0 𝑉
(5.5)
0
depending on 𝑢0 ; the expected hitting time of qECD is 𝑇𝑞 ≲
𝜆𝑞 𝑎2 . 𝑉0
(5.6)
We lower bound 𝑇𝑐 uniformly over 𝐸 > 0 and initial direction 𝑢0 ∈ {−1, 1} by its middle term in (5.5) to see a Ω(𝛽) factor quantum advantage as barrier height 𝛽 → ∞. Corollary 5.4. Under configuration assumptions in Section 5.1, if 𝑉0 ≳ 𝛽 as barrier height 𝛽 → ∞, then 1/4
𝑇𝑐 ≳ 𝑎3/2 𝜔 −1/2 𝑉0
≫
𝑎2 ≳ 𝑇𝑞 . 𝑉0
6
Additional Proofs
6.1
Proofs of Telegraph Propositions in Section 3.3
(5.7)
Let 𝜆 = 𝜆𝑐 . We sketch the boundary value problems proofs with the same template: define the quantity of interest depending on state (𝑥, 𝑢) ∈ R × {±}, write ℒℎ = 0 or ℒ𝐺 = −𝑤, impose boundary conditions, and solve the resulting ODE system. The generator on (0, 𝐿) is (ℒ𝑓 )+ (𝑥) = 𝑓+′ (𝑥) + 𝜆(𝑓− (𝑥) − 𝑓+ (𝑥)), (ℒ𝑓 )− (𝑥) = −𝑓−′ (𝑥) + 𝜆(𝑓+ (𝑥) − 𝑓− (𝑥)).
(6.1)
Proof of Theorem 3.5. Let ℎ± (𝑥) = P𝑥,± (𝑋𝑇 = 𝐿). On (0, 𝐿), ℒℎ = 0 gives ℎ′+ (𝑥) + 𝜆(ℎ− (𝑥) − ℎ+ (𝑥)) = 0,
−ℎ′− (𝑥) + 𝜆(ℎ+ (𝑥) − ℎ− (𝑥)) = 0.
Note that ℎ− (0) = 0 and ℎ+ (𝐿) = 1. Subtract the equations to get (ℎ+ − ℎ− )′ = 0, hence ℎ+ − ℎ− = 𝐷 is constant. Then ℎ′+ (𝑥) = 𝜆𝐷, so ℎ+ (𝑥) = ℎ+ (0) + 𝜆𝐷𝑥 and ℎ− (𝑥) = ℎ+ (𝑥)−𝐷. From ℎ− (0) = 0 we get ℎ+ (0) = 𝐷, and from ℎ+ (𝐿) = 1 we get 𝐷(1 + 𝜆𝐿) = 1, so 𝑞 = ℎ+ (0) = 𝐷 = 1/(1 + 𝜆𝐿). 17
Proof of Theorem 3.6. Recall that 𝐺− (0) = 0 and 𝐺+ (𝐿) = 0. Then, ℒ𝐺 = −𝑤 on (0, 𝐿) gives 𝐺′+ + 𝜆(𝐺− − 𝐺+ ) = −𝑤,
−𝐺′− + 𝜆(𝐺+ − 𝐺− ) = −𝑤,
Set 𝐷 = 𝐺+ − 𝐺− and 𝑆 = 𝐺+ + 𝐺− , so 𝐷′ = −2𝑤 and 𝑆 ′ = 2𝜆𝐷. As 𝐺− (0) = 0, 𝑐 := 𝑆(0) = 𝐷(0). We have 𝑆(𝐿) = −𝐷(𝐿)
𝑐 := 𝑆(0) = 𝐷(0) Let 𝑊 (𝑥) =
∫︀ 𝑥
∫︀ 𝑥 0 𝑤(𝑢)𝑑𝑢 and 𝑉 (𝑥) = 0 (𝑥 − 𝑢)𝑤(𝑢)𝑑𝑢, so
𝐷(𝑥) = 𝑐 − 2𝑊 (𝑥) =⇒ 𝑆(𝑥) = 𝑐 + 2𝜆
∫︁ 𝑥
𝐷(𝑢)𝑑𝑢 = 𝑐 + 2𝜆𝑐𝑥 − 4𝜆𝑉 (𝑥)
0
Now, as 𝐺+ (𝐿) = 0 0 = 𝐷(𝐿)+𝑆(𝐿) = 𝑐−2𝑊 (𝐿)+𝑐+2𝑐𝜆𝐿−4𝜆𝑉 (𝐿) =⇒ 𝑐 =
𝑊 (𝐿) + 2𝜆𝑉 (𝐿) 1 + 𝜆𝐿
This is exactly 𝐺+ (0). To solve for 𝐺− (𝐿), we plug 𝑐 into 𝐷(𝐿). Proof of Theorem 3.7. Let 𝜎𝐿 = inf{𝑠 > 0 : 𝑋𝑠 ∈ {0, 𝐿}}, so by Theorem 3.5 1 =0 𝐿→∞ 1 + 𝜆𝐿
P(0,+) (𝜎 = ∞) = lim P(0,+) (𝑋𝜎𝐿 = 𝐿) = lim 𝐿→∞
Hence, 𝜎 is finite almost surely. Conditioned on this∫︀event, the path ∫︀maximum 𝑀 = sup𝑠∈[0,𝜎] 𝑋𝑠 is finite, so along each sample path 0𝜎𝐿 𝑤(𝑋𝑠 )𝑑𝑠 = 0𝜎 𝑤(𝑋𝑠 )𝑑𝑠 for any 𝐿 > 𝑀 is eventually constant. By monotone convergence as 𝐿 → ∞ [︂∫︁ 𝜎
E(0,+)
0
[︂∫︁ 𝜎𝐿
]︂
𝑤(𝑋𝑠 )𝑑𝑠 = lim E(0,+) 𝐿→∞
]︂
𝑤(𝑋𝑠 )𝑑𝑠 0
To compute the right hand side, we use Theorems 3.5 and 3.6 and integrability of 𝑤 to compute ∞ (1 + 2𝜆𝐿) 0𝐿 𝑤(𝑥)𝑑𝑥 − 2𝜆 0𝐿 𝑥𝑤(𝑥) 𝑑𝑥 𝑞 (1 + 2𝜆(𝐿 − 𝑥))𝑤(𝑥) 𝑑𝑥 = →2 𝑤(𝑥)𝑑𝑥 1 + 𝜆𝐿 0 0 (6.2) 1 ∫︀ 𝐿 as 𝐿 → ∞, where the fact that 𝐿 0 𝑥𝑤(𝑥)𝑑𝑥 → 0 as 𝐿 → ∞ for integrable 𝑤 is a standard exercise in real analysis.
∫︁ 𝐿
6.2
∫︀
∫︀
∫︁
Proofs of Other Results in Section 3
Proof of Theorem 3.1. Since 𝑢𝑠 ≡ 1, then 𝑑𝑥/𝑑𝑠 = 1, so by (2.6) and (3.2) 1 𝑇det = 2
∫︁ 𝑆
𝑝(𝜑 0
−1
1 (𝑋𝑠 )) 𝑑𝑠 = 2 2
∫︁ 𝐿
𝑝(𝜑 0
where we observe 𝑑𝑥/𝑑𝜃 = 𝜑′ (𝜃) = 1/𝑝(𝜃). 18
−1
1 (𝑥)) 𝑑𝑥 = 2 2
∫︁ 𝑎
𝑝(𝜃)𝑑𝜃 −𝑎
(6.3)
Proof of Theorem 3.4. From (0, +), with probability 𝑞 we hit the right well in one leg; with probability 1 − 𝑞 we return to (0, −) in one leg. From (0, −), we always take one outward-return leg to (0, +). Thus, we have a linear system (︁
)︁
E(0,+) [𝐷hit ] = 𝑞 + (1 − 𝑞) 1 + E(0,−) [𝐷hit ]
(6.4)
E(0,−) [𝐷hit ] = 1 + E(0,+) [𝐷hit ] which solves to the desired.
Proof of Theorem 3.8. Recall that 𝑤(𝑥) = 𝑝(𝜑−1 (𝑥))2 /2. By Theorem 3.7, we compute ∫︁ ∞
E(0,−) [Δ𝑡] = 2
∫︁ 0
𝑝(𝜑
𝑤(𝑥)𝑑𝑥 =
−1
2
𝑝(𝜃)𝑑𝜃.
(𝑥)) 𝑑𝑥 = −∞
−∞
0
∫︁ −𝑎
(6.5)
where we observe 𝑑𝑥/𝑑𝜃 = 𝜑′ (𝜃) = 1/𝑝(𝜃). The same holds for the other outwards state, i.e. E(𝐿,+) [Δ𝑡]. From (0, +), we recall 𝑤 to compute that ∫︁ 𝐿
E(0,+) [Δ𝑡] = 𝑞
(1 + 2𝜆(𝐿 − 𝑥))𝑤(𝑥)𝑑𝑥
0
𝐿 𝑞 = (𝐿 − 𝑥)𝑤(𝑥)𝑑𝑥 𝑝(𝜑−1 (𝑥))2 𝑑𝑥 + 2𝑞𝜆 2 0 0 = 𝑞𝑇det + 𝑞𝜆𝐵(0,+)
∫︁ 𝐿
∫︁
(6.6)
where we recognize the first term as 𝑞𝑇det by (3.3) and the second term follows from )︃ ∫︁ (︃∫︁ ∫︁ 𝐿
𝐿
𝐿
(𝐿 − 𝑥)𝑤(𝑥)𝑑𝑥 =
2
𝑥
0
0
𝑑𝑦 𝑝(𝜑−1 (𝑥))2 𝑑𝑥
∫︁ 𝑎 (︂∫︁ 𝑎
= −𝑎
𝜃
𝑑𝜉 𝑝(𝜃)𝑑𝜃 = 𝐵(0,+) 𝑝(𝜉) )︂
(6.7)
where 𝑑𝑥/𝑑𝜃 = 𝜑′ (𝜃) = 1/𝑝(𝜃) and similarly 𝑑𝑦/𝑑𝜉 = 1/𝑝(𝜉). The same holds for (𝐿, −).
Proof of Theorem 3.9. We follow the proof in Theorem 3.4. The statement on stationary distribution follows from the fact that the embedded chain has uniform stationary distribution and the expected transition times given in Theorem 3.8. For the hitting times, starting at (0, −), we always transition to (0, +) in expected real time given exactly by E(0,−) [Δ𝑡], so E(0,−) [𝑇hit ] = E(0,+) [𝑇hit ] + E(0,−) [Δ𝑡].
(6.8)
The first-step analysis starting at (0, +) is more complicated: with probability 𝑞 we have the event 𝐸 that next state of 𝑍𝑛 is (𝐿, +). Then, the expected hitting time is the expected time of this transition, i.e. E(0,+) [Δ𝑡|𝐸]. On the complement 19
¯ of 𝐸, the next state is (0, −), in which case the expected additional hitting time 𝐸 is E(0,−) [𝑇hit ]. Together, we have E(0,+) [𝑇hit ] (︁
¯ + E(0,−) [𝑇hit ] = 𝑞E(0,+) [Δ𝑡|𝐸] + (1 − 𝑞) E(0,+) [Δ𝑡|𝐸]
)︁
¯ · E(0,+) [Δ𝑡|𝐸] ¯ = (1 − 𝑞)E(0,−) [𝑇hit ] + P(0,+) (𝐸) · E(0,+) [Δ𝑡|𝐸] + P(0,+) (𝐸) = (1 − 𝑞)E(0,−) [𝑇hit ] + E(0,+) [Δ𝑡].
(6.9)
Solving (6.8) and (6.9) gives the desired. Proof of Theorem 3.2. Combining Theorems 3.5, 3.8 and 3.9, we obtain )︁ 1 (︁ E(0,+) [Δ𝑡] + (1 − 𝑞1{𝑢0 =1} E(0,−) [Δ𝑡] 𝑞 (︂ )︂ 1 1 − 1{𝑢0 =1} E(0,−) [Δ𝑡] = E(0,+) [Δ𝑡] + 𝑞 𝑞
E(0,𝑢0 )[𝑇hit ] =
(︁
= 𝑇det + 𝜆𝐵(0,+) + 1{𝑢0 =−1} + 𝜆𝐿
)︁ ∫︁ 𝑎
(6.10)
𝑝(𝜃)𝑑𝜃
−∞
which is exact Theorem 3.2 upon plugging in 𝐵(0,+) . Proof of Theorem 3.3. Recall that 𝑤(𝑥) = 𝑝(𝜑−1 (𝑥))2 /2. Since 𝑉 is symmetric about 0, so is 𝑝, and so 𝑤 is symmetric about 𝐿/2. Therefore, by (6.7), in 𝑥-space 𝐵(0,+) = 2
∫︁ 𝐿
∫︁ 𝐿
∫︁ 𝐿
(𝐿−𝑥)𝑤(𝐿−𝑥)𝑑𝑥 = 2
(𝐿−𝑥)𝑤(𝑥)𝑑𝑥 = 2
0
0
0
𝑦𝑤(𝑦)𝑑𝑦 = 𝐵(𝐿,−) (6.11)
Moreover, by (3.3) ∫︁ 𝐿
∫︁ 𝐿
𝐵(0,+) + 𝐵(𝐿,−) = 2𝐿
𝑤(𝑥)𝑑𝑥 = 𝐿
𝑝(𝜑−1 (𝑥))2 𝑑𝑥 = 2𝐿𝑇det
0
0
(6.12)
Therefore, 𝐵(0,+) = 𝐵(𝐿,−) = 𝐿𝑇det . Together, by symmetry and (3.3) ∫︁ ∞
E(0,𝑢0 ) [𝑇hit ] = (1 + 𝜆𝐿)𝑇det + (𝜆𝐿 + 1{𝑢0 =−1} )
𝑝(𝜃)𝑑𝜃 𝑎
∫︁ 𝑎
= (1 + 𝜆𝐿) 0
𝑝(𝜃)𝑑𝜃 + (𝜆𝐿 + 1{𝑢0 =−1} )
(6.13)
∫︁ ∞
𝑝(𝜃)𝑑𝜃 𝑎
which simplifies to the desired equation.
6.3
Proof of Results in Section 4.2
Proof of Theorem 4.3. Setting 𝜆 = ℏ𝐸2 as the rescaled energy, the time-independent Schrödinger equation (4.6) becomes −(𝑉 𝜓 ′ )′ = 𝜆𝜓. 20
(6.14)
Define the Liouville transformation under coordinate change 𝑦(Θ) :=
∫︁ Θ 0
𝑑𝜃 . 𝑉 (𝜃)
(6.15)
√︀
From Section 2.4, 𝑉 (𝜃) has super-quadratic tails as |𝜃| → ∞, so the original domain Θ ∈ R gets compactified with this redefinition onto a finite interval (𝑦− , 𝑦+ ). The wavefunction unitarily transforms via √ 𝑢(𝑦) := 𝑉 (Θ(𝑦))1/4 𝜓(Θ(𝑦)), 𝑑Θ = 𝑉 𝑑𝑦 (6.16) such that
∫︁
𝑉
|𝜓(Θ)|2 𝑑Θ =
∫︁ 𝑦+
|𝑢(𝑦)|2 𝑑𝑦.
𝑦−
R
(6.17)
(6.14) then transforms into the Liouville normal form, a standard Schrödinger equation on a bounded interval (𝑦− , 𝑦+ ) −𝑢′′ (𝑦) + 𝑄(𝑦)𝑢(𝑦) = 𝜆𝑢(𝑦),
(6.18)
where 𝑄(𝑦) is an effective potential 1 1 (𝑉 ′ (Θ(𝑦)))2 1 𝑉𝑦𝑦 3 (𝑉𝑦 )2 𝑄(𝑦) = 𝑉 ′′ (Θ(𝑦)) − = − . 4 16 𝑉 (Θ(𝑦)) 4 𝑉 16 𝑉 2
(6.19)
Therefore the resolvent is compact by standard spectral theorem result, so the spectrum of 𝐻 is pure point and discrete. To show semi-boundedness of the spectrum, for any 𝜓 ∈ 𝐶𝑐∞ (R), since 𝑉 (𝑥) > 0 we have ⟨𝜓, 𝐻𝜓⟩ =
∫︁
ibp
𝜓(𝑥)(−ℏ2 𝜕𝑥 (𝑉 (𝑥)𝜓 ′ (𝑥)))𝑑𝑥 = ℏ2
R
∫︁
𝑉 (𝑥)|𝜓 ′ (𝑥)|2 𝑑𝑥 ⩾ 0.
R
(6.20) Using the Friedrichs extension associated with the closed quadratic form 𝑞(𝜓) = ⟨𝜓, 𝐻𝜓⟩ ⩾ 0, we have a Hamiltonian that is self-adjoint and bounded below by 0. Therefore 𝜎(𝐻) ⊂ [0, ∞). Proof of Theorem 4.4. For 𝐸 ⩾ 𝐸𝑐𝑢𝑡 , the WKB eigenstates takes the form of a plane wave ansatz ]︂ [︂ 𝑖 𝜓(Θ) = exp 𝜑(Θ) , (6.21) ℏ where 𝜑(Θ) is a complex phase. Expanding 𝜑 in power series in ℏ up to 𝑂(ℏ), such that 𝜑 = 𝜑0 + ℏ𝜑1 + 𝑂(ℏ2 ), and substituting into (4.6) gives ]︁ [︁ ]︁2 𝑑 [︁ 𝑉 (Θ)(𝜑′0 (Θ) + ℏ𝜑′1 (Θ) + 𝑂(ℏ2 )) −𝑉 (𝑥) 𝜑′0 (Θ) + ℏ𝜑′1 (Θ) + 𝑂(ℏ2 ) +𝐸 = 0 𝑑Θ (6.22) Solving the leading order 𝑂(ℏ0 ) terms of the Schrödinger equation assuming ℏ|𝜑′1 (Θ)| ≪ |𝜑′0 (Θ)| (we state the exact condition at (6.31)) gives the phase
𝑖ℏ
21
contribution √︀ to the eigenstate in terms of an integral of the local momentum 𝑝(Θ) := 𝐸/𝑉 (Θ) 𝜑0 (Θ) = ±
∫︁ Θ
(6.23)
𝑝(𝑥)𝑑𝑥.
Taking 𝜑′0 = ±𝑝(Θ) such that the leading order term vanishes, solving the next order 𝑂(ℏ) terms gives the amplitude of the eigenstate 𝜑1 (Θ) =
𝑖 ln 𝐸𝑉 (Θ) + 𝑐𝑜𝑛𝑠𝑡. 4
(6.24)
Combining both terms and assuming ℏ2 |𝜑′2 (Θ)| ≪ |𝜑′0 (Θ)| so the higher-order phase contribution is asymptotically small (we state the exact condition at (6.32)), we obtain the desired equation. For completeness, we also solve the next order 𝑂(ℏ2 ) terms and present it here1 𝜑2 (Θ) = ∓
∫︁ Θ
[︃
]︃
1 (𝑉 ′ (𝑥))2 1 ′′ 1 √︀ 𝑉 (𝑥) − . 16 𝑉 (𝑥) 2 𝐸𝑉 (𝑥) 4
(6.25)
Interestingly, the numerator of the integrand is exactly the effective quantum potential in the transformed y-space. This confirms the intuition that the next order phase correction to the semiclassical approximation is a purely qantum one. Due to Theorem 4.3, the energy eigenstates of the qECD Hamiltonian are bound states given by a linear combination of the orthogonal traveling-wave solutions )︃ (︃ √ ∫︁ 𝐴 𝐸 Θ 1 √︀ 𝜓𝑊 𝐾𝐵,𝐸 (Θ) = 𝑑𝑥 + 𝑂(ℏ) + 𝜑 . (6.26) sin ℏ Θ0 𝑉 (𝑥) (𝐸𝑉 (Θ))1/4 where 𝐴, 𝜑 are amplitude and phase constants to be determined by normalization and boundary conditions, respectively. The hard wall boundary conditions as enforced by the Friedrichs extension require the wavefunction to vanish at infinity lim 𝜓𝑊 𝐾𝐵,𝐸 (Θ) = 0.
Θ→±∞
(6.27)
This means that the sine functions must be integer multiples of 𝜋 at the boundaries, leading to the quantization rule where 𝑛 = 1, 2, 3, · · · √ (︂ )︂ 𝐸𝑛 𝑛𝜋ℏ 2 𝐿 = 𝑛𝜋, 𝐸𝑛 = . (6.28) ℏ 𝐿 This confirms the Liouville coordinate picture, where the system is effectively a particle in a rigid box of length 𝐿. 𝐴 is a normalization constant such that the wavefunction satisfies ∫︁ ∞ −∞
|𝜓𝑛 (𝑥)|2 𝑑𝑥 = 1.
1
(6.29)
In the WKB eigenstate, this gives the next order contribution to the phase term, scaling as exp{𝑂(ℏ)}.
22
Therefore the wavefunction simplifies to the desired expression √︂
𝜓𝑊 𝐾𝐵,𝑛 (Θ) =
(︃
2 1 𝑛𝜋 sin 1/4 𝐿 𝑉 (Θ) 𝐿
)︃
∫︁ Θ
1 √︀ 𝑑𝑥 + 𝑂(ℏ) . 𝑉 (𝑥) −∞
(6.30)
To the 𝑂(ℏ) order in the phase expansion, the semiclassical approximation holds when the perturbation series for the phase converges rapidly. This requires the following conditions to be satisfied: 1. In solving the leading order terms in the Schrödinger equation, we assumed that ℏ|𝜑′1 (Θ)| ≪ |𝜑′0 (Θ)|. This reduces to ℏ|𝑉 ′ (Θ)| √︀ ≪ 1. 4 𝐸𝑉 (Θ)
(6.31)
Physically, this validity condition means that 𝑉 (Θ) changes slowly over the distance of one local de Broglie wavelength. 2. In dropping higher order corrections to the phase term, we assumed that ℏ2 |𝜑′2 (Θ)| ≪ |𝜑′0 (Θ)|. This reduces to ⃒ ⃒ ℏ ⃒ ⃒
2⃒ 𝑉
′′ (Θ)
4
⃒
𝑉 ′ (Θ)2 ⃒⃒ − ⃒ ≪ 2𝐸. 16𝑉 (Θ) ⃒
(6.32)
Physically, this validity condition means that the second-order phase correction is small compared to the leading-order classical phase contribution. Interestingly, in the Liouville coordinate, this condition implies that the effective quantum Hamiltonian 𝑄(𝑦) is negligible compared to the kinetic term. The WKB condition for qECD can therefore be summarized as (︃
ℏ|𝑉 ′ (Θ)| ℏ2 |𝑉 ′′ (Θ)| , max √︀ 4𝐸 4 𝐸𝑉 (Θ)
)︃
(6.33)
≪ 1.
In this work, we are interested in studying the transition between local minima under the qECD dynamics. To separate low energy from semiclassical physics, we define the semiclassical (WKB) energy cutoff within the region of interest ⃒ ⃒ |𝑉 ′ (𝑥)|2 𝐸𝑐𝑢𝑡 := ℏ max sup , sup ⃒𝑉 ′′ (𝑥)⃒ . 𝑥∈[−2𝑎,2𝑎] 𝑉 (𝑥) 𝑥∈[−2𝑎,2𝑎] {︃
}︃
2
6.4
(6.34)
Proof of Results in Section 4.3
Proof of Theorem 4.5. We start with the discrete spectrum expression for 𝐾ℎ𝑖𝑔ℎ , assuming no degeneracy: 𝐾𝑙𝑜𝑤 (Θ2 , 𝑡; Θ1 , 0) =
∑︁ 𝑛:𝐸𝑛 <𝐸𝑐𝑢𝑡
23
𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝜓𝑛 (Θ2 )𝜓𝑛* (Θ1 ).
(6.35)
By Weyl’s law, we can estimate the number of energy eigenstates below 𝐸𝑐𝑢𝑡 , 𝑁𝑙𝑜𝑤 , via the WKB quantization rule up to an 𝑂(1) error, giving 𝐿 𝑁𝑙𝑜𝑤 = max 2𝜋
⃒ ⃒ |𝑉 ′ (𝑥)|2 sup , sup ⃒𝑉 ′′ (𝑥)⃒ + 𝑂(1). 𝑥∈[−2𝑎,2𝑎] 𝑉 (𝑥) 𝑥∈[−2𝑎,2𝑎] }︃
{︃
(6.36)
Observe that the number of states residing in the non-WKB regime is independent of ℏ at leading order. Assuming the geometric features of the landscape is 𝑂(1) and 𝜓𝑛 have unit norm, we have ⃒ ⃒
⃒ ⃒
𝐾𝑙𝑜𝑤 (Θ2 , 𝑡; Θ1 , 0) ⩽ 𝑁𝑙𝑜𝑤 sup ⃒𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝜓𝑛 (Θ2 )𝜓𝑛* (Θ1 )⃒ = 𝑂(1).
(6.37)
Proof of Theorem 4.6. WLOG, assume Θ2 > Θ1 . We start with the discrete spectrum expression for 𝐾𝑤𝑘𝑏 , assuming no degeneracy: 𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝜓𝑛 (Θ2 )𝜓𝑛* (Θ1 ).
∑︁
𝐾𝑤𝑘𝑏 (Θ2 , 𝑡; Θ1 , 0) =
(6.38)
𝑛:𝐸𝑛 >𝐸𝑐𝑢𝑡
Substituting the WKB wavefunctions derived in Theorem 4.4, we have 𝐾𝑤𝑘𝑏 (Θ2 , 𝑡; Θ1 , 0) =
2 × 𝐿(𝑉 (Θ2 )𝑉 (Θ1 ))1/4
𝑒−𝑖𝐸𝑛 𝑡/ℏ sin
∑︁
(︁√︀
)︁
𝐸𝑛 𝐼(Θ2 ) + 𝑂(ℏ) sin
(︁√︀
)︁
𝐸𝑛 𝐼(Θ1 ) + 𝑂(ℏ) ,
(6.39)
𝑛:𝐸𝑛 >𝐸𝑐𝑢𝑡
where we define the phase constant ∫︁ Θ
𝐼(Θ) := −∞
1 𝑑𝑥. 𝑉 (𝑥)
(6.40)
√︀
We can expand the product of the sine functions 1 𝑖𝑆0 −𝑖𝑆0 𝑖𝑆𝑙 −𝑖𝑆𝑙 exp + exp − exp − exp , 4 ℏ ℏ ℏ ℏ (6.41) where 𝑆0 , 𝑆𝐿 are action-like quantities defined via [︂
]︂
sin(𝜃𝑛 (Θ2 )) sin(𝜃𝑛 (Θ1 )) =
√︀
𝑆0 := ℏ 𝐸𝑛 (𝐼(Θ2 ) − 𝐼(Θ1 )),
√︀
𝑆𝑙 := ℏ 𝐸𝑛 (𝐼(Θ2 ) + 𝐼(Θ1 )).
(6.42)
Physically, 𝑆0 denotes the action of a direct path from Θ1 to Θ2 , while 𝑆𝑙 denotes the action of a path starting from Θ1 going into negative infinity and reflecting back to Θ2 ("left-reflecting"). To extract analytical behavior of this infinite sum, one can utilize the Poisson summation formula ∞ ∑︁ 𝑛:𝐸𝑛 >𝐸𝑐𝑢𝑡
𝑓 (𝑛) =
∞ ∫︁ ∞ ∑︁ 𝑘=−∞ 𝐸𝑐𝑢𝑡
24
(︂
𝑑𝐸
𝑑𝑛 𝑓 (𝑛)𝑒2𝜋𝑖𝑘𝑛 𝑑𝐸 )︂
(6.43)
to rewrite the sum over discrete energy level 𝑛 as an integral over energy 𝐸. The density of state 𝑑𝑛/𝑑𝐸 can be derived from the quantization condition √
𝐿 ⇒ 𝑑𝑛 = √ 𝑑𝐸. 2 𝐸𝜋ℏ
𝐸𝐿 = 𝑛𝜋ℏ
𝑆(𝐸) =
(6.44)
Substituting back to the 𝐾𝑤𝑘𝑏 expression gives 𝐾𝑤𝑘𝑏 (Θ2 , 𝑡; Θ1 , 0) =
∞ ∫︁ ∞ ∑︁
𝑑𝐸
𝑘=−∞ 𝐸𝑐𝑢𝑡
𝑒−𝑖𝐸𝑛 𝑡/ℏ 𝑒𝑖2𝑘𝑆(𝐸)/ℏ √ × 4𝜋ℏ 𝐸(𝑉 (Θ2 )𝑉 (Θ1 ))1/4
𝑖𝑆0 −𝑖𝑆0 𝑖𝑆𝑙 −𝑖𝑆𝑙 . exp + exp − exp − exp ℏ ℏ ℏ ℏ ]︂
[︂
(6.45)
The factor 𝑒−𝑖2𝑘𝑆(𝐸)/ℏ introduced by the Poisson summation formula physically represents the path action accumulated during 𝑘 round trips. The sum over 𝑘 can therefore be interpreted as summing the propagating waves over all winding numbers. For every 𝑘, the four terms represent a full set of topological reflections as follows: 1. 𝑆0 + 2𝑘𝑆 ("direct" path): Θ1 → Θ2 + 𝑘 full round trips 2. −𝑆0 + 2𝑘𝑆 ("left,right-reflected" path): Θ1 → −∞ → +∞ → Θ2 + (𝑘 − 1) full round trips 3. 𝑆𝑙 + 2𝑘𝑆 ("left-reflected" path): Θ1 → −∞ → Θ2 + 𝑘 full round trips 4. −𝑆𝑙 + 2𝑘𝑆 ("right-reflected" path) : Θ1 → +∞ → Θ2 + (𝑘 − 1) full round trips. Therefore we see that the Poisson summation expression indeed sums over all possible paths that the quantum system can take between Θ1 and Θ2 . It is easy to see that every summand in this infinite sum takes the general form ∫︁ ∞
1 𝑖 √ 𝑑𝐸 𝐽𝑝𝑎𝑡ℎ = exp Φ(𝐸) , 1/4 ℏ 4𝜋ℏ 𝐸(𝑉 (Θ2 )𝑉 (Θ1 )) 𝐸𝑐𝑢𝑡 Φ(𝐸) = 𝑆𝑝𝑎𝑡ℎ − 𝐸𝑡. {︂
}︂
(6.46)
The integral can be analyzed via a saddle point expansion Φ′ (𝐸* ) = 0
⇒
𝐸* =
2 𝐼𝑝𝑎𝑡ℎ , 4𝑡2
𝑆𝑝𝑎𝑡ℎ 𝐼𝑝𝑎𝑡ℎ = √ = 𝐸
∫︁ 𝑝𝑎𝑡ℎ
𝑑𝑠 √︀
1 . 𝑉 (𝑠)
(6.47)
It is crucial for the saddle point approximation that 𝐸* > 𝐸𝑐𝑢𝑡 . Recalling the definition of 𝐸𝑐𝑢𝑡 due to the WKB condition, we have 2 𝐼𝑝𝑎𝑡ℎ inf > ℏ2 max 𝑝𝑎𝑡ℎ 4𝑡2
{︃
⃒ ⃒ |𝑉 ′ (𝑥)|2 sup , sup ⃒𝑉 ′′ (𝑥)⃒ 𝑥∈[−2𝑎,2𝑎] 𝑉 (𝑥) 𝑥∈[−2𝑎,2𝑎]
25
}︃
(6.48)
Therefore, it suffices to ensure 𝑡 ⩽ 𝛿𝐼ℏ0 for some 𝛿 > 0 depending only on landscape 𝑉 (and not ℏ). This sets the time scale where this semiclassical analysis remains valid, as stated in the lemma. Assuming that the time scale condition is satisfied, at the saddle point, Φ(𝐸* ) =
2 𝐼𝑝𝑎𝑡ℎ , 4𝑡
2𝑡3 Φ′′ (𝐸* ) = − 2 < 0. 𝐼𝑝𝑎𝑡ℎ
(6.49)
Expanding the integral around the saddle point with 𝐸 = 𝐸* + 𝜖, we can keep terms up to 𝑂(𝜖2 ) in the integrand and perform Gaussian integration to get 2 𝐼𝑝𝑎𝑡ℎ 1 𝜋 𝐽𝑝𝑎𝑡ℎ = √ exp 𝑖 − 1/4 4ℏ𝑡 4 4 𝜋ℏ𝑡(𝑉 (Θ2 )𝑉 (Θ1 ))
{︃ (︃
)︃}︃
(1 + 𝑂(ℏ)).
(6.50)
Note that the amplitude prefactor is independent of 𝑘. To further simplify the summands, observe that ∞ ∑︁
{︂
exp
𝑘=−∞
∞ ∑︁ 𝑖 2 𝑖 𝐼𝑑𝑖𝑟𝑒𝑐𝑡 (𝑘) = exp (𝑆0 + 2𝑘𝑆)2 4ℏ𝑡 4ℏ𝑡 𝑘=−∞
}︂
{︂
∞ ∑︁
}︂
𝑖 2 𝐼 (−𝑘) = exp 4ℏ𝑡 𝑙𝑒𝑓 𝑡,𝑟𝑖𝑔ℎ𝑡 𝑘=−∞ ∞ ∑︁
{︂
exp
𝑘=−∞
{︂
}︂
∞ ∑︁ 𝑖 𝑖 2 𝐼𝑙𝑒𝑓 𝑡 (𝑘) = exp (𝑆𝑙 + 2𝑘𝑆)2 4ℏ𝑡 4ℏ𝑡 𝑘=−∞
}︂
{︂
∞ ∑︁
𝑖 2 = exp 𝐼 (−𝑘) 4ℏ𝑡 𝑟𝑖𝑔ℎ𝑡 𝑘=−∞ {︂
(6.51)
}︂
}︂
(6.52)
Collecting all terms: 𝑒−𝑖𝜋/4 𝐾𝑤𝑘𝑏 (Θ2 , 𝑡; Θ1 , 0) = √ × 2 𝜋ℏ𝑡(𝑉 (Θ2 )𝑉 (Θ1 ))1/4 ∞ ∑︁
[︃
{︃
𝑖(𝐼(Θ2 ) − 𝐼(Θ1 ) + 2𝑘𝐿)2 exp 4ℏ𝑡 𝑘=−∞
}︃
{︃
𝑖(𝐼(Θ2 ) + 𝐼(Θ1 ) + 2𝑘𝐿)2 − exp 4ℏ𝑡
}︃]︃
𝑒−𝑖𝜋/4 = √ × 2 𝜋ℏ𝑡(𝑉 (Θ2 )𝑉 (Θ1 ))1/4 [︃
{︃
}︃
{︃
}︃
]︃
𝑖(𝐼(Θ2 ) − 𝐼(Θ1 ))2 𝑖(𝐼(Θ2 ) + 𝐼(Θ1 ))2 exp 𝜗3 (𝑧− , 𝜏 ) − exp 𝜗3 (𝑧+ , 𝜏 ) , 4ℏ𝑡 4ℏ𝑡 (6.53)
where 𝜗3 (𝑧± , 𝜏 ) are Jacobi Theta functions with 𝑧± =
𝐿(𝐼(Θ2 ) ± 𝐼(Θ1 )) , 2ℏ𝑡 26
𝜏=
𝐿2 . 𝜋ℏ𝑡
(6.54)
We now show that only the 𝑘 = 0 term contributes to the evolution of a physical wave function, to leading order in ℏ. Now, recall from (4.10) that an initial wave function evolves under the Hamiltonian via a spatial integral over the propagator kernel ∫︁ 𝜓(Θ2 , 𝑡) := 𝑑Θ1 𝐾(Θ2 , 𝑡; Θ1 , 0)𝜓0 (Θ1 ). (6.55) For the set up considered in this work, 𝜓0 has zero momentum, so the integral contains fast oscillating terms taking the form ∫︁
{︃
}︃
𝜓(Θ1 ) 𝑖(𝐼(Θ2 ) ± 𝐼(Θ1 ) + 2𝑘𝐿)2 𝑑Θ1 (𝑐𝑜𝑛𝑠𝑡) · exp , 4ℏ𝑡 𝑉 (Θ1 )1/4
(6.56)
where the constant term contains amplitude information of 𝜓0 and 𝐾𝑤𝑘𝑏 . The leading order contribution to this oscillatory integral can be analyzed using a saddle point expansion. The saddle points for these terms, for any fixed 𝑘, take the form 𝐼(Θ*2,𝑘 ) = ±𝐼(Θ1 ) ± 2𝑘𝐿. (6.57) Since 𝐼(Θ) ∈ [0, 𝐿], as discussed in the Liouville transformation section, the only physically permitted saddle point is 𝐼(Θ*2,0 ) = 𝐼(Θ1 ). This saddle point comes from the 𝑘 = 0 direct path term. Every other saddle point lies outside the integration domain, and therefore has negligible contribution to the dynamics of the quantum state. Therefore the effective time-propagator is given by }︃
{︃
𝑖(𝐼(Θ2 ) − 𝐼(Θ1 ))2 𝑒−𝑖𝜋/4 + 𝑂(ℏ) , exp 𝐾𝑤𝑘𝑏 (Θ2 , 𝑡; Θ1 , 0) = √ 4ℏ𝑡 2 𝜋ℏ𝑡(𝑉 (Θ2 )𝑉 (Θ1 ))1/4 (6.58) thus proving the desired time-propagator result. Remark 6.1 (The Continuum Approximation). Remarkably, the requirement that the first saddle point sits above the WKB energy cutoff sets a time scale where the semiclassical physics exhibits identical behavior to a system with a continuous spectrum, as can be seen by examining the 𝑘 = 0, direct path term in the Poisson sum before performing the saddle point expansion. Proof of Theorem 4.8. Starting from (4.10), we substitute the initial Gaussian state defined in (4.3) and the time-propagator derived in Theorem 4.7 to get the time√ evolved quantum state. Let 𝜎 = 𝛼 ℏ, where 𝛼 is an 𝑂(1) initialization constant we can choose. The state at time 𝑡 is ∞ 𝑒−𝑖𝜋/4 1 1 𝜓(Θ, 𝑡) = √ 𝑑Θ′ exp Φ(Θ′ ) 1/4 ′ ℏ (𝑉 (Θ )) 2 𝜋ℏ𝑡(2𝜋𝛼2 ℏ𝑉 (Θ))1/4 −∞ 2 ′ 2 (Θ + 𝑎) 𝐼(Θ , Θ) Φ(Θ′ ) = − +𝑖 . 2 4𝛼 4𝑡
{︂
∫︁
27
}︂
(6.59)
The integrand is a sharp Gaussian envelope with an oscillatory part. The derivatives of the phase are Θ′ + 𝑎 𝑖𝐼(Θ′ , Θ) √︀ − 2𝛼2 2𝑡 𝑉 (Θ) 1 𝑖 𝑖𝐼(Θ′ , Θ)𝑉 ′ (Θ′ ) Φ′′ (Θ) = − 2 + . + 2𝛼 2𝑡𝑉 (Θ′ ) 4𝑡𝑉 (Θ′ )3/2
Φ′ (Θ′ ) = −
(6.60)
The saddle point of this integral can be expressed as an implicit equation 𝑖𝛼2 Θ′* = −𝑎 − √︀ 𝐼(−𝑎, Θ′ ). 𝑡 𝑉 (Θ′* )
(6.61)
The phase function and its second derivative at the saddle point are then 𝛼2 𝐼(−𝑎, Θ)2 𝑖𝐼(−𝑎, Θ)2 + . 4𝑡2 𝑉 (Θ′* ) 4𝑡
(6.62)
1 𝑖 𝛼2 𝐼(−𝑎, Θ)2 𝑉 ′ (Θ′* ) + + . 2𝛼2 2𝑡𝑉 (Θ′* ) 4𝑡2 𝑉 (Θ′* )
(6.63)
Φ(Θ′* ) = Φ′′ (Θ′* ) = −
As ℏ → 0, this integral is overwhelmingly dominated by 𝑂(ℏ) region around the saddle point. Since 𝑉 (Θ) is independent of ℏ, within this effective integration region, 𝑉 (Θ′ )−1/4 = 𝑉 (Θ′𝑥 )−1/4 (1 + 𝑂(ℏ)), (6.64) so we can evaluate the slowly varying amplitude 𝑉 (Θ′ )−1/4 at the saddle point and pull it in front of the integral with 𝑂(ℏ) error. The state at time 𝑡 can therefore be simplified into {︁
}︁
𝑒−𝑖𝜋/4 exp ℏ1 Φ(Θ′* ) 𝜓(Θ, 𝑡) = √ × 2 𝜋ℏ𝑡(2𝜋𝛼2 ℏ𝑉 (Θ)𝑉1 )1/4 }︂ {︂ ∫︁ 1 (4) ′ 1 ′′ ′ ′ ′ 2 ′ ′ 4 ′ Φ (Θ* )(Θ − Θ* ) + Φ (Θ* )(Θ − Θ* ) + · · · , 𝑑Θ exp 2ℏ 24ℏ 𝐶 (6.65) where we integrate over the contour of steepest descent 𝐶 across the complex saddle point Θ′* . Let 𝑥 = Θ′ − Θ′* , the contour integral is dominated by the leading order Gaussian integral, with subleading contribution coming from the quartic term: {︂
∫︁
𝐼𝐶 =
𝑑𝑥 exp 𝐶
√︃
=
1 (4) ′ 4 1 ′′ ′ 2 Φ (Θ* )𝑥 + Φ (Θ* )𝑥 + · · · 2ℏ 24ℏ
}︂
2𝜋ℏ (1 + 𝑂(ℏ)). −Φ′′ (Θ′* )
28
(6.66)
Combining all ingredients, we arrive at the final expression of the quantum state at time t: 𝑒−𝑖𝜋/4 𝜓(Θ, 𝑡) = √ 2 𝜋ℏ𝑡(2𝜋𝛼2 ℏ𝑉 (Θ)𝑉 (Θ′* )1/4
√︃
2𝜋ℏ × −Φ′′ (Θ′* )
{︃ (︃
𝑖 𝛼2 𝐼(−𝑎, Θ)2 𝑖𝐼(−𝑎, Θ)2 exp + ℏ 4𝑡2 𝑉 (Θ′* ) 4𝑡
(6.67)
)︃}︃
[1 + 𝑂(ℏ)].
The probability density of the quantum state is given by 2 {︀ 1 ′ }︀ exp Re Φ(Θ [1 + 𝑂(ℏ)], *) ℏ 2𝑡 2𝜋ℏ𝑉 (Θ)|𝑉 (Θ′* )||Φ′′ (Θ′* )| (6.68) giving the desired result. |𝜓(Θ, 𝑡)|2 =
{︂
}︂
√︀
Proof of Theorem 4.9 and Theorem 4.1. Recall that the instantaneous transition probability is given by ∫︁ 𝑎+𝜎
𝑝𝜎 (𝑡) =
𝑑Θ|𝜓(Θ, 𝑡)|2 .
𝑎−𝜎
(6.69)
√ Since we are integrating around an interval 2𝛼 ℏ that only contributes to higherorder ℏ corrections, the leading-order instantaneous probability density is effectively constant over the integration window, therefore √ 𝑝𝜎 (𝑡) = (2𝛼 ℏ)Θ|𝜓(𝑎, 𝑡)|2 {︂ }︂ (6.70) 2 {︀ 1 ′ }︀ exp Re Φ(Θ ) [1 + 𝑂(ℏ)]. = √︀ * ℏ 𝑡 2𝜋𝑉0 |𝑉 (Θ′* )||Φ′′ (Θ′* )| √ 2 ′ Recall that Im{Θ′* } = − 𝛼√𝐼(Θ* ,Θ) , so at time 𝑂(1/ ℏ) and above, the saddle ′ 𝑡
𝑉 (Θ* )
point becomes asymptotically close to the real axis. We will later confirm that this is indeed the characteristic time scale of the dynamics. At this time scale, we can approximate ⃒ ⃒ ⃒𝑉 (Θ′ )⃒ = 𝑉1 + 𝑂(ℏ), *
{︀
Re
⃒ ′′ ′ ⃒ ⃒Φ (Θ )⃒ = *
1 + 𝑂(ℏ) 2𝛼2
}︀ 𝛼2 𝐼(−𝑎, 𝑎)2 + 𝑂(ℏ). Φ(Θ′* ) = 2𝑡2 𝑉1
(6.71)
The average transition probability is therefore {︃ }︃ √ 2 (︂ )︂ ∫︁ 𝜏 𝑑𝑡 2𝛼 𝛼2 𝐼(−𝑎, 𝑎)2 𝐴 𝐵 √ 𝑝𝜎 (𝜏 ) = exp − 𝑑𝑡 = E1 2 [1 + 𝑂(ℏ)], 2 2ℏ𝑡 𝑉1 2𝜏 𝜏 0 𝜏 𝑡 2𝜋𝑉0 𝑉1 (6.72) ∫︀ ∞ 𝑒−𝑢 where E1 (𝑥) := 𝑥 𝑢 𝑑𝑢 is the exponential integral, and 𝐴, 𝐵 are √ 𝛼2 2 𝛼2 𝐼(−𝑎, 𝑎)2 𝐴= √ , 𝐵= . (6.73) ℏ𝑉1 𝜋𝑉1 𝑉0 29
With a change of variable 𝑥 = 𝐵/𝜏 2 , 𝜏 2𝐵 1 𝐼(−𝑎, 𝑎)2 = [1 + 𝑂(ℏ)] = (𝑐𝑜𝑛𝑠𝑡) · 𝑝𝜎 (𝜏 ) 𝐴 𝑥E1 (𝑥) ℏ
√︃
𝑉0 [1 + 𝑂(ℏ)]. (6.74) 𝑉1
Note that the minimum of 𝑥E11(𝑥) can be reached at 𝑥0 , where 𝑥0 is an 𝒪(ℏ) constant, so we can extract the leading order characteristic time scale up to a constant 𝐼(−𝑎, 𝑎) . 𝜏* = (𝑐𝑜𝑛𝑠𝑡) · √ ℏ𝑉1
(6.75)
√ This 𝒪(1/ ℏ) time scale confirms the vanishing complex shift of the saddle point, and satisfies the limit imposed by (4.13). This proves the desired result in Theorem 4.9. The desired upper bound in Theorem 4.1 is achieved with 𝜏* , with 𝑝𝜎 (𝜏* ) = √ (𝑐𝑜𝑛𝑠𝑡) · 𝐼(−𝑎,𝑎)ℏ √𝑉 to leading order in ℏ. This concludes the quantum hitting 0 time proof.
6.5
Case Study Computations in Section 5
We prove Theorems 5.1 and 5.3 together. By a change of variables, with 𝛿 = 𝑉0 /𝛽 and 𝜃 = 𝑎𝑢, we have (︁ )︁ 𝑉 (𝑎𝑢) = 𝛽 𝛿 + (1 − 𝑢2 )2 (6.76) Therefore, the cases of guessing error correspond to 𝛿 ≲ 1 versus 𝛿 ≳1. We compute integrals √ ∫︁ 𝑎 𝛽 1 √︁ 𝐿= √ 𝛿 + (1 − 𝑢2 )2 𝑑𝑢 (6.77) 𝐸 −1 √ and as 𝑎/ 𝛽 ≍ 1/𝜔, we have √ ∫︁ ∫︁ ∞ 𝑎 𝐸 ∞ 𝑑𝑢 √︀ 𝑝(𝜃)𝑑𝜃 = √ 𝛽 1 𝛿 + (1 − 𝑢2 )2 𝑎 (6.78) √ ∫︁ 𝑎 ∫︁ 𝑎 𝐸 1 𝑑𝑢 √︀ 𝑝(𝜃)𝑑𝜃 = √ 𝛽 0 𝛿 + (1 − 𝑢2 )2 0 Also, note that for 𝐼 defined in (4.2) 𝐼(−𝑎, 𝑎) ≍ 𝐸
−1/2
∫︁ 𝑎
𝑝(𝜃)𝑑𝜃 0
Hence, to compute 𝑇𝑐 and 𝑇𝑞 , it suffices compute the three integrals over 𝑢 above and apply Theorem 3.3 and Theorem 4.1. Proof of Theorem 5.1. Here, 𝛿 ≲ 1. Then, the integral in (6.77) a constant. For the integrals in (6.78), we note a divergence near 𝑢 = 1: let 𝑡 = 𝑢 − 1, then (𝑢2 − 1)2 = (2𝑡 + 𝑡2 )2 ∼ 4𝑡2 for 𝑢 ∈ [0, 2], so ∫︁ 1 0
𝑑𝑢 ≍ 𝛿 + (1 − 𝑢2 )2
√︀
∫︁ 2 1
√︀
𝑑𝑢 ≍ 𝛿 + (1 − 𝑢2 )2 30
∫︁ 𝐶 0
√
(︁ )︁ 𝑑𝑡 ≍ log 𝛿 −1 𝛿 + 4𝑡2
This shoes the second integral in (6.78). For the first one, we split at 𝑢 = 2 and use the equation above as well as ∫︁ ∞ 2
∫︁ ∞
𝑑𝑢 = 𝛿 + (1 − 𝑢2 )2
1
𝑑𝑢 ⩽ 𝛿 + (1 − 𝑢2 )2
∫︁ ∞ 2
3𝑑𝑢 = 𝑂(1) 𝑢2
𝛿 + (𝑢2 − 1)2 ⩾ 𝑢2 − 1 ≳ 𝑢2 /3 for 𝑢 ⩾ 2. Together
since
√︀
√︀
√︀
∫︁ 2 1
)︁ (︁ ∞ 𝑑𝑢 𝑑𝑢 −1 √︀ + ≍ log 𝛿 𝛿 + (1 − 𝑢2 )2 2 𝛿 + (1 − 𝑢2 )2 ∫︁
√︀
so both integrals in (6.78) must be asymptotically log 𝛿 −1 . (︀
)︀
Proof of Theorem 5.3. If 𝛿 ≳ 1, then (1 − 𝑢2 )2 ∈ [0, 1] for 𝑢 ∈ [−1, 1], so ∫︁ 1 √︁
𝛿 + (1 − 𝑢2 )2 𝑑𝑢 ≍
√ 𝛿
−1
and
∫︁ 1 0
√︀
𝑑𝑢 1 √ ≍ 𝛿 + (1 − 𝑢2 )2 𝛿
Now, we split the last integral to bound the denominators and conclude ∫︁ ∞ 1
√︀
𝑑𝑢 = 𝛿 + (1 − 𝑢2 )2
∫︁ 𝛿 1/4 √︀
0
∫︁ 𝛿 1/4
⩽
0
𝑑𝑢 + 𝛿 + (1 − 𝑢2 )2
𝑑𝑢 √ + 𝛿
∫︁ ∞
𝑑𝑢
𝛿 1/4
𝑢2 − 1
∫︁ ∞ 𝛿 1/4
𝑑𝑢 𝛿 + (1 − 𝑢2 )2
√︀
≲ 𝛿 −1/4
and we obtain an asymptotically matching lower bound: ∫︁ ∞ 1
√︀
𝑑𝑢 ⩾ 𝛿 + (1 − 𝑢2 )2
∫︁ 𝛿 1/4 0
∫︁ 𝛿 1/4
≳
0
𝑑𝑢 𝛿 + (1 − 𝑢2 )2
√︀
𝑑𝑢 √ ≳ 𝛿 + 𝑢4
∫︁ 𝛿 1/4 0
𝑑𝑢 √ = 𝛿 −1/4 𝛿
so the tail integral in 𝑢 must be asymptotically 𝛿 −1/4 .
7
Conclusion and Future Directions
Landscape Generalizations. Providing a proof of concept for ECD, we established exponential improvements in expected hitting time over gradient-based baselines on one-dimensional double-well objectives in the under-guessing regime. Extending the analysis to more general objectives with multiple minima, as well as to other guessing regimes corresponding to sign-indefinite potentials, is the focus of forthcoming work. Preliminary results suggest that qECD exhibits robustness with guess 𝐹0 from quantum tunneling effects; a full analysis exceeds the scope of the present paper and is deferred. A further extension to higher-dimensional objectives via Theorems 2.2 and 2.4 is a key direction, as this setting is most relevant for practical applications. 31
Algorithmic Considerations. Beyond dynamical improvements, a complete notion of algorithmic speedup requires analyzing query complexity and overhead, including discretization effects of for example Theorem 2.2 for sECD and query complexity of Hamiltonian simulation in an oracle model; such analyses enables principled resource-matching criteria beyond dynamical time comparisons. In forthcoming work, we also study robustness to initialization via mixing-time analyses. For sECD, mixing time characterizes convergence to a stationary distribution. For qECD, where unitary dynamics do not converge pointwise, we instead analyze convergence of time-averaged distributions to a dephased limit. This framework provides a unified perspective on robustness properties of both ECD dynamics. Acknowledgments We thank Hideo Mabuchi and Eva Silverstein for helpful discussions. Funding YS is funded by the NSF Graduate Research Fellowship and the Stanford Graduate Fellowship. HW acknowledges support from the Stanford QFARM Quantum Science Seed Grant and Knight-Hennessy Scholars. JB acknowledges support from grants NSF-CCF-2403007 and NSF-CCF-2403008.
References [CCD+ 03] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, page 59–68, New York, NY, USA, 2003. Association for Computing Machinery. [DLNSZ25] G Bruno De Luca, Benjamin Nachman, Eva Silverstein, and Henry Zheng. Optimizers for stabilizing likelihood-free inference. Physical Review D, 112(9):092008, 2025. [DLS22]
Giuseppe Bruno De Luca and Eva Silverstein. Born-infeld (bi) for ai: Energy-conserving descent (ecd) for optimization. In International Conference on Machine Learning, pages 4918–4936. PMLR, 2022.
[HLLL19]
Wenqing Hu, Chris Junchi Li, Lei Li, and Jian-Guo Liu. On the diffusion approximation of nonconvex stochastic gradient descent. Annals of Mathematical Sciences and Applications, 4(1):3–32, 2019.
[KB15]
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, ICLR (Poster), 2015. 32
[KLY18]
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima?, 2018.
[LGS23]
G. Bruno De Luca, Alice Gatti, and Eva Silverstein. Improving energy conserving descent for machine learning: Theory and practice, 2023.
[LSL23]
Yizhou Liu, Weijie J Su, and Tongyang Li. On quantum speedups for nonconvex optimization via quantum tunneling walks. Quantum, 7:1030, 2023.
[MZLU22] Takashi Mori, Liu Ziyin, Kangqiao Liu, and Masahito Ueda. Power-law escape rate of SGD. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 15959–15975. PMLR, 17–23 Jul 2022. [SMDH13] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1139–1147, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR. [SSJ23]
Bin Shi, Weijie Su, and Michael I Jordan. On learning rates and schrödinger operators. Journal of Machine Learning Research, 24(379):1–53, 2023.
Yihang Sun Department of Management Science and Engineering, Stanford University
Huaijin Wang Leinweber Institute for Theoretical Physics Stanford University
e-mail: [email protected]
e-mail: [email protected]
Patrick Hayden Google DeepMind Leinweber Institute for Theoretical Physics Stanford University
Jose Blanchet Department of Management Science and Engineering, Stanford University e-mail: [email protected]
e-mail: [email protected]
33