Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier RankResearch Paper
A convex body is usually available only through an oracle. In the membership oracle model, an algorithm may ask whether a point lies in a body , given radii with , and it must return a nearly optimal point for a linear objective. Classically this costs a polynomial number of membership queries, and…