Brandon Augustino

This work investigates the possibility of quantum speedups for continuous optimization through quantum Hamiltonian simulation. We establish the first rigorous query complexity bounds for unconstrained convex optimization via a fully-specified instance of digital quantum annealing, based on the non-adiabatic Quantum Hamiltonian Descent (QHD) framework. In the process, we derive the first rigorous resource estimates for digital quantum simulation Schr\"odinger operators that depend only on input simulation parameters, given black-box evaluation access to a separable $G$-Lipschitz potential $b(t)f(x)$. We apply these simulation bounds to assess the complexity of optimization in the high-dimensional regime. Our annealing schedule achieves \emph{arbitrarily fast} convergence rates in the evolution time, with computational time determined solely by the cost of discretization. We show that a $G$-Lipschitz convex function can be optimized to an error of $\epsilon$ with $\widetilde{\Ocal}(d^{1.5} G^2 R^2/\epsilon^2)$ queries, given a starting point that is Euclidean distance $R$ from optimal. Under reasonable assumptions about the query complexity of simulating general Schr\"odinger operators and choice of initial state, we show that $\widetilde{\Omega}(d/\epsilon^2)$ queries are necessary. As a result, QHD does not appear to offer improvements over classical zeroth order methods when $f$ is accessed via exact black-box evaluations. However, we show that the QHD algorithm can tolerate $\widetilde{\Ocal}(\epsilon^3 /d^{1.5} G^2 R^2)$ noise in function evaluation, and as a result, provides a super-quadratic query advantage over the best existing noise-tolerant classical algorithms in the high-dimensional setting. We leverage this to design a quantum algorithm for stochastic convex optimization that offers a super-quadratic speedup over all known classical algorithms in this regime. The algorithms also outperforms existing zeroth-order quantum algorithms for noisy (with the same noise tolerance) and stochastic convex optimization in this setting. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization obtained through a dynamical algorithm.

Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} in general but of great practical importance, and it is valuable to identify algorithmic speedups to expand the domain of problems that can be solved in practice. It has proven challenging to identify super-quadratic quantum speedups for ILPs. A primary difficulty is that most classical algorithms that handle ILPs with many constraints are global and exhaustive, whereas quantum frameworks that offer the potential for super-quadratic speedups leverage the local properties of the objective function and feasible set. We address this difficulty by considering quantum algorithms for Gomory's group relaxation, a relaxation of an ILP that is obtained by removing the nonnegativity constraints from variables that are positive in the optimal solution of the linear programming relaxation, while keeping integrality of the decision variables. We present a classical algorithm that is competitive with known alternatives that solves the group relaxation via a local search, and a corresponding quantum algorithm that under reasonable technical conditions offers a super-quadratic speedup. When the group relaxation satisfies a non-degeneracy condition analogous to (albeit stronger than) that found in linear programming, our approach yields an optimal solution to the original integer program. In other cases, the group relaxation can improve downstream branch-and-cut solvers by reducing the integrality gap, a behavior that we numerically show to be typical for some practically interesting ILPs.