A quantum analogue of convex optimization

Abstract

Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schr\"odinger operator $h=-\Delta +V$ with convex potential $V:{\mathbb{R}}^n\to {\mathbb{R}}_{\ge 0}$ such that $V(x)\to \infty$ as $\Vert x\Vert \to \infty$. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of $h$ up to error $ϵ$ in polynomial time in $n$, $1/ϵ$, and parameters that depend on $V$. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an $n$-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an $n$-dimensional region that is defined by $m$ linear constraints in polynomial time in $n$, $m$, $1/ϵ$ and the radius $R$ of a ball encompassing the region.