Quantum lower bounds for convex optimization and real matrix-vector query problems
Abstract
We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of ℝn with evaluation and membership queries is Ω̃(n), nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an n × n real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.
Related
- Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
- Certified bounds on optimization problems in quantum theory
- Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
- Sharp convex body sparse bounds and quantitative matrix weighted estimates for Hilbert transforms along curves
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
BibTeX
@misc{childs2026quantum,
title = {{Quantum lower bounds for convex optimization and real matrix-vector query problems}},
author = {Andrew M. Childs},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.05679},
eprint = {2609.05679},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05679},
}
RIS
TY - UNPB
TI - Quantum lower bounds for convex optimization and real matrix-vector query problems
AU - Andrew M. Childs
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2609.05679
UR - https://arxiv.org/abs/2609.05679
AB - We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of ℝ^n with evaluation and membership queries is Ω̃(n), nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an n × n real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.
ER -