2025/03/21 by Brandon Augustino, Dylan Herman, Augustino, Brandon +11 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Convex function #Convex optimization #FOS: Physical sciences #Gradient descent #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum algorithm #Quantum phase estimation algorithm #Quantum sort #Quantum state #Semidefinite programming #Stochastic Gradient Optimization Techniques #Stochastic gradient descent
paper · pdf · doi:10.48550/arxiv.2503.17356
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.