A quantum-classical performance separation in nonconvex optimization

2023/11/01 by Leng, Jiaqi, Zheng, Yufan, Wu, Xiaodi · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2311.00811

Abstract

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 \widetildeO(d³) quantum queries to the function value and \widetildeO(d⁴) 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.

Cited by

• Stochastic Quantum Hamiltonian Descent
• Quantum Optimization via Gradient-Based Hamiltonian Descent

Related

• Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
• Quantum Hamiltonian Descent for Non-smooth Optimization
• On Speedups for Convex Optimization via Quantum Dynamics
• Robustness of Quantum Algorithms for Nonconvex Optimization
• Quantum Optimization via Gradient-Based Hamiltonian Descent