Quantum Speedups for Minimax Optimization and Beyond

This paper investigates convex-concave minimax optimization problems where only the function value access is allowed. We introduce a class of Hessian-aware quantum zeroth-order methods that can find the $ϵ$-saddle point within $\tilde{\mathcal{O}}(d^{2/3}{ϵ}^{-2/3})$ function value oracle calls. This represents an improvement of $d^{1/3}{ϵ}^{-1/3}$ over the $\mathcal{O}(d{ϵ}^{-1})$ upper bound of classical zeroth-order methods, where $d$ denotes the problem dimension.

We extend these results to $\mu$-strongly-convex $\mu$-strongly-concave minimax problems using a restart strategy, and show a speedup of $d^{1/3}{\mu }^{-1/3}$ compared to classical zeroth-order methods.

The acceleration achieved by our methods stems from the construction of efficient quantum estimators for the Hessian and the subsequent design of efficient Hessian-aware algorithms. In addition, we apply such ideas to non-convex optimization, leading to a reduction in the query complexity compared to classical methods.