Efficient Learning Implies Quantum Glassiness

We show a surprising relation between quantum learning theory and algorithmic hardness. We demonstrate that finding the ground state of certain sparse disordered quantum systems is average-case hard for "Lipschitz" quantum algorithms if there exists an efficient, local learning algorithm---such as the classical shadows algorithm---for estimating the energy of a state of the system. A corollary of our result is that both $O(\log(n))$-depth variational quantum algorithms and $O(\log(n))$-time Lindbladian dynamics fail to find the near-ground state of these systems, matching known bounds for classical disordered systems. To achieve this, we prove that there exists a topological property of certain quantum systems that we call the quantum overlap gap property (QOGP). We then show that systems which exhibit this topological property in their low-energy space exhibit a form of average-case algorithmic hardness. We prove that the QOGP is satisfied for a sparsified variant of the quantum $p$-spin model, giving the first known average-case hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Conversely, we show that the Sachdev--Ye--Kitaev (SYK) model does not exhibit the QOGP, consistent with previous evidence that the model is rapidly mixing at low temperatures.