Researchers have established a new quantum lower bound for high-accuracy convex optimization, resolving an open question in the field. The study focuses on linear optimization over an explicit family of n-dimensional ellipsoids, where the feasible set is accessed via a membership oracle. They showed that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error Θ(n⁻²) requires Ω(n/(log n loglog n)) membership queries. This result holds even if the returned point is only required to be approximately feasible, within Θ(n⁻²) distance from the feasible set. This resolves, up to logarithmic factors, an open question posed in previous works by Chakrabarti et al. (2020) and van Apeldoorn et al. (2020), and tightly characterizes the query complexity of high-accuracy convex optimization up to logarithmic factors.
Year I · No. 112
— Natura non facit saltus —
Wednesday, 9 Sep 2026
NewsPhysics
Physics daily·Since MMXXVI·Morning edition