Dylan Herman

The Sherrington-Kirkpatrick (SK) model serves as a foundational framework for understanding disordered systems. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum optimization algorithm whose performance monotonically improves with its depth $p$. In this work, we introduce a new equivalence between the task of evaluating the energy of QAOA applied to the SK model in the infinite-size limit and the task of simulating a spin-boson system, which we show can be done with modest cost using matrix product states. Using this equivalence, we optimize QAOA parameters and provide numerical evidence that QAOA obtains a $(1-\epsilon)$ approximation to the optimal energy with circuit depth $\mathcal{O}(n/\epsilon^{\infiniteSizeLimitOneOverEta})$ in the average case, with $\varepsilon\lesssim\infiniteSizeLastpError\%$ at $p=\infiniteSizeLastp$. We then use these optimized QAOA parameters to evaluate the QAOA energy for finite-sized instances with up to $30$ qubits and find convergence to the ground state consistent with the infinite-size limit prediction. Our results provide strong numerical evidence that QAOA can efficiently approximate the ground state of the SK model in the average case.

We introduce new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, broadening the scope of quantum advantage beyond traditional tunneling-based explanations. By establishing a rigorous correspondence between the spectral properties of Schrödinger operators and classical Langevin diffusion, we identify regimes where a real-space adiabatic algorithm (RsAA) can significantly outperform classical stochastic gradient-based methods. Leveraging this connection and novel non-asymptotic versions of well-known semi-classical results, we provide polynomial (in the dimension $d$) runtime bounds for RsAA on rotated block-separable functions, and offer theoretical evidence that black-box classical algorithms require exponential time for optimization in these settings, thereby generalizing and formalizing prior work by Leng et al (arXiv:2311.00811). While we can design certain specialized, structure-aware classical algorithms that can efficiently optimize these functions, we further show that the quantum ground state exhibits remarkable robustness to nontrivial perturbations. Leveraging recent advances in the study of the hypercontractivity of Schr\"{o}dinger operators, we construct new families of nonconvex functions for which RsAA achieves polynomial-time optimization, whereas both off-the-shelf and structure-aware classical algorithms incur exponential computational costs. These results provide new insight into quantum-classical separations in nonconvex optimization and highlight tractable and general pathways to advantage in this setting.