Quantum speedups for stochastic optimization

2023/08/03 by Aaron Sidford, Chenyi Zhang, Sidford, Aaron +1 · 3 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Optimization and Control (math.OC) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2308.01582

openalex publication_date 2023/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. 2022 and provide a general quantum-variance reduction technique of independent interest.

Cited by

• Isotropic Noise in Stochastic and Quantum Convex Optimization
• Quantum Algorithms for Finite-horizon Markov Decision Processes
• Advancing Quantum State Preparation Using Decision Diagram with Local Invertible Maps

Related

• Quantum Algorithms for Non-smooth Non-convex Optimization
• Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
• Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization
• Fast Convex Optimization with Quantum Gradient Methods