Quantum Global Smooth Nonconvex Optimization under Weak Localization

We develop a fully discrete quantum simulated-annealing framework for global optimization of smooth non-convex functions under a weak localization assumption: a known bounded region contains an ${\epsilon }_{\mathrm{loc}}$-optimal solution of the original problem. This assumption is strictly weaker than the dissipativity conditions commonly imposed in Langevin-based analyses. Unlike continuous-space formulations that defer discretization to implementation, our algorithm is defined end-to-end on a finite discrete space and can be implemented with finite registers using only function and gradient access. We provide an explicit spectral-gap lower bound for the underlying discrete walk, which in turn gives a computable phase-gap guarantee for the quantum walk and makes the resulting complexity fully quantifiable under weak localization. While a polynomial gap cannot be guaranteed uniformly over this broad problem class without additional structural assumptions, we derive an unconditional and computable lower bound that can be supplied directly to the algorithm. This yields a complexity guarantee without requiring stronger structural assumptions. Overall, our framework makes the spectral-gap limitations of weakly localized non-convex optimization explicit while reducing the annealing costs through adaptive temperature selection.