Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
Abstract
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 approximately feasible, within Θ(n−3/2) distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real n× n matrix requires at least n/2 matrix-vector product queries. The construction also yields an Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n× n matrix to additive accuracy Θ(n−2). These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an Ω(min{√κ,n}) gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and κ-smooth functions, which is optimal up to a logarithmic factor.
Related
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Optimal Extrapolation Bounds for Sparse Fourier Sums
- Optimal MM* bounds for convex bodies
- Pfaffian Positivity for Convex Kernels and Optimal Matching Bounds
- Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
BibTeX
@misc{augustino2026nearoptimal,
title = {{Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank}},
author = {Brandon Augustino and Shouvanik Chakrabarti and Enrico Fontana and Dylan Herman and Junhyung Lyle Kim and Guneykan Ozgul and Nadezhda Voronova},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.09035},
eprint = {2609.09035},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09035},
}
RIS
TY - UNPB
TI - Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
AU - Brandon Augustino
AU - Shouvanik Chakrabarti
AU - Enrico Fontana
AU - Dylan Herman
AU - Junhyung Lyle Kim
AU - Guneykan Ozgul
AU - Nadezhda Voronova
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.09035
UR - https://arxiv.org/abs/2609.09035
AB - 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 approximately feasible, within Θ(n^−3/2) distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real n× n matrix requires at least n/2 matrix-vector product queries. The construction also yields an Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n× n matrix to additive accuracy Θ(n^−2). These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an Ω(min{√κ,n}) gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and κ-smooth functions, which is optimal up to a logarithmic factor.
ER -