{"id":"arxiv/2609.09035","url":"https://arxiv.org/abs/2609.09035","tags":["quant-ph","cs.DS","math.OC"],"score":0,"title":"Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank","domain":"quant-ph","source":"arxiv","authors":["Brandon Augustino","Shouvanik Chakrabarti","Enrico Fontana","Dylan Herman","Junhyung Lyle Kim","Guneykan Ozgul","Nadezhda Voronova"],"reviews":0,"subject":"quant-ph","summary":"We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error $Θ(n^{-1/2})$ requires $Ω(n)$ membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}