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 ˜ O ( d 2 / 3 ǫ − 2 / 3 ) function value oracle calls. This represents an improvement of d 1 / 3 ǫ − 1 / 3 over the O ( dǫ − 1 ) upper bound of classical zeroth-order methods, where d denotes the problem dimension. We extend these results to µ -strongly- convex µ -strongly-concave minimax problems using a restart strategy, and show a speedup of d 1 / 3 µ − 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.