  In recent works, much progress has been made with regards to so-called
randomized measurement strategies, which include the famous methods of
classical shadows and shadow tomography. In such strategies, unknown quantum
states are first measured (or ``learned''), to obtain classical data that can
be used to later infer (or ``predict'') some desired properties of the quantum
states. Even if the used measurement procedure is fixed, surprisingly,
estimations of an exponential number of vastly different quantities can be
obtained from a polynomial amount of measurement data. This raises the question
of just how powerful ``measure-first'' strategies are, and in particular, if
all quantum machine learning problems can be solved with a measure-first,
analyze-later scheme. This paper explores the potential and limitations of
these measure-first protocols in learning from quantum data. We study a natural
supervised learning setting where quantum states constitute data points, and
the labels stem from an unknown measurement. We examine two types of machine
learning protocols: ``measure-first'' protocols, where all the quantum data is
first measured using a fixed measurement strategy, and ``fully-quantum''
protocols where the measurements are adapted during the training process. Our
main result is a proof of separation. We prove that there exist learning
problems that can be efficiently learned by fully-quantum protocols but which
require exponential resources for measure-first protocols. Moreover, we show
that this separation persists even for quantum data that can be prepared by a
polynomial-time quantum process, such as a polynomially-sized quantum circuit.
Our proofs combine methods from one-way communication complexity and
pseudorandom quantum states. Our result underscores the role of quantum data
processing in machine learning and highlights scenarios where quantum
advantages appear.
