Title | A quantum-classical performance separation in nonconvex optimization |
Publication Type | Journal Article |
Year of Publication | 2023 |
Authors | Leng, J, Zheng, Y, Wu, X |
Date Published | 11/1/2023 |
Abstract | In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2d 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˜(d3) quantum queries to the function value and O˜(d4) 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. |
URL | https://arxiv.org/abs/2311.00811 |