



@article {3412,
	title = {A quantum-classical performance separation in nonconvex optimization},
	year = {2023},
	month = {11/1/2023},
	abstract = {<p>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\&tilde;(d3) quantum queries to the function value and O\&tilde;(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.</p>},
	url = {https://arxiv.org/abs/2311.00811},
	author = {Jiaqi Leng and Yufan Zheng and Xiaodi Wu}
}
