Abstract

We show a surprising relation between quantum learning theory and algorithmic hardness. We demonstrate that finding near-ground states 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 many standard quantum algorithms fail to find near-ground states of these systems, including short-time Lindbladian dynamics, short-time quantum annealing, phase estimation, and shallow-depth variational quantum algorithms. To achieve this, we introduce a topological property of quantum systems that we call the quantum overlap gap property (QOGP). This property is only satisfied by systems with an efficient local learning algorithm for the energy. We prove that systems which exhibit this topological property in their low-energy space are intractable for quantum algorithms whose outputs are stable under perturbations to 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. Our resulting lower bound for quantum algorithms optimizing this model using Lindbladian evolution matches the best-known time lower bound for classical Langevin dynamics optimizing classical p-spin models. For this reason we suspect that finding ground states of typical quantum p-spin models using quantum algorithms is, in practice, as intractable as the classical p-spin model is for classical algorithms. 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.

Personal information

Eric is a Burke Fellow at Caltech and recently completed his PhD at MIT under the joint supervision of Aram Harrow and Misha Lukin. Much of his research involves studying the limitations of quantum algorithms through the lens of spin glass theory. He also has an interest in quantum foundations theory, including how quantum contextuality can be used as a resource for quantum algorithms.