Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4

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…