A Quantum-Classical Performance Separation in Nonconvex Optimization*

In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2^d local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any d-dimensional instance from this family using O(d^3) quantum queries to the function value and O(d^4) additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.