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

Yihang Sun, Huaijin Wang, Patrick Hayden, Jose Blanchet
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6554-6575, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-sun26a, title = {Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent}, author = {Sun, Yihang and Wang, Huaijin and Hayden, Patrick and Blanchet, Jose}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6554--6575}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/sun26a/sun26a.pdf}, url = {https://proceedings.mlr.press/v337/sun26a.html}, 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.} }
Endnote
%0 Conference Paper %T Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent %A Yihang Sun %A Huaijin Wang %A Patrick Hayden %A Jose Blanchet %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-sun26a %I PMLR %P 6554--6575 %U https://proceedings.mlr.press/v337/sun26a.html %V 337 %X 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.
APA
Sun, Y., Wang, H., Hayden, P. & Blanchet, J.. (2026). Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6554-6575 Available from https://proceedings.mlr.press/v337/sun26a.html.

Related Material