Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
This work establishes near-optimal quantum query lower bounds for solving high-accuracy convex optimization problems over explicit families of ellipsoids. By using a novel Fourier rank polynomial method, the authors show that any algorithm requires at least $\Omega(n \log n \log \log n)$ membership queries in the worst case, resolving open questions about quantum speedups in this regime.