Fetching the paper…
Reading the bibliography…
We explore the potential for quantum speedups in convex optimization using discrete simulations of the Quantum Hamiltonian Descent (QHD) framework, as proposed by Leng et al., and establish the first rigorous query complexity bounds.
Beweis des adiabatensatzes
Max Born and Vladimir Fock · 1928
Earlier work this paper cites.
Some methods of speeding up the convergence of iteration methods
Boris T. Polyak · 1964
Earlier work this paper cites.
II: Fourier analysis, self-adjointness
Michael Reed and Barry Simon · 1975
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate 𝒪 ( 1 / k 2 ) {\cal O}(1/k^{2})
Yurii Nesterov · 1983
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadi Semenovič Nemirovskii and David Borisovich Yudin · 1983
Earlier work this paper cites.
Real and complex analysis
Walter Rudin · 1987
Earlier work this paper cites.
Nonsmooth optimization, 1994
Terry Rockafellar · 1994
Earlier work this paper cites.
Quantum annealing in the transverse Ising model
Tadashi Kadowaki and Hidetoshi Nishimori · 1998
Earlier work this paper cites.
Quantum annealing of a disordered magnet
J. Brooke, David Bitko, Rosenbaum, and Gabriel Aeppli · 1999
Earlier work this paper cites.
On growth of Sobolev norms in linear Schrödinger equations with smooth time dependent potential
Jean Bourgain · 1999
Earlier work this paper cites.
Quantum computation by adiabatic evolution, 2000
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser · 2000
Earlier work this paper cites.
Tunable quantum tunnelling of magnetic domain walls
J. Brooke, T.F. Rosenbaum, and G. Aeppli · 2001
Earlier work this paper cites.
A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda · 2001
Earlier work this paper cites.
How powerful is adiabatic quantum computation?
Wim Van Dam, Michele Mosca, and Umesh Vazirani · 2001
Earlier work this paper cites.
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac Chuang · 2002
Earlier work this paper cites.
Exponential algorithmic speedup by a quantum walk
Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman · 2003
Earlier work this paper cites.
On the generalization ability of on-line learning algorithms
Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile · 2004
Earlier work this paper cites.
The quantum adiabatic optimization algorithm and local minima
Ben W. Reichardt · 2004
Earlier work this paper cites.
Online convex optimization in the bandit setting: gradient descent without a gradient
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan · 2005
Earlier work this paper cites.
Fast quantum algorithm for numerical gradient estimation
Stephen P. Jordan · 2005
Earlier work this paper cites.
Structure-preserving algorithms for ordinary differential equations
Ernst Hairer, Christian Lubich, and Gerhard Wanner · 2006
Earlier work this paper cites.
Filters, mollifiers and the computation of the gibbs phenomenon
Eitan Tadmor · 2007
Earlier work this paper cites.
Adiabatic quantum computation is equivalent to standard quantum computation
Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev · 2008
Earlier work this paper cites.
From quantum to classical molecular dynamics: reduced models and numerical analysis
Christian Lubich · 2008
Earlier work this paper cites.
Quantum algorithm for linear systems of equations
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Earlier work this paper cites.
Robust stochastic approximation approach to stochastic programming
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro · 2009
Earlier work this paper cites.
Optimal algorithms for online convex optimization with multi-point bandit feedback
Alekh Agarwal, Ofer Dekel, and Lin Xiao · 2010
Earlier work this paper cites.
Anderson localization makes adiabatic quantum optimization fail
Boris Altshuler, Hari Krovi, and Jérémie Roland · 2010
Earlier work this paper cites.
Stochastic convex optimization with bandit feedback
Alekh Agarwal, Dean P. Foster, Daniel J. Hsu, Sham M. Kakade, and Alexander Rakhlin · 2011
Earlier work this paper cites.
Functional analysis, Sobolev spaces and partial differential equations
Haim Brezis and Haim Brézis · 2011
Earlier work this paper cites.
Spectral methods: algorithms, analysis and applications
Jie Shen, Tao Tang, and Li-Lian Wang · 2011
Earlier work this paper cites.
Simulating quantum dynamics on a quantum computer
Nathan Wiebe, Dominic W. Berry, Peter Høyer, and Barry C. Sanders · 2011
Earlier work this paper cites.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Sébastien Bubeck and Nicolo Cesa-Bianchi · 2012
Earlier work this paper cites.
Summability of multi-dimensional trigonometric fourier series
Ferenc Weisz · 2012
Earlier work this paper cites.
Trigonometric Fourier series and their conjugates
Levan Zhizhiashvili · 2012
Cited alongside, same era.
Quantum theory for mathematicians
Brian C. Hall · 2013
Cited alongside, same era.
On the complexity of bandit and derivative-free stochastic convex optimization
Ohad Shamir · 2013
Cited alongside, same era.
Adiabatic quantum simulation of quantum chemistry
Ryan Babbush, Peter J. Love, and Alán Aspuru-Guzik · 2014
Cited alongside, same era.
Evidence for quantum annealing with more than one hundred qubits
Sergio Boixo, Troels F. Rønnow, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer · 2014
Cited alongside, same era.
A quantum approximate optimization algorithm, 2014
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Quantum algorithms and lower bounds for convex optimization
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu · 2020
Later among the works it cites.
Mean estimation with sub-gaussian rates in polynomial time
Samuel B Hopkins · 2020
Later among the works it cites.
Convex optimization using quantum oracles
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf · 2020
Later among the works it cites.
Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems
Lucas T. Brady, Christopher L. Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V. Gorshkov · 2021
Later among the works it cites.
Kernel-based methods for bandit convex optimization
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee · 2021
Later among the works it cites.
Quantum-optimal-control-inspired ansatz for variational quantum algorithms
Alexandre Choquette, Agustin Di Paolo, Panagiotis Kl Barkoutsos, David Sénéchal, Ivano Tavernelli, and Alexandre Blais · 2021
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A variational eigenvalue solver on a photonic quantum processor
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’brien · 2014
Cited alongside, same era.
Escaping the local minima via simulated annealing: Optimization of approximately convex functions
Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin · 2015
Cited alongside, same era.
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Optimal rates for zero-order convex optimization: The power of two function evaluations
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono · 2015
Cited alongside, same era.
Saddle-point integration of C ∞ C_{\infty} ”bump” functions, 2015
Steven G. Johnson · 2015
Cited alongside, same era.
Accelerated mirror descent in continuous and discrete time
Walid Krichene, Alexandre Bayen, and Peter L. Bartlett · 2015
Cited alongside, same era.
Later among the works it cites.
High-precision quantum algorithms for partial differential equations
Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander · 2021
Later among the works it cites.
Near-optimal lower bounds for convex optimization for all orders of smoothness
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif · 2021
Later among the works it cites.
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif · 2021
Later among the works it cites.
From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
Alicia B. Magann, Christian Arenz, Matthew D. Grace, Tak-San Ho, Robert L. Kosut, Jarrod R. McClean, Herschel A. Rabitz, and Mohan Sarovar · 2021
Later among the works it cites.
Gate-free state preparation for fast variational quantum eigensolver simulations
Oinam Romesh Meitei, Bryan T Gard, George S Barron, David P Pappas, Sophia E Economou, Edwin Barnes, and Nicholas J Mayhall · 2021
Later among the works it cites.
Implementable tensor methods in unconstrained convex optimization
Yurii Nesterov · 2021
Later among the works it cites.
Lectures on stochastic programming: modeling and theory
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski · 2021
Later among the works it cites.
Optimal control for quantum optimization of closed and open systems
Lorenzo Campos Venuti, Domenico D’Alessandro, and Daniel A. Lidar · 2021
Later among the works it cites.
Quantum algorithms for escaping from saddle points
Chenyi Zhang, Jiaqi Leng, and Tongyang Li · 2021
Later among the works it cites.
Quantum simulation of real-space dynamics
Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang · 2022
Later among the works it cites.
Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits
Tongyang Li and Ruizhe Zhang · 2022
Later among the works it cites.
A quantum central path algorithm for linear optimization
Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tamás Terlaky, and Xiaodi Wu · 2023
Later among the works it cites.
Quantum speedups for zero-sum games via improved dynamic Gibbs sampling
Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian · 2023
Later among the works it cites.
Quantum algorithm for estimating volumes of convex bodies
Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu · 2023
Later among the works it cites.
Quantum algorithms: A survey of applications and end-to-end complexities
Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, et al · 2023
Later among the works it cites.
Randomized gradient-free methods in convex optimization
Alexander V. Gasnikov, Darina Dvinskikh, Pavel Dvurechensky, Eduard Gorbunov, Aleksandr Beznosikov, and Alexander Lobanov · 2023
Later among the works it cites.
Sparse spectral methods for solving high-dimensional and multiscale elliptic pdes, 2023
Craig Gross and Mark Iwen · 2023
Later among the works it cites.
Quantum Hamiltonian Descent, 2023
Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu · 2023
Later among the works it cites.
A quantum-classical performance separation in nonconvex optimization, 2023
Jiaqi Leng, Yufan Zheng, and Xiaodi Wu · 2023
Later among the works it cites.
Quantum speedups for stochastic optimization
Aaron Sidford and Chenyi Zhang · 2023
Later among the works it cites.
Challenges and opportunities in quantum optimization
Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, et al · 2024
Later among the works it cites.
Time-dependent Hamiltonian simulation using discrete-clock constructions
Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee · 2024
Later among the works it cites.
Fast convex optimization with quantum gradient methods
Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, and Marco Pistoia · 2025
Closest in time.
A quantum speed-up for approximating the top eigenvectors of a matrix
Yanlin Chen, András Gilyén, and Ronald de Wolf · 2025
Closest in time.
Exponentially better bounds for quantum optimization via dynamical simulation
Ahmet Burak Catli, Sophia Simon, and Nathan Wiebe · 2025
Closest in time.
(sub) exponential quantum speedup for optimization
Jiaqi Leng, Kewen Wu, Xiaodi Wu, and Yufan Zheng · 2025
Closest in time.
Quantum Hamiltonian Descent for Non-smooth Optimization”, 2025
Jiaqi Leng, Yufan Zheng, Zhiyuan Jia, Chaoyue Zhao, Yuxiang Peng, and Xiaodi Wu · 2025
Closest in time.