Quantum Advantage via Physics-Inspired Methods in Optimization: Empirical and Theoretical Analysis

Abstract

Continuous and combinatorial optimization are foundational to science and engineering. While convex optimization can be usually tackled efficiently, large-scale nonconvex optimization and combinatorial optimization remain a significant challenge for classical computation.Physics-inspired quantum algorithms, such as Quantum Adiabatic Algorithm (QAA) and Quantum Hamiltonian Descent (QHD), offer a promising paradigm for solving these problems by utilizing quantum dynamics to accelerate navigating complex landscapes of objective functions. However, the precise conditions under which these methods provide a provable advantage over state-of-the-art classical algorithms are still largely unexplored. In this thesis, we make progress toward answering this question.

First, we establish the global convergence of QHD for nonsmooth continuous objective functions. We also conduct complementary numerical evaluations to demonstrate that QHD consistently outperforms classical subgradient methods. Second, we present evidence of the scalable quantum advantage by QHD. We construct a family of objective functions with exponentially many local minima and prove that QHD minimizes them in polynomial time. In contrary, a comprehensive empirical study reveals that several off-the-shelf state-of-the-art classical solvers require superpolynomial time to find global minima. Third, we investigate the complexity of Schrödinger operators, since QHD is formulated as real-space Schrödinger dynamics. We prove that simulating time-independent Schrödinger dynamics is BQP-hard and estimating their ground energy is StoqMA-complete under mild technical assumptions. Finally, we present the first provable exponential quantum speedups for QHD and QAA by constructing specific objective functions that require exponentially many classical queries but only polynomial quantum resources. To our best knowledge, these results represent the first rigorous superquadratic speedups for QHD and QAA in optimization. Together, these contributions and technical methods developed advance the understanding of the power of quantum optimization and shed light on how practical quantum advantage might be achieved.