Quantum Glassiness From Efficient Learning

Abstract

We show a relation between quantum learning theory and algorithmic hardness. We use the existence of efficient, local learning algorithms for energy estimation -- such as the classical shadows algorithm -- to prove that finding near-ground states of disordered quantum systems exhibiting a certain topological property is impossible in the average case for Lipschitz quantum algorithms. A corollary of our result is that many standard quantum algorithms fail to find near-ground states of these systems, including time-$T$ Lindbladian dynamics from an arbitrary initial state, time-$T$ quantum annealing, phase estimation to $T$ bits of precision, and depth-$T$ variational quantum algorithms, whenever $T$ is less than some universal constant times the logarithm of the system size. To achieve this, we introduce a generalization of the overlap gap property (OGP) for quantum systems that we call the quantum overlap gap property (QOGP). We prove that preparing low-energy states of systems which exhibit the QOGP is intractable for quantum algorithms whose outputs are stable under perturbations of their inputs. We then prove that the QOGP is satisfied for a sparsified variant of the quantum $p$-spin model, giving the first known algorithmic hardness-of-approximation result for quantum algorithms in finding the ground state of a non-stoquastic, noncommuting quantum system. Inversely, 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.