2025 Noether Early Career Scholar Award - Can quantum algorithms bridge the statistical-computational gap in random combinatorial optimization?

Music City Center 

Random combinatorial optimization problems often exhibit statistical-computational gaps in classical regimes. For instance, classical algorithms fail to achieve near-optimal objective values in general q-spin spin-glass models and require significantly higher signal-to-noise ratios to recover the planted signal in spiked-tensor models. One intriguing question is whether quantum algorithms could bridge such statistical-computational gaps. In this talk, we study the Quantum Approximate Optimization Algorithm (QAOA), a general-purpose quantum algorithm for combinatorial optimization. We analyze the performance of constant-depth QAOA on the aforementioned problems that exhibit the classical statistical-computational gaps. Specifically, in the q-spin spin glass models, we characterize the energy levels achieved by QAOA, given by a set of saddle point equations. In the spiked-tensor model, we calculate the asymptotic overlap between the QAOA state and the underlying signal, which exhibits an intriguing sine-Gaussian law. Despite these insights, our findings unfortunately reveal that arbitrary constant-depth QAOA does not surpass classical algorithms in these problems. This suggests that demonstrating the potential quantum advantage of QAOA requires an analysis beyond sub-polynomial algorithmic depth.