  Quantum machine learning is often highlighted as one of the most promising
practical applications for which quantum computers could provide a
computational advantage. 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 introduce a new class of quantum models where
quantum resources are only required during training, while the deployment of
the trained model is classical. Specifically, the training phase of our models
ends with the generation of a 'shadow model' from which the classical
deployment becomes possible. We prove that: i) this class of models is
universal for classically-deployed quantum machine learning; ii) it does have
restricted learning capacities compared to 'fully quantum' models, but
nonetheless iii) it achieves a provable learning advantage over fully classical
learners, contingent on widely-believed assumptions in complexity theory. These
results provide compelling evidence that quantum machine learning can confer
learning advantages across a substantially broader range of scenarios, where
quantum computers are exclusively employed during the training phase. By
enabling classical deployment, our approach facilitates the implementation of
quantum machine learning models in various practical contexts.
