Research map / Optimization / Nonconvex and smooth optimization
Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes quantum (sub)gradient estimation from noisy function-evaluation oracles to obtain dimension-independent query complexity for zeroth-order convex optimization in smooth and nonsmooth settings.
Problem
Zeroth-order convex optimization, where only function values are accessible, typically has query complexity that depends on dimension; the paper asks whether quantum methods can remove this dependence.
Approach
Uses quantum (sub)gradient estimation with noisy function evaluation oracles so that zeroth-order methods match the first-order query complexities of classical gradient descent, with no dimension dependence (up to poly-logarithmic factors).
Key results
- Demonstrates the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings.
- Using only noisy function evaluation oracles, matches the first-order query complexities of classical gradient descent.
Surprising findings
- Zeroth-order methods with only noisy function evaluations match first-order gradient descent query complexity.
Experimental setup
Metrics: query complexity
Baselines: classical gradient descent
Closest papers by meaning
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.91)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.89)
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.89)
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.88)
- Quantum Algorithm for Online Exp-concave Optimization (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.