A quantum-classical performance separation in nonconvex optimization
This addresses the challenge of solving hard nonconvex optimization problems for researchers in quantum computing and optimization, showing a potential quantum advantage, though it is incremental as it builds on existing quantum methods.
The paper tackles the problem of nonconvex continuous optimization by identifying a family of instances with many local minima to demonstrate a quantum-classical performance separation, showing that Quantum Hamiltonian Descent solves any d-dimensional instance using O~(d^3) quantum queries and O~(d^4) gates, while classical solvers like Gurobi require super-polynomial time.
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.