  Quantum machine learning is often highlighted as one of the most promising
uses for a quantum computer to solve practical problems. However, a major
obstacle to the widespread use of quantum machine learning models in practice
is that these models, even once trained, still require access to a quantum
computer in order to be evaluated on new data. To solve this issue, we suggest
that following the training phase of a quantum model, a quantum computer could
be used to generate what we call a classical shadow of this model, i.e., a
classically computable approximation of the learned function. While recent
works already explore this idea and suggest approaches to construct such shadow
models, they also raise the possibility that a completely classical model could
be trained instead, thus circumventing the need for a quantum computer in the
first place. In this work, we take a novel approach to define shadow models
based on the frameworks of quantum linear models and classical shadow
tomography. This approach allows us to show that there exist shadow models
which can solve certain learning tasks that are intractable for fully classical
models, based on widely-believed cryptography assumptions. We also discuss the
(un)likeliness that all quantum models could be shadowfiable, based on common
assumptions in complexity theory.

Quantum Physics;Artificial Intelligence;Machine Learning;Machine Learning