Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions

We present new theoretical mechanisms for quantum speedup in global optimization of nonconvex functions, expanding quantum advantage beyond tunneling-based explanations. Our main building block is a rigorous correspondence between the spectral properties of Schrödinger operators and the mixing times of classical Langevin diffusion. This motivates a separation: while quantum algorithms operate on the original potential, the classical diffusions correspond to a Schrödinger operator with a WKB potential having nearly degenerate global minima. We formalize these ideas by proving that a real-space adiabatic quantum algorithm (RsAA) achieves provably efficient, polynomial-time optimization for broad families of nonconvex functions. By leveraging novel non-asymptotic semiclassical spectral analysis, we first prove that RsAA optimizes block-separable functions in polynomial runtime, while off-the-shelf classical algorithms require exponential runtimes in general. Next, using advances in intrinsic hypercontractivity of Schrödinger operators, we show RsAA achieves polynomial runtimes on perturbed strongly convex functions lacking global structure, while classical algorithms remain exponentially bottlenecked. In contrast to prior works based on quantum tunneling, these separations do not depend on the geometry of barriers between local minima. Our theoretical claims about classical algorithm runtimes are supported by rigorous analysis and comprehensive numerical benchmarking.