  Classical machine learning (ML) provides a potentially powerful approach to
solving challenging quantum many-body problems in physics and chemistry.
However, the advantages of ML over more traditional methods have not been
firmly established. In this work, we prove that classical ML algorithms can
efficiently predict ground state properties of gapped Hamiltonians in finite
spatial dimensions, after learning from data obtained by measuring other
Hamiltonians in the same quantum phase of matter. In contrast, under widely
accepted complexity theory assumptions, classical algorithms that do not learn
from data cannot achieve the same guarantee. We also prove that classical ML
algorithms can efficiently classify a wide range of quantum phases of matter.
Our arguments are based on the concept of a classical shadow, a succinct
classical description of a many-body quantum state that can be constructed in
feasible quantum experiments and be used to predict many properties of the
state. Extensive numerical experiments corroborate our theoretical results in a
variety of scenarios, including Rydberg atom systems, 2D random Heisenberg
models, symmetry-protected topological phases, and topologically ordered
phases.
