Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent

Yihang Sun; Huaijin Wang; Patrick Hayden; Jose Blanchet

quant-phApr 14, 2026

Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent

Authors: Yihang Sun, Huaijin Wang, Patrick Hayden, Jose Blanchet

Organizations: Department of Management Science and Engineering, Stanford University. · Leinweber Institute for Theoretical Physics, Stanford University. · Leinweber Institute for Theoretical Physics, Stanford University and Google DeepMind.

Abstract

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 in a tractable model where the barrier-crossing mechanism can be computed explicitly. For one-dimensional double-well objectives in the under-guessing regime, we compute the expected dynamical hitting times from a local minimum to the global minimum. We prove that both sECD and qECD exhibit exponential improvements in continuous hitting time relative to their respective gradient-based baselines, stochastic gradient descent (SGD) and quantum tunneling walk (QTW). For objectives with tall barriers, qECD admits a further hitting time improvement over sECD. Mechanistically, ECD sidesteps the exponential cost associated with rare-escape events of SGD from local minima by moving from dissipative to energy-conserving dynamics.

Figures & tables

		Classical	Quantum
Gradient Descent Methods		$\asymp\frac{\sqrt{s}}{a\omega^{3}}\exp(\omega^2a^2/s)$	$\asymp\frac{1}{a\omega^{3/2}\sqrt{h}}\exp(a^2\omega/h)$
Energy Conserving Descent	$V_{0}\gtrsim\beta:$	$\asymp\frac{\lambda_{c}a^{3/2}V_{0}^{1/4}}{\sqrt{\omega}}+\frac{a\sqrt{E}}{\sqrt{V_{0}}}$	$\lesssim\frac{\lambda_{q}a^{2}}{V_{0}}$
Energy Conserving Descent	$V_{0}\lesssim\beta:$	$\asymp\mathopen{}\mathclose{{\left(\lambda_{c}a^{2}+\frac{\sqrt{E}}{\omega}}}\right)\log\mathopen{}\mathclose{{\left(\frac{\beta}{V_{0}}}}\right)$	$\lesssim\frac{\lambda_{q}}{\omega^{2}}\log^{2}\mathopen{}\mathclose{{\left(\frac{\beta}{V_{0}}}}\right)$

Table 1: We study general one-dimensional positive double-well objectives, but instantiate our results to the symmetric case

V(\Theta)={\omega^{2}}(\Theta^{2}-a^{2})^{2}/{8a^{2}}+V_{0}

with

V_{0}>0

. Here,

\beta\coloneqq V(0)=a^{2}\omega^{2}/8

is the barrier height (see figure in Appendix A ). We compare hitting times from local minimum at

-a

to global minimum at

+a

for standard gradient descent methods (SGD Shi et al. (2023) and QTW Liu et al. (2023) ) and for sECD and qECD dynamics. The parameters

s,h,E,\lambda_{c},\lambda_{q}

are tunable in the respective dynamics and treated here as constants. Our results are asymptotic as

\beta\to\infty

Figure 1: Comparison of qECD and sECD hitting times for the symmetric double-well potential with $V_{0}=1$ .

Figure 2: Comparison of qECD and sECD hitting times for the symmetric double-well potential with $V_{0}=10\beta$ .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Symmetric double-well potential in the under-guessing regime.

Symbol	Meaning
$F$	objective function
$F_{0}$	scalar guess for $\min F$
$V=F-F_{0}$	ECD potential
$V_{0}=V(a)$	potential value at the global minimum
$V_{1}=V(-a)$	potential value at the local minimum
$\beta=V(0)$	barrier height in the quartic double well

Appendix

Table 2: Frequently used notation.

Figure 4: Time evolution of the wavefunction probability density under the symmetrical double-well potential, simulated over $x\in[-6,6]$ . The top panel shows the normalized probability density $|\psi(x,t)|^{2}$ for $x\in[-3,3]$ ; red dotted lines mark the location of the wells. The bottom panel shows the corresponding potential $V(x)=2(x^{2}-1)^{2}+0.6$ .

Nonconvex Optimization

Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.

See all 145 papers

Quantum mechanical framework for quantization-based optimization: from Gradient flow to Schroedinger equation
Mar 12, 2026Jinwuk Seok, Changsik ChoHJB Equations Global Optimization
On-Device AIM Research Section AIC Research Lab, ETRI Daejeon, Rep. Korea
Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
Jul 28, 2026Bin Luo, Chengchang Liu, Jonathan Allcock +2Nonconvex Stochastic Optimization Heavy-Tailed Noise
The Chinese University of Hong Kong · Westlake University · Tencent Quantum Laboratory
Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time
Jun 15, 2026Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu +3Hamiltonian Dynamics
Department of Computer Science, Yale University · Department of EECS, Massachusetts Institute of Technology

Mar 12, 2026J/K move · Enter open · S save

Quantum mechanical framework for quantization-based optimization: from Gradient flow to Schroedinger equation

Jinwuk Seok, Changsik Cho

On-Device AIM Research Section AIC Research Lab, ETRI Daejeon, Rep. Korea

HJB Equations Global Optimization Nonconvex Optimization

Open paper AskPDF arXiv

This work presents a quantum mechanical framework for analyzing quantization-based optimization algorithms. The sampling process of the quantization-based search is modeled as a gradient-flow dissipative system, leading to a Hamilton-Jacobi-Bellman (HJB) representation. Through a suitable transformation of the objective function, this formulation yields the Schroedinger equation, which reveals that quantum tunneling enables escape from local minima and guarantees access to the global optimum. By establishing the connection to the Fokker-Planck equation, the framework provides a thermodynamic interpretation of global convergence. Such an analysis between the thermodynamic and the quantum dynamic methodology unifies combinatorial and continuous optimization, and extends naturally to machine learning tasks such as image classification. Numerical experiments demonstrate that quantization-based optimization consistently outperforms conventional algorithms across both combinatorial problems and nonconvex continuous functions.

Abstract

Nonconvex Optimization

Explore similar work

Quantum mechanical framework for quantization-based optimization: from Gradient flow to Schroedinger equation

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time