A quantum-classical performance separation in nonconvex optimization
Jiaqi Leng Yufan Zheng Xiaodi Wu
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 $\widetilde{\mathcal{O}}(d^3)$ quantum queries to the function
value and $\widetilde{\mathcal{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.