A Quantum-Classical Performance Separation in Nonconvex Optimization

ORAL

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(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.

* We thank Lei Fan for helpful discussions on the empirical study with Gurobi. We also thank Aram Harrow, Alexander Dalzell, Daochen Wang, Jin-Peng Liu, and Shouvanik Chakrabarti for insightful feedback on our work. This work was partially funded by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research in Quantum Computing under Award Number DE-SC0020273, the Air Force Office of Scientific Research under Grant No. FA95502110051, the U.S. National Science Foundation grant CCF-1816695 and CCF-1942837 (CAREER), and a Sloan research fellowship.

–

Publication: Jiaqi Leng, Yufan Zheng, and Xiaodi Wu. "A quantum-classical performance separation in nonconvex optimization". Manuscript in preparation.

Presenters

  • Jiaqi Leng

    University of Maryland, College Park

Authors

  • Jiaqi Leng

    University of Maryland, College Park

  • Yufan Zheng

    University of Maryland, College Park

  • Xiaodi Wu

    University of Maryland, College Park