Limitations of measure-first protocols in quantum machine learning

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.