  Quantum computers are believed to bring computational advantages in
simulating quantum many body systems. However, recent works have shown that
classical machine learning algorithms are able to predict numerous properties
of quantum systems with classical data. Despite various examples of learning
tasks with provable quantum advantages being proposed, they all involve
cryptographic functions and do not represent any physical scenarios encountered
in laboratory settings. In this paper we prove quantum advantages for the
physically relevant task of learning quantum observables from classical
(measured out) data. We consider two types of observables: first we prove a
learning advantage for linear combinations of Pauli strings, then we extend the
result for the broader case of unitarily parametrized observables. For each
type of observable we delineate the boundaries that separate physically
relevant tasks which classical computers can solve using data from quantum
measurements, from those where a quantum computer is still necessary for data
analysis. Our results shed light on the utility of quantum computers for
machine learning problems in the domain of quantum many body physics, thereby
suggesting new directions where quantum learning improvements may emerge.
