Quantum Glassiness From Efficient Learning

Understand

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).