Quantum Algorithms for High-dimensional Convex Optimization

We investigate the potential for quantum speedups in high-dimensional black-box convex optimization. First, we demonstrate that the quantum gradient algorithm can achieve exponential speedups in dimension for zeroth-order convex optimization, while matching known lower bounds on convergence rates. Next, we analyze Quantum Hamiltonian Descent (QHD), a dynamical approach introduced by Lang et al. (2023), which simulates real-space evolution under a kinetic-plus-potential Hamiltonian. We also provide a refined error analysis of the pseudospectral method for real-space quantum simulation (Childs et al. 2022), allowing us to bound the runtime of a digital version of QHD. This result enables us to prove that the dynamical approach offers speedups over all known classical algorithms in certain noisy convex optimization settings, representing, to our knowledge, the first rigorous quantum speedups for convex optimization via a dynamical algorithm. Finally, we discuss potential applications in the financial industry.