Eunou Lee (Oct 03 2025).
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ödinger operator
h=−Δ+V with convex potential
V:Rn→R≥0 such that
V(x)→∞ as
∥x∥→∞. 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.