  We study supervised learning algorithms in which a quantum device is used to
perform a computational subroutine - either for prediction via probability
estimation, or to compute a kernel via estimation of quantum states overlap. We
design implementations of these quantum subroutines using Boson Sampling
architectures in linear optics, supplemented by adaptive measurements. We then
challenge these quantum algorithms by deriving classical simulation algorithms
for the tasks of output probability estimation and overlap estimation. We
obtain different classical simulability regimes for these two computational
tasks in terms of the number of adaptive measurements and input photons. In
both cases, our results set explicit limits to the range of parameters for
which a quantum advantage can be envisaged with adaptive linear optics compared
to classical machine learning algorithms: we show that the number of input
photons and the number of adaptive measurements cannot be simultaneously small
compared to the number of modes. Interestingly, our analysis leaves open the
possibility of a near-term quantum advantage with a single adaptive
measurement.
