Research map / Optimization / Nonconvex and smooth optimization
Quantum Algorithms for Non-smooth Non-convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes quantum zeroth-order methods (QGFM and QGFM+) that build quantum gradient estimators of the δ-smoothed surrogate from stochastic function-value oracles, achieving quantum query complexities for finding (δ,ε)-Goldstein stationary points of Lipschitz non-smooth non-convex objectives.
Problem
Finding (δ,ε)-Goldstein stationary points of stochastic Lipschitz, possibly non-smooth and non-convex objectives using only function-value oracles; classical methods are bottlenecked at δ^-1 ε^-3 queries.
Approach
Construct quantum estimators of the gradient of the randomized-smoothing surrogate using O(1) quantum stochastic function-value oracle queries (via quantum sampling oracles and quantum mean estimation), then plug them into a gradient-descent framework and a PAGE-style variance-reduced loop with adaptive variance levels.
Key results
- QGFM achieves query complexity Õ(d^{3/2} δ^{-1} ε^{-3}) for (δ,ε)-Goldstein stationary points using the quantum stochastic function value oracle (Theorem 4.1).
- QGFM+ achieves Õ(d^{3/2} δ^{-1} ε^{-7/3}), beating the classical optimal δ^{-1}ε^{-3} by a factor of ε^{-2/3} (Theorem 4.3).
- QGM+ for smooth stochastic non-convex optimization achieves Õ(√d ε^{-7/3}) quantum stochastic gradient queries, improving Q-SPIDER's Õ(√d ε^{-5/2}) (Theorem G.1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use quantum zeroth-order estimation with QGFM instead of classical GFM | QGFM · (δ,ε)-Goldstein stationary point | query complexity: O(d3/2δ−1ǫ−4) -> ˜O (d3/2δ−1ǫ−3) | Helped |
| use quantum variance reduction with QGFM+ instead of classical GFM+ | QGFM+ · (δ,ε)-Goldstein stationary point | query complexity: O(d3/2δ−1ǫ−3) -> ˜O (d3/2δ−1ǫ−7/3) | Helped |
| use QGFM+ instead of QGFM, adding variance reduction | QGFM · (δ,ε)-Goldstein stationary point | query complexity: ˜O (d3/2δ−1ǫ−3) -> ˜O (d3/2δ−1ǫ−7/3) | Helped |
| use QGFM+ instead of classical OptimalZO | QGFM+ · (δ,ε)-Goldstein stationary point | query complexity: O (dδ−1ǫ−3) -> ˜O (d3/2δ−1ǫ−7/3); ǫ−2/3 | Helped |
| adapt the variance level in QGM+ instead of using Q-SPIDER's fixed variance levels | QGM+ · ε-stationary point, smooth non-convex optimization | query complexity: ˜O(d1/2ǫ−5/2) -> ˜O(d1/2ǫ−7/3); ǫ−1/6 | Helped |
Limitations
- Assumes ideal quantum sampling oracles over the sphere and noise distribution, with idealized circuit sizes (unbounded qubits in the ideal scenario).
- Query complexity still has heavy dimension dependence (d^{3/2}).
- Purely theoretical; no experiments are reported.
Experimental setup
Metrics: query complexity
Baselines: GFM GFM+ OptimalZO Q-SPIDER SPIDER/PAGE
Builds on: GFM (Lin et al.) GFM+ (Chen et al.) PAGE Q-SPIDER (Sidford and Zhang) quantum mean estimation
Closest papers by meaning
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.90)
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.90)
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.90)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.89)
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.86)
- Quantum Algorithm for Online Exp-concave Optimization (ICML 2024 · similarity 0.86)
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.