Posted

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=Δ+Vh = -\Delta + V with convex potential V:RnR0V:\mathbb R^n \rightarrow \mathbb R_{\ge 0} such that V(x)V(x)\rightarrow\infty as x\|x\|\rightarrow\infty. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of hh up to error ϵ\epsilon in polynomial time in nn, 1/ϵ1/\epsilon, and parameters that depend on VV. 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 nn-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an nn-dimensional region that is defined by mm linear constraints in polynomial time in nn, mm, 1/ϵ1/\epsilon and the radius RR of a ball encompassing the region.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!