Limitations of measure-first protocols in quantum machine learning
Authors: Casper Gyurik
Riccardo Molteni
Vedran Dunjko
Venue: ICML 2025 poster (2025)
Keywords: Quantum machine learning
Quantum-classical learning separations
Learning theory
Primary area: theory->learning_theory
TL;DR: We demonstrate a learning separation in a supervised learning task between quantum models that can coherently process quantum inputs and those restricted to classical representations of them.

Abstract: In recent times, there have been major developments in two distinct yet connected domains of quantum information. On the one hand, substantial progress has been made in so-called randomized measurement protocols. Here, a number of properties of unknown quantum states can be deduced from surprisingly few measurement outcomes, using schemes such as classical shadows. On the other hand, significant progress has been made in quantum machine learning. For example, exponential advantages have been proven when the data consists of quantum states and quantum algorithms can coherently measure multiple copies of input states. In this work, we aim to understand the implications and limitations of combining randomized measurement protocols with quantum machine learning, although the implications are broader. Specifically, we investigate quantum machine learning algorithms that, when dealing with quantum data, can either process it entirely using quantum methods or measure the input data through a fixed measurement scheme and utilize the resulting classical information. We prove limitations for the general class of quantum machine learning algorithms that use fixed measurement schemes on the input quantum states.
Our results have several implications. From the perspective of randomized measurement procedures, we show limitations of measure-first protocols in the average case, improving on the state-of-the-art which only focuses on worst-case scenarios. Additionally, previous lower bounds were only known for physically unrealizable states. We improve upon this by employing quantum pseudorandom functions to prove that a learning separation also exists when dealing with physically realizable states, which may be encountered in experiments. From a machine learning perspective, our results are crucial for defining a physically meaningful task that shows fully quantum machine learning processing is not only more efficient but also necessary for solving certain problems. The tasks at hand are also realistic, as the algorithms and proven separations hold when working with efficiently preparable states and remain robust in the presence of measurement and preparation errors.

Limitations of Measure-First Protocols in Quantum Machine Learning
Casper Gyurik 123
Riccardo Molteni 12
Vedran Dunjko 12
Abstract
dorandom functions prove that learning sep- aration also exists when dealing with physically realizable states, which may be encountered in experiments. From a machine learning perspec- tive, our results are crucial for defining a physi- cally meaningful task that shows fully quantum machine learning processing is not only more efficient but also necessary for solving certain problems. The tasks hand also realistic, the algorithms and proven separations hold when working with efficiently preparable states and re- main robust in the presence of measurement and preparation errors.
In recent times, there have been major develop- ments in two distinct yet connected domains of quantum information. On the one hand, substan- tial progress has been made in so-called random- ized measurement protocols. Here, number of properties of unknown quantum states can be de- duced from surprisingly few measurement out- comes, using schemes such as classical shadows. On the other hand, significant progress has been made in quantum machine learning. For exam- ple, exponential advantages have been proven when the data consists of quantum states and quan- tum algorithms can coherently measure multiple copies of input states. In this work, we aim to un- derstand the implications and limitations of com- bining randomized measurement protocols with quantum machine learning, although the impli- cations are broader. Specifically, we investigate quantum machine learning algorithms that, when dealing with quantum data, can either process it entirely using quantum methods measure the input data through fixed measurement scheme and utilize the resulting classical information. We prove limitations for the general class of quantum machine learning algorithms that use fixed mea- surement schemes on the input quantum states. Our results have several implications. From the perspective of randomized measurement proce- dures, we show limitations of measure-firs. proto- cols in the average case, improving on the state- of-the-art which only focuses on worst-case sce- narios. Additionally, previous lower bounds were only known for physically unrealizable states. We improve upon this by employing quantum pscu-
1. Introduction
A central question in quantum machine learning revolves around understanding the various types of advantages one can achieve by exploiting quantum effects. Some of the most interesting scenarios arise when the dataset itself com- prises quantum states, which then be processed fully coherently, or through elaborate measurement strategies. In this context, exponential advantages have been identified when coherent measurements of multiple copies of a given quantum state are allowed (Chen et al., 2022b; Huang et al., 2022; 2020; King et al., 2025; Chen et al., 2024a:b). In parallel related line, there have been significant break- throughs in extracting useful classical information from quantum states using the versatile toolkit of randomized measurements (Elben et al., 2023). This toolkit includes the groundbreaking concept of classical shadows (Huang et al., 2020; 2022), which can extract an efficient classical descrip- tion of quantum states that allows one to compute various physical properties. These two distinct research lines cast doubt on the advantages of quantum machine learning pro- tocols that process quantum data directly compared to those that use fixed measurement procedure, which can also allow for a coherent manipulation of quantum states before the fixed measurement, in order to extract valuable classical data In particular we address the question: is it possible
"applied Quantum algorithms, Leiden University, 2333 CA Leiden, Netherlands 'LIACS, Universiteit Leiden, 2333 CA Leiden, Netherlands 'Pasqal SaS, rue Léonard de Vinci, 91300 Massy, France. Correspondence to: Casper Gyurik <casper.gyurikk pasqal.com>> Riccardo Molteni <r.molteni @liaacaaleeaa Jedenuniii.... Vedran Dunjko <v.dunjko@ liacs ledds.leidenu....122.
'eechicalll, we allow that the processing of the classical data is also done on quantum computer. What is critical for the "measure first" stage is that the data measured first, before the possible quantum processing.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
that a "measure-forst" protocol can be universally used as a substitute for any "fully-quantum" protocol in the general context of machine learning?
Learning problem Concept claes: C [M, xx [0.1)")
Data: T. { (0 mnbnn)]
We formally define what we mean by "measure-fite first"' or a "fully-quantum" protocol in Section (see Definition 2.3 and Definition 2.5), and we provide an overview in Figure 1. Im- portantly, we focus on physically relevant scenarios where the quantum states in the dataset are efficiently preparable, rather than arbitrary unphysical states that do not allow polynomial description in terms of quantum gates.
Measure- first protocols
Fully-quantum protocols
Learning
Deployment
Leurning
Deployment
A
P
M
Tx
p
Fr P
Our main conceptual contribution is to resolve the above question negatively by presenting a concrete machine leamn ing scenario that clearly exhibits the limitations of any measure- first protocol. In a machine learning setup, we construct a task that requires reproducing an undisclosed measurement from the data. This task shows an exponen- tial difference in the number of data needed between fully- quantum protocols and measure-fine first protocols.
Figure I. An overview the quantum machine learning protocols explored in our paper. In both protocols, the quantum algorithm A is tasked with processing training data TN to output a classical description of function h that correctly produces samples 2" for new input states p" (i... It should implement the quantum measurement). The difference between the two protocols is that, in the measure-first protocol, both the input quantum states and those in the training set Tr are subjected to randomized mea- surement strategy M. Consequently, these quantum states p are transformed into a classical representation pz Importantly, this strategy is allowed to depend only on the concept class C (which captures the general learning problem), not on the specific target concept T. E C. In other words, the same randomized measure- ment strategy M is used to preprocess the quantum data for all concepts Tx E C.
Outside of machine learning, certain limitations of measure- first protocols are implied by other works in various tasks such as distributed sampling (Montanaro, 2019) and rela- tional problems (Aaronson et al., 2024). However, these results primarily address separations in worst-case scenarios, which contrasts with the typical focus in machine learning settings where average-case performance is usually suffi- cient. In this paper, we advance these findings by identi- fying the limitations of measure-first protocols that need only achieve average-case correctness for set of efficiently preparable quantum states, i.c. physical states. On a techni- cal level, establishing limitations for measure-first protocols in general quantum machine learning setting necessitates novel techniques beyond those utilized in previous studies. In particular, limitations for the task of predicting properties of quantum states were also recently derived for worst-case settings (Grier et al., 2024) exploiting lower bounds for classical one-way communication complexity. However, this approach inherently limits the focus to states that are not efficiently preparable. This limitation arises because, if states were efficiently preparable, there would be con- cise classical description of their preparation procedure, enabling the transmission of valid classical messages to the recipient. Our main technical contribution lies in exploiting that, from the more general machine learning standpoint, it makes sense to constrain the computational power of the learning protocol. This allows us to additionally impose the requirement that states must be efficiently preparable and still achieve a separation by utilizing a novel construction that combines results on one-way communication complex- ity and pscudorandom quantum states (Brakerski & Shmueli, 2019). The task we consider is also experimentally robust, in the sense that we allow for errors in the preparation of the input quantum states and on the measurement outcomes which label them.
1.1. High-level overview of learning setting and main result
The machine learning problem concerns learning an un- known measurement acting on a set of input quantum states. Specifically, the data that the learning protocol gets consists of pairs of copies of n--ubit quantum states P drawn from some distribution 'D together with a corresponding label 2 E {0, 1) POVM measurement A₂ = {EE | j E (0, 1]"] from some set A = (A2 x E 10.). The remaining n + 1 bits are determined by the outcome of A₂ on the quantum state P. The goal of the machine learning protocol is "learn" how to reproduce the measurement Ag. More precisely, the trained learning protocol has to receive as input an unseen quantum state p' and output sample 2' in agreement with the probability distribution (p) where Tu (p) denotes the distribution of the measurement outcomes of Ag-
The first n bits of 2 encode a -utcome
This paper explores whether solving learning problems such as the above requires quantum computer capable of adap- tive measurements on the training data, or if fixed mea- surement strategy that produces classical representations of the quantum states is sufficient. Specifically, we consider so- called "measure-fiee protocols" that are forced to measure the input states and use the obtained classical description to train the machine learning model to produce samples
2

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
from the target distribution. Importantl, in measure-fins' first protocol the measurements are not allowed to depend on the training data, but are unconstrained otherwise. In particular, the measure- mheasure-first protocol can depend on the set of measure- ments that is to be reproduced from the data, but not on the specific individual measurement hidden within some given training data. On the other hand, we consider so-called "fully-quantum protocols" that can coherently process the quantum states and adjust the measurements based the training data. Our main result is the existence of a learning problem where the quantum data is efficiently generatable on a quantum computer for which a "measure-firs protocol" requires an exponential amount of data to be able to repro- duce measurement outcomes on new input states, whereas a fully-quantum protocol only requires polynomial amount of data. Additionally, we require that the protocols must be efficient in the sense that they run in time polynomial in n. Using the notion of learning we presented above, we now give an informal description of the main result of this paper.
ments on an n-qubit state p up to precision c. It has been shown that this can be done using a number of copies of p that scale polylogarithmically in M, linearly in n, and inverse- polynomially in e (Aaronson, 2018). In contrast to the methods in (Huang et al., 2020), the approach in (Aaron- son, 2018) requires coherent measurements on multiple copies of p. Additionally, as demonstrated in (Huang et al., 2022: Chen et al.. 2022a) for specific tasks, the capacity to coherently measure multiple copies of quantum states provides an exponential advantage in sample complexity over sequential measurements. Considering our framework, where measurements can act coherently on multiple copies of each input state, one might question whether such strate- gies enable a measure-firs protocol to solve our learning task. However, it is important to note that coherent mea- surements do not improve the scaling with respect to the precision leaving room for the possibility of separation since the learning task studied in this paper would require at least exponential precision to be solved.
Theorem 1.1. (Informal) There exist concept class C, where each concept is defined by a measurement and a dis- tribution D over efficiently preparable quantum states such that no "measure-frrs' protocol can learn to reproduce C correctly on average with a polynomial amount of truin- ing data. On the other hand, there exists a ffilly-quantuni " protocol which can learn C efficienctly with respect to both sample and time complexity.
In (Gong & Aaronson, 2023), the authors extended the con- cept of shadow tomography to the scenario of learning a K-outcome POVMs (for K > 2) selected from a set of M unknown quantum measurements. In contrast to the binary outcome case. the goal now is approximate an unknown distribution up to precision in total variation distance, rather than focusing on expectation values. Their procedure requires a number of copies of the quantum state scaling linearly with K and n, polylogarithmically with M, and inverse-polynon polersolllln with the precision e. Moreover, they establish the optimality of this scaling with respect to the dependence on the number of outcomes K. This result prompts the question of whether our separation between measure-first and fully qullt-quantum protocols can be directly inferred from it. However, in establishing their lower bound, it is important to note that no assumptions were made re- garding the complexity of the unknown quantum state. The crux of our study lies in demonstrating that measure-first protocols fall short of reproducing the unknown measure- ment, even on quantum states that are efficiently prepara- ble. Moreover, it is important to highlight that while their shadow tomography procedures can be employed to con- struct a measure- first protocol by "shadowfying" input states to approximate the expected values of each measurement outcome, this is not strictly necessary for our task. Specifi- cally, understanding the probability of each outcome allows for the creation of an "evaluator" that can compute the cor- rect probability for every outcome. However, to resolve our learning problem, a "generator" (i.e., an algorithm generat- ing samples with the correct probabilities) already suffices, and it does not necessarily require computing the output probabilities (Sweke al., 2021).
The specific learning problem which exhibits learning separation is carefully outlined in Section 3 and the precise proofs of Theorem 1.1 can be found in the Appendix.
1.2. Related work
In this section we discuss related works and highlight their relationships to our learning setting. Firstly, in (Huang et al., 2020), the authors introduced a randomized measurement technique tailored to extract a classical description of a quan- tum state p. This description enables the computation of the expectation values of any set of observables {Ox} ) k= provided they have a low "shadow norm", such when the observables are local up to precision of c. Notably, they showed that a number of copies of p, scaling logarithmically with the number of observables M and inverse-poly povere--olyyommilly in the precision c, suffices for this task. As we want to learn the distribution associated of a 2" -outcome POVM with an e error in total variation, directly applying these techniques to estimate each of the 2n outcomes would require an expo- nential precision for each. In their upper bound estimates, this results in the requirement of an exponential number of samples.
The concept of shadow tomography, introduced in (Aaron- son, 2018), revolves around the problem of computing the expectation values of any set of M two-outcome measure-
Next, in (Grier et al., 2024) the authors explore lower bounds on the number of copies of quantum state required for solv-
3

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
ing what they term the "classical shadow" task. This task involves estimating the expected values of observables us- ing teesure-ffrstt approach. While they establish lower bounds on the number of copies of a quantum state required for this task, shedding light on the inherent limitations of measure-first protocols, it is crucial to note two significant bottlenecks their approach when viewed from our more general machine learning perspective. Firstly, their analy- sis only focuses worst-case scenarios, whereas in our machine learning scenarios we are concerned with average- case performance. Secondly, their investigation centers on protocols required to operate effectively even for unphysical quantum states that are not efficiently preparable.
During training the learner is given set of examples Tg where each example consists of a polynomial number of copies of phase state (wr) together with a sample from the associated POVM-induced distribution. This is a spe- cial case of labeled quantum data, which was introduced in (Aïmeur et al., 2006), where we are additionally allowed to have access to polynonially many copies of the input quantum state. We formalize our learning problem by gen- eralizing the standard PAC learning framework (Valiant, 1984). In our generalization, concept corresponds to quantum randomized function, i.e., a function that on each quantum input state outputs a sample from random vari- able (which in our case corresponds to the outcomes of a POVM on the input quantum state). Before we define the concept class studied throughout this paper, we first setup some auxilliary definitions.
The authors of (Cheng et al., 2016) provide upper bounds for the dual problem of shadow tomography, or more specif- ically the problem of learning measurement. In partic- ular, they studied the task of learning an unknown two- outcome POVM denoted { 7 E), from data of the form {P::, Tr( [E):)) They showed that to approximate the unknown E' up to a precision of e on new n-qubit input states, 0(2"/2² training samples are sufficient. Nonethe- less, the number of required samples scales exponentially with the number of qubits.
Definition 2.1 (Auxiliary definitionssnotaation)
Let N 2", or equivalently =log2 N.
We identify function f {0, 1)"" - {0, 1} with its truth table f E {0, and we denote its correspond- ing phase state with
Finally, in (Jerbi et al., 2023) the authors study quantum process learning, where the task is to learn a unitary U, from data of the form (1b4) U [+:)). In particular, they study the limitations of what they call incoherent learning, where the learner constrained to first measure multiple copies of the data U (b4)). While they therefore also study the problem of extracting classical information from quantum data and utilizing it in the learning process, the setting in their work differs from ours. Namely, the quantum states in our scenario are labeled by a sample obtained from the unknown measurement process, whereas in (Jerbi et al., 2023) the labels are the input quantum states when evolved under some unknown target unitary.
Wy)
1 VN
Σ
(11)
(1)
Let Sphase = (1bb 60 / E {0, 13 denote the set
of f poly(n) copies of n-qubit phase states.
We write x ~ π to denote that x was drawn according to a distribution æ.
We write U(X) for the uniform distribution over a set X.
We write (XX) for the set of all distributions over a set Set
For p, E R probability distributions over {0, 1}"
2. Background
we define
In this section, we introduce the notations and definitions needed to frame our main result, which involves a learn- ing problem that demonstrate the separation between any measure-first protocol and a fully quantum protocol.
|lp allrv = 2 ==/0,13"
Σ lpz qzl
to be the total variation distance.
The learning problem we study is the learning of mea- surement. In particular, it involves generating samples from a distribution induced by measuring an (unknown) POYM measurement Ar on n-qubit quantum states. The (unknown) target measurement A₂ is drawn from a set of POVMs (A. x E {0, })"). }. and each measurement A₂ is a computational basis measurement preceded by an n--ubit unitary Uz, i.e.,
Definition 2.2 (Concept class). We define our concept class as C {Tp x E {0, 1)",,, where
Tz : :Sphase + A(10, (100,]2mt))
(2)
where (f) is a distribution over samples (I,y,b) e {0, (0,1]2n+1 where (y.b) E {0, 10,11 are variables sam- pled from a problem-specific distribution characterizing the specific learning task.
A, { F j 1,..., }"}, where F== = U. 15) GiU..
4

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
In particular, T. is randomized function which takes as in- put polynomial number of copies of phase state and outputs sample consisting of
strategy M, and (ii) a learning algorithm A. The main differ- ence between a measure-fint' firstt protocol and fully-quantum protocol is that the former involves randomized measure- ment procedure that first measures the quantum states be- fore putting it into a learning algorithm. Importantly, the measure-firs: protocol is allowed to perform arbitrary co- herent measurements on all input quantum states (i.e., the Eilyoomally-mmny many copies of the phase states). The only constraint is that the measurement strategy cannot depend the specific target concept of the learning problem, al- though it is allowed to depend on the concept class (i.e., the set of all possible target concepts). In short, a random- ized measurement strategy is a polynomial-timg algorithms that maps a polynomial number of copies of phase state (yy) to some classical description wy E {0, 1)m for some m poly(n), These classical descriptions b are then used as input for the learning algorithm, that is tasked with implementing randomized function close to Tg.
{0, 1 together with some (v. b) E {0, 1| sampled from some problem- specific probability distribution. As we will see in the next section, a learning separation for this kind of learning prob- lem achieved by considering (y. b) sampled uniformly from the set of variables which satisfy the Hidden Matching relation defined by the input functions f and the bitstring E {0, 1)"
A learner then is given several evaluations of the randomized function " in the form of training data and its objective is to implement a randomized function Te that closely approx- imates T, on most input states.
In this paper, we compare two categories of machine learn- ing systems that can tackle problems of this type. First, we introduce what we call a "fully-quantunn protocol".
Definition 2.3 (Fully-quantum protocol). A fully-quantuu protocol for the concept class C in Definition 3.1 is a polynomial-time quantum algorithm A that takes as input training data of the form
Definition 2.5 (Measure- ffrrst protocol). A measure-first protocol a tuple (M, A) where
M is a measurement strategy that in time (poly(nn) maps y 1 E Sphase" 2 to some By E {00,1)", where m poly(n).
Tx - ( (1)ro)) Be (c. (1) | (,, ~ TT (1());
(3)
and g ~ 2 ((0.))))) poby(n)
is a polynomial-time quantum algorithm that takes input of the form
i=1
and outputs a classical description of a polynomial-time quantum algorithm that on input ) @f E ESphase generates a sample from a distribution 7e (f) E A[(0, 2n+11) ).
TM x = =FFo (o..,i) (a. ~ Tx (F(())
poly(n)
and f ~ u (10.1).))
We emphasize that for a "fully quantum" protocol, the learn- ing algorithm must produce a classical description of the quantum algorithm generating samples from 7.. Conse- quently, we do not store any quantum states from the train- ing data in quantum memory, which would be more general but not studied in this paper. Ultimately, the goal of the protocol is to implement a randomized function 7e that closely approximates the actual data-gent generating randomized function म. for most of the input quantum states.
(5)
and outputs a description of polynomial-time quan- tum algorithm that on input 1hy M(1p)) 06
generates a sample from a distribution (f) E
Note that the distinction between measure-first and fully- quantum protocols lies in Eq. 5, where the data is mea- sured to give b instead of remaining quantum states (&y)) Nonetheless, the measurements employed by the measure- ment strategy M are completely arbitrary and entirely unre- stricted. We emphasize, however, that the sole constraint on the measurement strategy M is that it must not rely on the specific concepts it will be applied to later, although it can depend on the concept class it is intended for. Recall that the objective of the protocol is to implement randomized func- tion 7. that closely approximates the actual data- tata-generating randomized function T. on most inputs.
Definition 2.4 ((c, 6. Pauce) ) -fulll---uuuulllll quaattum learnable). We say that C is (c. 6, P --fllllllll-atuun learnable if there exists fully qully-quaatum protocol A such that for every Tu E C. with probability at least Pauce we have
Pry Pry-ucto.11)) (l ( T. (.lllV 16)1-1 6- 6, (4)
where #2( E A(f0, A(f0,1)2*+) 1)2 denotes the distribution that the polynomial-time quantum algorithm obtained from
the learning algorithm A generates samples from on input
(wy)) of E Sphase.
Forr completeness, we note here that our results still apply if M is allowed coherently measure multiple input data for different f and then return a polynomial-ste -iize classical representation.
Next, we introduce a "measure-firs protocol" which con- sists of two components: (i) a randomized measurement
5

---

mental setting where the input states ( are affected by preparation errors and they are just close in trace distance Limitations of Mcasure-First Protocols in Quantum Machine Learning
Definition 2.6 ((e, 6, meesur--mass learnable). We say that C is (c, 6. Psncce)--ne -meesse--ase learnable if there exists measure-first protocol (M, A) such that for every Tz E C. with probability at least Pauce we have
Importantly, in (Aaronson al., 2024) the authors showed that for each {0, 1)" there exist POVM measurement Ar which when applied to a phase state (&b) outputs a pair exactly satisfying the relation Ry(x), With regards to our learning problem, the task of the learning protocols is to learn this measurement.
(0,30 (fī=(()) - Txx (fillvr 5021-6 8,
(6)
We now describe how the concept class in Definition 3.1 is fully-quantum learnable.
where (f) E A( 1 denotes the distribution that the polynomial-time time quantum algorithm obtained from the learning algorithm A generates samples from input dby-
Proposition 3.2. The concept class in Definition 3.1 is (0, 0. Iufullly-quantum learnable.
M (1b))) ).
The proof of Proposition 3.2 can be found in Appendix A, and we provide a high-level overview of the fully-quantum protocol here. Firstly, the fully-quantum protocol reads out x from one of the samples generated by T.. in the training data. Next, a quantum circuit denoted as Up is constructed following the procedure outlined in (Aaronson et al., 2024). Measuring Uz (db) in the computational basis results in sample from the distribution 2/( (x)) Crucially, it is worth noting that these quantum circuits Uz are of size O (poly(n)) and can be constructed in time O (poly(n)). We remark here that the concept class in Definition 3.1 re- mains fully quantum learnable even when errors are present in the training data, see Appendix A.
Although we defined the two protocols in an idealized case, we will show in Appendix A. that our separation results are robust. In particular, they still hold even in the experi-
to the ones defined in Eq.( 1). Furthermore, we also allow for measurement errors on the labels (y, b).
3. Main result
In this section, we present the key findings of our paper. In Section 3.1, we define the specific learning problem con- sidered and show how the fully-quantum machine learning model can efficiently solve it. In Section 3.2, we present our first main result showing that no measure-first quantum machine learning model can solve our learning problem effi ciently. Finally, in Section 3.3, we show that this separation between the models still holds if the quantum states in the data are efficiently preparable.
It might seem that little genuine learning occurs when r can be readily read out from single example in Tz. However, we can introduce various levels of learning by providing only partial information about æ within the examples. This partial information should allow the recovery of x from a polynomial number of examples. Several examples illustrat- ing this are discussed in more detail in Appendix A.
3.1. The learning problem
3.2. Limitations of measure-first protocols with general quantum data
In this section, we concretely define the learning problem for which we prove a learning separation. Then, we initiate the proof by showing that is learnable using a fully-quantum protocol.
In the last section, we discussed how the concept class in Definition 3.1 is fully-quantum learnable. Conversely, in this section we discuss the first part of our main result which states that this concept class is not measure- first learnable.
The specific concept class we developed to prove our main result is a particular instance of the one defined in Def. 2.2, with the condition that the variables (y, b) are sampled from the set R. (f) defined as follows:
Theorem 3.3. The concept class in Definition 3.1 is not (e, 5, Psuce) ) -eeasur--frsss learnable for (1-e). > 7/8 and any Psuce 0.
Definition 3.1 (Concept class). C= (Tx x E (0, where
The full proof of Theorem 3.3 is provided in Appendix B, we present a concise overview of the proof here. At its core, the proof hinges on the notion that the existence of a measure-firg protocol for the concept class described in Definition 3.1 implies the existence of an efficient classical one-way communication protocol for the Hidden Matching (HM) problem (Bar-Yossef et al., 2004). Notably, in (Bar- Yossef et al., 2004). it has been shown that the HM problem cannot be solved with a communication cost of O (poly(n)) bits, even on a 7/8 fraction of possible inputs. In essence, if the concept class in Definition 3.1 was learnable, one of the
Wa. Sphase
+ A[10,
(7)
(16)) 00
+ (f)
where (.((f) is a distribution over samples (x., y, b). where (v.b) ~ (x)) and
Ry(x)= (1,bb) E 10, (0,1), f(w) e fovef(yer o x) = b).
6

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
two parties can employ the measurement protocol to encode their input for the HM problem, transmit it to the other party, who can then utilize the learning algorithm A to success- fully solve the HM problem. Intuitively, the reason behind why meesure-first learning fails is that due to (Bar- et al., 2004) it is not possible to compress a phase state ( into a polynomially-sizee classical representation / that contains enough information to allow one to generate samples from the distributions T. (f) for all possible æ. Im- portantly, within the machine learning context, is crucial to also consider the possibility of protocols making errors on fraction of inputs and the requirement to gather the necessary data. To overcome this limitation, we use Yao's principle to show that the existence of a protocol which succeeds in the machine learning context would still violate the classical hardness of the HM problem. In particular, by applying Yao's principle, we can ensure the existence of deterministic algorithm that solves the HM problem on sufficiently large fraction of inputs, provided that there exists machine learning measure-first protocol capable of solving the learning task defined in Definition 2.6.
son al., 2024; Bar- et al., 2004). Our definition of pseudorandom functions is as follows.
Definition 3.4 (Quantum-secure pseudorandom function (QPRF) (Brakerski & Shmueli, 2019)). Let K: = {K₂, hu21 be an efficiently samplable key distribution, and let PRF = {PRFa) PRF, K,, x {0, 1}"" + {0, 1 be an effi- cientl computable function. We say PRF is a quantum- secure pseudorandom function if for every efficient non- uniform quantum algorithm A that can make quantum queries there exists a negligible function negl(.) such that for every n 2 1:
Premz((k).))
[APRF,((0 ==
(9)
P [A'0= 11 S negl(n)
Where the notation A stands for the non-uniform quan- tum algorithm which can make queries to the function f and can take any quantum state as input. We remark that if every function PRF,, admits a classical circuit of size s(n) and depth d(n). then one can prepare the corresponding phase states using a quantum circuit of size (s)))) and depth d(nn) + (Brakerski & Shmueli, 2019). Moreover, the existence of such PRF,, n, is implied by the existence of quantum secure one-way functions (Zhandry, 2012).
Since in our machine learning setting we are concerned with physical states appearing in the real-world, in the next sec- tion we show that our findings also apply to settings where states are efficiently preparable, which we achieve by us- ing pscudorandom states (Brakerski & Shmueli, 2019) (see Section 3.3). Finally, it is crucial to note that even when the data in Eq.( 5) is derived from polynomial number of copies of each input state ( measure-first protocols remain incapable of solving the task. This holds true even when considering inefficient (i (i.e., superpolynomial-tinn -ime ) algorithms an exponential number of training points, as the communication complexity bounds still apply regard- less of the time resources utilized by the algorithms (since the communication protocol assumes both parties have un- bounded resources).
3.3.1. FULLY-QUANTUM LEARNABILITY WITH PSEUDORANDOM PIASE STATES
Note that when we constrain the inputs of n. to phase states of pseudorandom functions, we essentially modify the dis- tribution over input states in Eq. and Eq. 6. This new distribution now only has support on phase states that are efficiently preparable. While Proposition 3.2 examines gen- eral quantum phase states as input states (which are not typi- cally efficiently preparable), we note that the fully-quantum learnability directly extends the setting where we limit our- selves to efficiently preparable phase states as well. We summarize this observation in the following proposition (whose proof is the same as that of Proposition 3.2).
3.3. Learning separation with efficiently preparable quantum data
From a pragmatic perspective, a crucial limitation of the learning problem outlined in the previous section is that preparing a general phase state is intractable (i.e., not re- alized by polynomial-te
Proposition 3.5. Let Spc PRF, (k;, k E KC), where PRF is quantum- pseu- dorandom function functtion with keys K. The concept class in Def- inition 3.1 is (0,0, 1)-fully- quuunty-quantum learnable when the distribution over input states is uniform over Spr.
(1)y oz I ((0)())
processes). In particular, this raises the question of whether separations could persist for states that are prepared by (natural or artificial) polynomial- time processes. To address this limitation, we show that the concept class in Definition 7 remains not measure- first learnable, even when we constrain the input of the random functions n. to phase states of so-called pseudorandom func- tions. Notably, phase states corresponding to appropriately chosen pseudorandom functions can be efficiently prepared. Because of this additional consideration, separations are notably more general than those in previous works (Aaron-
3.3.2. LIMITATIONS OF MEASURE-FIRE PROTOCOLS WITH PSEUDORANDOM PHASE STATES
In the last section, we discussed how the concept class in Definition 3.1 remains fully-quantum learnable when re- stricted to phase states of pseudorandom functions. Con- versely, in this section we show that this concept class also
7

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
remains not measure-first learnable when restricted to phase states of pseudorandom functions.
vided an example of a learning problem efficiently solved by a fully-quantum protocol but beyond the capabilities of measure-first protocols. Moreover, we showed that this persists even when we limit from universal quantum states, which include also those intractable to prepare, to efficiently preparable quantum states. These findings underscore the crucial role of processing unmeasured quantum data in ma- chine learning, presenting a setting where quantum advan- tages arise. In particular, they imply that certain learning tasks inherently require the "exponential capacity" of quan- tum states, distinct from classical data. In other words, the number of bits needed to store n qubits, in way that allows a learner to successfully solve the learning problem, is expo- nential n. Such a conclusion is analogous to what Monta- naro refers as "anti-Holevo" theorems (Montanaro, 2019). While our proof relies on both separations in one-way com- munication complexity and pseudorandom states, high- light the potential for more general constructions. Instead of considering states demonstrating a one-way communica- tion complexity separation, any quantum advice state used in quantum advice complexity classes that cannot be clas- sically simulated with polynomial overhead could suffice, leveraging the separation between the classes FBQPP/q /qpoly and FBQP PeQP/poly showed in (Aaronson et al., 2024). In par- ticular, by the result in (Aaronson & Drucker, 2010) any problem that can be efficiently solved with a polynomial- sized quantum advice state can also be solved with an advice state that is the ground state of a local Hamiltonian. This suggests that learning problems where the input quantum data consists of ground states of sufficiently complex local Hamiltonians are promising candidates for demonstrating separation between measure-first and fully- fully-quantum pro- tocols. Finally, we note that beyond pseudorandom states one could use so-called "computationally indistinguishable" states, which are known to exist assuming the intractability of the graph isoorpphssm problem (Kawachi et al., 2012), or various other complexity theoretic assumptions (Brakerski et al., 2022).
Theorem 3.6. Let Spr = (1)) ,RF,, .), k E K.,, where PRF is a quantum- pseu- dorandom function with keys K. The concept class in Def- inition 3./ is not (c, 5, Psuce) maees-----uuefeie learnable for (1- (1 8) Panee > for any constant с >> 7/88 when the distribution over input states is uniform over Spr.
(()))) =
The main results of this section directly follows from com- bining Theorem 3.6 and Proposition 3.5.
Corollary 3.7 (informal). If there exist quantum--ecure pseudorandom lonnomfffiiiii functions, then there exists a quantum super- vised learning problem with efficiently generatable quantum data, which cannot be learned by any measure-fin first proto- col according to Def. 2.6 while there exist a qull-qqunnunn protocol which satisfies the learning condition of Def. 2.4
The proof of Theorem 3.6 is provided in Appendix C, and we first present a concise overview of the proof here. The main idea behind the proof is to illustrate that if the concepts are measure-fire first learnable when restricted to pseudorandom phase states, then the corresponding measure- ffrrtt learning protocol can be harnessed to create a non-uniform quantum algorithm that is able to distinguish between truly random functions and pseudorandom functions. More precisely, this "distinguisher" algorithm employs the measure-fine learning protocol and evaluates its performance when applied to the phase state corresponding to the function it has been given oracular access to. In the proof of Theorem 3.3, we estab- lished an upper bound on the generalization performance of any measure-first protocol for truly random phase states. If, however, the measure-first protocol performs well on pseudorandom phase states, then the outcomes of the "dis- tinguisher" algorithm would differ significantly based on whether it is given oracular access to a truly random or a pseudorandom function, thereby contradicting the pseudo- randomness assumption. In other words, if the measure- first protocols were effective on pseudorandom states, there would be a clear difference in the performance of the dis- tinguisher: poor accuracy when dealing with truly random functions and strong accuracy when dealing with pscudo- random functions. However, since this would violate Eq. 9, measure-fins first protocols have to fail when applied to pseudo- random functions.
A Akknowledgements
VD and CG acknowledge the support of the Dutch Research Council (NWO/ OCW), as part ofthe Quantum Software Consortium programme (project number 024.003.037). This work was supported by the Dutch National Growth Fund (NGF), as part of the Quantum Delta NL programme. This publication is also part of the project Divide & Quantum (with project number (389.20.241) of the research pro- gramme NWA-ORC which is (partly) financed by the Dutch Research Council (NWO).
4. Conclusion
In our study, we explored the constraints and capabilities of learning from quantum data. We established formal machine learning framework that contrasts two protocols: "fully quantum", which adjusts measurements based on data, and "mmasurrefirse" restricted by fixed initial (though ar- bitrarily powerful) measurements. In particular, we pro-
8

---

Limitations of Mcasure-Firsl Protocols in Quantum Machine Learning
Impact Statement
Chen, S., Gong, W., and Ye, Q. Optimal tradeoffs for estimating pauli observables. In 2024 IEEE 65th Annual Symposium Foundations of Computer Science (FOCS), pp. 1086-1105. IEEE, 2024a.
This paper presents work whose goal is to advance the field of Quantum Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, S., Gong, W. and Zhang, Z. Adaptivity can help exponentially for shadow tomography. arXiv preprint arXiv:2412.1902,, 2024b.
References
Aaronson, S. Shadow tomography of quantum states. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pp. 325-338, 2018.
Cheng, H.-C., Hsieh, M.-H., and Yeh, P.-C. The learnabil- ity of unknown quantum measurements. Quantum Info. Comput., 16(7-8):615 656, May 2016. ISSN 1533-7146.
Aaronson, S. and Drucker, A. full characterization of quantum advice. In Proceedings of the forty-second ACM symposium Theory of computing, pp. 131-140, 2010.
Elben, A., Flammia, S. T., Huang, H.-Y., Kueng, R., Preskill, J., Vermersch, B., and Zoller, P. The randomized mea- surement toolbox. Nature Reviews Physics, 5, 2023.
Aaronson, S., Buhrman, H., and Kretschmer, W. A Qubit, Coin, and an Advice String Walk into a Relational Prob- lem. In Guruswami, V. (ed.), 15th Innovations in Theoret- ical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 1:1-1:24, Dagstuhl, Germany, 2024. Schloss Dagstuhl Lee--eiiiiieeeruu für Informatik. ISBN 978- 3-95977-309-6. doi: (0.4230/LIPlcs.TTCS...o 2024.. URL https: //ropss///ppp//o dagstuhl de/entities) document/10, 10..4/330////// Dccomment/....23/IIIIc.... ITCS. 2024..1.
Gong, W. and Aaronson, S. Learning distributions over quantum measurement outcomes. In International Con- ference on Machine Learning, pp. 11598-11613. PMLR, 2023.
Grier, D., Pashayan, H. and Schaeffer, L. Sample- optimal classical shadows for pure states. Quantum, 8: 1373, June 2024. ISSN 2521-327X. doi: 10.22331/ q- 22024-06-17-1327 URL https: /ttp///oiiioo org/10.
Aimeur, E., Brassard, G., and Gambs, S. Machine learning in a quantum world. In Proceedings of the Advances in Artificial Intelligence: 19th Conference of the Canadian Society for Computational Studies of Intelligence, pp. 431 442. Springer, 2006.
Huang, H.- Y., Kueng, R., and Preskill, J. Predicting many properties of quantum system from very few measure- ments. Nature Physics, 16, 2020.
Huang, H.-Y., Kueng, R., Torlai, G., Albert, V. V., and Preskill, J. Provably efficient machine learning for quan- tum many-body problems. Science, 377, 2022.
Bar- Yossef, Z., Jayram, T. S., and Kerenidis, Exponential separation of quantum and classical one-way communica- tion complexity. In Proceedings of the thirty-sixth annual ACM symposium Theory of computing, 2004.
Jerbi, S., Gibbs, J., Rudolph, M. S., Caro, M. C., Coles, P. J., Huang, H.-Y., and Holmes, Z. The power and limitations of learning quantum dynamics incoherently. arXiv:2303 14
Brakerski, Z. and Shmueli, O. (pseudo) random quantum states with binary phase. In Theory of Cryptography Conference. Springer, 2019.
Kawachi, A., Koshiba, T., Nishimura, H., and Yamakami, T. Computational indistinguishability between quantum states and its cryptographic application. Journal of cryp- tology, 25:528 -5088 2012.
Brakerski, Z.,
Canetti, R., and Qian, L. On the computa- tional hardness needed for quantum cryptography. arXiv preprint ar arXiv:2209. 222200904410. 04101, 2022.
King, R., Gosset, D., Kothari, R., and Babbush, R. Triply efficient shadow tomography. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 914-946. SIAM. 2025.
Chen, S., Cotler, J., Huang, H.-Y., and Li, J. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 574-585. IEEE, 2022a.
Liu, Y., Arunachalam, S., and Temme, K. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 2021.
Chen, S., Cotler, J., Huang, H.-Y., and Li, J. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022b.
Montanaro, A. Quantum states cannot be transmitted effi- ciently classically, Quantum, 2019.

---

Limitations of Measure-Firsl Protocols in Quantum Machine Learning
Nielsen, M. A. and Chuang, I. L. Quantum compulation and quantum information. Cambridge university press, 2010.
Sweke, R., Seifert, J.-P., Hangleiter, D., and Eisert, On the quantum versus classical learnability of discrete dis- tributions. Quantum, 5:417, 2021.
Valiant, L. G. theory of the learnable. Communications the ACM, 27(11):1134-1144 1142,, 1984.
Zhandry, M. How to construct quantum random functions. In 2012 IEEE 53rd Anmual Symposium on Foundations of Computer Science. IEEE, 2012.
10

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
A. Proof of Proposition 3.2
Proposition 3.2. The concept class Definition 3.1 is (0, O, 1)ffully-qquatuum learnable.
Proof. To prove that the concept class C in Definition 3.1 is fully-quantum learnable we will provide a fully-quantum protocol A that does so successfully. Suppose we are given training data T2 of the form provided in Eq. 3. Firstly, the fully-quantum protocol A reads out æ from one of the examples in Tz. Next, uses the construction of (Aaronson et al., 2024) to construct circuit U2 of size (nn) in time ((n) such that when measuring the state ( U2 k in the computational basis it produces (y₂ {0, 1]m+1 such that b [vv) e [(x + y). The operator Uz. whose graphical representation is provided in Figure 3 of (Aaronson al., 2024), is defined as follows. Consider
{0, 1) with
Hamming weight of k 2 1. The operator Ua acts on qubits based on the values of the entries of as follows:
1. A position is selected such that x; 1. The corresponding qubit i then chosen to output the value of b E {0,
2. For each of the remaining positions j where z; 1 and j ن i, CNOT gate is applied with qubit j as the control and qubit i as the target. This results in a total of l: - 1 CNOT gates.
3. Finally, a Hadamard gate is applied to qubit i.
Measuring the resulting state Ur w in the computational basis yields n-bit string ji, such that the variables j1, Jn-1 and 6 = jn² are guaranteed to satisfy the relation b = fly) @ f(x @ y).
The learning protocol outputs the description of the POVM measurement
I = UU> 15) (1 j (0.
(10)
as by the above measuring IT on an arbitrary phase state (xby) implements T. with zero error.
While it may appear that little learning is occurring when we can readily extract æ from a single example in T,. we can introduce varying degrees of learning by not appending the complete description of x to the examples. Instead, we include only partial information about x that still allow us to recover a full description of using a polynomial number of examples. For instance, instead of appending x the examples we can append certain functions (x)),, where ge is drawn uniformly random from some of {gi her. For instance, for E {0, 1)" we can consider functions like
(x) (i x. e 10,1)**1
(11)
where z Σý Dz in mod 2. Another example of such a family of functions would be
(x) xx) = (DLP(z),, e 13+
(12)
where (LP:(z) denotes the ith bit of the discrete logarithm of x in a suitably chosen group. For these functions, one can show that can be recovered with high probability from a polynomial number of evaluations of gi (x)) for randomly chosen ge from G. Moreover, functions similar the gi in Eq. 12 require a quantum computer be able efficiently recover (Liu et al., 2021).
A.I. Learnability with noisy data
In realistic setting, quantum states and measurements will always be affected with experimental errors. In this section we study whether the fully-quantum protocol still manages to solve the learning task even in non ideal scenarios.
We specifically address the scenario where the input states are not exactly the phase states (bby) from Eq.( 1) but are instead approximate states (ely).,, in trace distance, such that:
d(wb)) (15)) S Eap
(13)
'Without loss of generality, we assume the qubit in the above construction to he at the positon i n.

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
where d((v))) 11y c..) - (1 (yyl-wyy) Wyyl.. || is the trace distance between the states (&by and (
As mentioned before, we also allow for measurement errors on the training labels. Specifically we can consider the case that the labels (y. b) in the training data follow an approximate distribution TT (f) which is only close to the ideal one in total variation distance:
vf E {0, 1
| (f) Txe (f)lTV S EM
(14)
Note that only the two variables (y, b) are affected by measurement errors, while the variable x, which labels each concept, not affected by any error.
Even with both of the above sources of experimental enror, the learning problem in Def. 3.1 remains fully quantum learnable in the following sense.
Proposition A.I. Assuming a maximum error 2na on the input states and a maximum error M the corresponding
labels, then there exists a fully-quantum protocol such that for every Ta E C. with probability 1 satisfies:
()) (I1=1()) - TT (fllrv S mea
(15)
where (f( A((0, 112mt1) denotes the distribution that the polynomial-tine quantum algorithm obtained from the learning algorithm A generates samples from on input {
We can adjust Def. 2.3 of fully-quantum protocols to take into account the presence of errors in the training data. Definition A.2 (Fully-quantum protocols with noisy data). A (Eeps eas Jufully-quantum protocol for the concept class C in Definition 3.1 is a polynomial-time algorithm A that takes as input training data the form
Ta. Tacoppe = (10y)))))) Be (1.
U. ~ (1()),
(16)
and ((0) ~u (10.1),)) paayin)
and outputs classical description of polynomial-time quantum algorithm that on input (wby) oe E Sphase generates a sample from distribution (f( E A(10, 1)2=-1).
Having noisy data, the natural modified learning condition for the fully-quantum protocol is the following.
Definition A.3 ((E, Exps eM, d, Psuce) (aael)--ffuluannnn learnable with noisy data). We say that C is (E, Eaps éM, 6, Psuce) Jfully- quantum learnable if there exists a (Eap: eM ) (-li)--lfguuumnnn -qaanumm protocol A such that for every Ta E C, with probability at least Psuce we have
P))-u((0.130)) (1 (f) =z(Oillrv= $ 2
(17)
where éoo = + Exp FEM and 7z (S) E A((O, 13 1 denotes the distribution that the polynomial-time quantum algorithm
obtained from the learning algorithm A generates samples from on input (ıby) S E Sphase-
We can now prove that the concept class C is fully-quantum learnable even in the presence of noisy data. Proposition A.4. Assuming maximum error of ep the input states, the concept class in Definition 3.1 is (0, exp emaz 0, 1)- fully-quantum learnable.
Proof. The proof follows directly from the one for the ideal case in Appendix A. The fully-quantum protocol performs exactly the same steps as in the ideal case, in this way the error in the prediction is bounded by the error in state preparation. Specifically, assuming for every f e {0, 13. input states (+) are such that:
d(wr) (1b5)) (,.))...))))
mar
(18)
sp
Then by the definition of trace distance we have that given any set of POVM {Em} (see Theorem 9.1 of (Nielsen & Chuang, 2010)) it holds that:
Σ |r| (1b5) Whrl - 1&s) (Vr (ep)le.)]]] S d((v)) (Wr)).))
(19)
12

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
Therefore, any probability distribution obtained from the measurement outcomes of the POVM Em on each state (yy) cap will have a total variation distance of at most d((w)) ksp)) compared to the distribution induced by applying the same esp)
POVM Em on the ideal states ( As the inequality ( 19) holds for any set of POVM {Em J. it will particularly be true for the set of POVM T of Eq.( 10) implemented by the fully-quantum protocol. This then concludes the proof as we previously showed that the fully-quantum protocol exactly reconstruct the target distribution Ty (f) for each f with zero error and we assumed emaz to be the maximum difference in trace distance between the noisy input states and the ideal ones.
Following the same reasoning as in the proof of Theorem 3.3 in Appendix B, is straightforward to show that when mar < 7/8, the learning task becomes intractable for any measure-first protocol. sp
B. Proof of Theorem 3.3
-6) 6) > 7/8 and Theorem 3.3. The concept class in Definition 3.1 is not (c, 6, Panccc)-measurr-ffrss learnable for (1-6). (11)))11))))
any Psuce > 0.
Proof of Theorem 3.3. The main building block of our proof of Theorem 3.3 is result in one-way communication complexity by Bar- Yossef, Jayram and Kerenidis (Bar- Yossef et al., 2004). They define a problem called Hidden Matching (HM). Here Alice is given string {0, 1JN, while Bob is given perfect matching M on the set [N], consisting of N/2 edges. Bob's goal is output some (i. fx @ fy) for some edge (i, j) E M. Their main result is:
Theorem B.1 (Classical hardness of HM (Bar- Yossef et al., 2004)). Let M be any set perfect matchings on [N] that is pairwise rdge-disjoin and satisfies JM| = [. Let μ. be the distribution over inputs to HM in which Alice's 's input is uniform in {0, 1} and Bob's 's input is uniform in M. Then, any deterministic one-way protocol for HM that errs with probability at most 1/8 with respect to p requires MV/N) bits of communication.
Suppose the concept class in Definition 3.1 is (c, 5. --ees-------efrnre learnable using measure-first protocol given by (M, A) with (1 c)- (1 8) > 7/8 and Psuce > O. Throughout the proof, will show that the existence of such measure-first learning protocol contradicts the classical hardness of HM outlined in Theorem B. To do so, consider the HM problem with MM- = MM x E {0, 10.] where
M₂ ((..vx) 10.
(20)
and note that [M] = N. To solve this instance of the HM problem Bob first generates training data TM as in Eq. 5. Note that Bob can do so because he has knowledge of the bitstring x. In particular, Bob can generate f( from {0, 1) compute
Ryco (x) and pick an element (y, b) from it. Next, Alice applies the measure protocol M to ( for her input f E (0, 1
and sends f M(1rg) Bob. Finally, Bob applies A on the data T.M he generated and Alice's input G to obtain sample (x, y, b) ~ T. (Wy). Since we assumed that Psuce > O, we know that for any x E {0, 1}" there must exist training data T.M and internal randomization of the learning algorithm A such that the polynomial-time quantum algorithm output by the protocol satisfies Eq. 6. Throughout the remainder of this proof, we assume Bob fixes this to be the training data and internal randomization he uses for his input x (note that Bob can do so because this does not depend on the input of Alice). Based on this fixed choice of training data and internal randomization we partition {0, 13.V F LI F denotes the set of functions for which
bad where F good
good
T.. (f) - TT (f)lly I 11-6,
(21)
where H. is the random function implemented by the quantum algorithm output by the protocol when using the training data TM and internal randomization as above. Moreover, we note [ gena > (1 11-5] 5)- 2n by Eq. 6. Finally, due Eq. 6 we find that the probability that (y, b) E (x) is at least
Pr((y,b) E Rx(x)) 2 (1
(22)
for all f E Food In conclusion, we find that the above described protocol is a randomized one-way communication protocol for HM with success probability at least for all inputs (z. f) in the subset
X =
U
{x} x Fr good
(23)
13

---

Limitations of Mcasure-Firsl Protocols in Quantum Machine Learning
In the remainder of our proof, we let (1, v denote the protocol that Bob TM, running the algorithm A on it, and drawing a sample from क (o))). Also, we ensure Bob does so using only classical randomized computation by classically simulating the quantum algorithms. Next, we use Yao's principle to show that the above randomized one-way communication protocol implies the existence of deterministic one-way communication protocol that errs with probability most (1 - e) (1-6) 6) with respect to μ (which would violate Theorem B.1 since (1- (1- 6) 7/8). Let A denote the family of deterministic protocols obtained by "hardwiring" all possible internal randomizations of the evaluation of T. by A', i.e.,
his side (i.e., generating the training data
A = (A((..) E {0, (0,1pe))()))
(24)
Also, let X be the random variable with values (x, f) distributed according to the uniform distribution over X, and let A be the random variable over A where the r uniformly random. Finally, we define the function s X'' x A
R as
s((z, A, (.. = [A,( $5) Ry(())
(25)
Theorem B.2 (Yao's principle). Let A be random variable with values in A. as defined in Eq. 24, and let X. be a random variable with values in X' as defined in Eq. 23. Then,
min E [ss(2,, max E [(((,, (2,
(26)
A.EA
where s the function defined in Eq.
Observe that the quantity E (s(X,,A)) AT)] is precisely the success probability of the deterministic algorithm A, E A with respect to the uniform distribution over X. Thus, Eq. 26 implies the existence of deterministic algorithm A' such that
[[,(X, AD) Pr(ee))uuis)
(A, (A, Fy) E Ry(x))
(27)
2 min E [ss((z,]),,) A)) (a.f)xx
(), A.] is precisely the success probability of the randomized algorithm A', which we have previously shown to be at least 1 c. By combining this with Eq. 27 we find that
Moreover, observe that the quantity min(x,,)ex E [s((,,
(4 E Ry(x)) 2 -
(28)
Moreover, since F good 2 (1 - 8) 2 we find that
Pr (A, (x)))) 2 21 (1--))(11-- (1
(29)
Finally, since
(1 7/8, this violates the classical hardness of HM outlined in Theorem B.
C. Proof of Theorem 3.6
Theorem 3.6. Let Spr = foo) St (())) PRF (k;,.....) k E K),, where PRF is a quantum-secure pseudorandom function with keys K. The concept class in Definition 3.1 not (e, 8, mmeasre-e firstt learnable for (1-c)-(1-b) Pauce > e for any constant e > 7/8 when the distribution over input states is uniform over Spr.
Proof of Theorem 3.6. Suppose the concept class in Definition 3.1 is (c, Pauce) -eaeurr----------- first learnable with Psuce (1 c) (1-11 - 8) > for constant > 7/8 when the distribution over input states uniform over Spr using a measure-firt protocol given by AM, That is, for every Ta C, with probability least Peuce have
Pro-au(K..) (1()))(())) n.. T= $() 1-5
(30)
where (.) (RF(k,.) .) and : the randomized quantum function obtained from A on input of the form
14

---

Limitations of Mcasure-First Protocols in Quantum Machine Learning
TMM = (0), (2,
T (F()))
(31)
poly(n)
and k ~ u (Kn)
The main goal of the remainder of the proof is to show that the above assumptions violates the assumption that PRF is a quantum-secure pseudorandom function. To achieve this, we devise a quantum algorithm, denoted as AI, which has query access to function f, and which will exhibit a significant difference in the probability of outputting when provided with either truly random function f or a pseudorandom function (()), In essence, A/ will train a measure-fite first protocol on phase states of pseudorandom functions and evaluate its performance on the provided function f. outputting if it produces correct sample (ar, y, b) with (v. b) E (x)) Assuming our measure-first protocol can successfully learn the concepts for phase states of pseudorandom functions, A will most likely output when f is pseudorandom. Conversely, if f is truly random, then based on arguments similar to those used in the proof of Theorem 3.3, the measure-first learning protocol is likely to be incorrect, leading A' to most of the time output 0. In particular, we consider the polynomial-ting quantum algorithm A that does the following:
1. Sample u{00, 13").
2. Generate a set of examples T.M as in Eq. 31
3. Use the learning algorithm A with set of examples T.M to obtain a quantum algorithm A' for 7..
4. Using quantum query access to f prepare kky) *
5. Apply M to (bb)) f obtain Gy M (105))*))
6. Apply A' to by to obtain sample (I,, y, b) and output y E Ry(x)), and 0 otherwise.
By the Eq. 30 and the paragraph leading up to it, we know that
P(K)))(()..)) [Ar = 2 Psuce (1 c). (1 (1-6)
(32)
On the other hand, from the classical lower bound for the HM problem in Theorem B.I, we know that P (A) = 1] s 7/8.
(33)
In particular, if Eq. 33 does not hold, then one can construct one-way communication protocol for HM that succeeds with probability at least 7/8 with respect to μ by having Bob perform steps (2) (3), having Alice perform steps (4) (5), and sending y to Bob to perform the first part of step (6) where they obtain the a sample (I, y, b). In summary, we conclude that the measure-fire first protocol, when trained on phase states of pseudorandom functions, cannot generalize well to truly random functions based on the lower-bound established for the HM problem in Theorem B.I. Moreover, given our assumption that the concept class C in Definition 3.1 is (c, 5, P.Pance Damcc)-measureefff first learnable on phase states of pseudorandom states, it has to generalize well to other pseudorandom states. This implies a distinctive behavior of the "benchmarking algorithm" A when provided with access to either pseudorandom function ((() or a truly random function f. In other words, we thus conclude that Eq. 32 and Eq. 33 are in contradiction with the assumption that PRF is quantum-secure pseudorandom function.
D. Two examples of measure-first protocols
To elaborate on the definition of measure-first (MF) protocols (i.e., Definition 2.5) and their potential capabilities, we present two concrete MF protocols that, at first glance, appear capable of solving the learning task. However, in each case, we identify fundamental reasons for their failure, which highlight the limitations of MF protocols.
*Note that we can do so efficiently using a quantum algorithm since only consider phase states of pseudo-random functions.
"This step is also efficient both for random and pseudorandom function since we suppose oracle access to f-
15

---

Limitations of Mcasure-Firs, Protocols in Quantum Machine Learning
D.I. Measure-first protocol based classical shadows
One plausible MF protocol leverages the classical shadow framework (Huang al., 2020). Here, the measurement strategy M takes as input multiple copies of each state ( and generates a classical representation B by performing randomized measurements as prescribed by the classical shadow protocol (Huang et al., 2020). The learning algorithm can then use the training data Fg to determine z and output a hypothesis hg. This hypothesis would use the classical representation zhy to predict the correct labels associated with by approximating the outcomes of the POVMs F.j.
However, for the hypothesis hr to generate samples (y, b) that are close in total variation distance to the target distribution Ag, the precision required each POVM f must scale exponentially. As result, the number of copies N of ((by) required by the classical shadow protocol to achieve such precision also grows exponentially. Therefore, this MF protocol fails due to fundamental limitations in efficiently compressing pseudorandom phase states into classical representations capable of achieving the required exponential precision. this sense, our result can also be interpreted as a lower bound on the number of copies required for any shadow-based procedure to recover observables with exponential precision.
D.2. Measure-first protocol with circuit learning
Another potential MF protocol could attempt to directly learn a polynomially-sizer description of the circuit that prepares the pseudorandom states y) By definition, pseudorandom states are efficiently preparable and always admit such a circuit. In this approach, the measurement scheme M would take as input multiple copies of (vb)) and attempt to infer this circuit description. The learning algorithm A would then use the training data Ta to determine æ and output a hypothesis 1t. The hypothesis hg could use the learned circuit to recreate the state ( and implement the measurement Ag.
However, despite the existence of polynomial-depth eircuit that prepares ( our results show that no efficient mea- surement strategy M can extract succinct classical description of this circuit. This failure arises from the inherent pscudorandomness of the states, which ensures that no efficient measurement strategy can compress the information contained in (gby) into a usable classical description. Consequently, this MF protocol also fails to achieve the learning goal.
These examples highlight not only the challenges faced by MF protocols but also the fundamental separations between MF and fully quantum (FQ) protocols. They illustrate the difficulty of efficiently compressing pscudorandom phase states into classical descriptions that retain enough information for the machine learning task.
16


Reviews:
[{"review_id": "2AgDUg1fFr", "reviewer": "Reviewer_KBU4", "summary": "This paper details the difference of two approaches in the task of quantum state or quantum distribution identification. The first approach is the measure-first approach where form a given set of quantum samples, a randomized measurement is performed and then a classical representation is constructed. The second approach, fully-quantum, takes the quantum data and from it directly constructs the classical distribution, or classical image.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**My main concern in this work is that of concrete advancement. ...  As such, is the novelty defensible?**\n\nWe appreciate the reviewer’s comment and would like to clarify that our contribution is both novel and nontrivial.\n\nFirst, our work is motivated by practical ML scenarios, focusing on quantum states efficiently preparable on quantum hardware. The HM problem, by contrast, originates in communication complexity, where lower bounds do not directly apply when states can be efficiently prepared. In such cases, the preparation circuit itself can act as a message, potentially bypassing standard lower bounds.\n\nTo address this, we rigorously prove that learning remains classically intractable even for efficiently preparable states. We achieve this by leveraging pseudorandom states and imposing a time efficiency constraint on the learner—a key consideration in ML. This step is crucial: without it, the separation would lack practical significance. With it, however, we extend the separation beyond the HM setting, showing the advantage persists as long as the states are sufficiently \"rich.\"\n\nSecond, unlike the traditional HM problem, we focus on average-case correctness and robustness to noise—both critical in ML but absent in HM.\n\nIn summary, our contribution is both highly relevant to ML and nontrivial (e.g., it requires invoking results on pseudorandom states and Yao’s principle for average-case hardness). We hope this clarifies the novelty of our work.\n\nAdditionally, while one might expect a fully quantum protocol to be inherently more powerful than measure-first protocols -- given that, as you note in (b), quantum computing enables unitary transformations before measurement -- measure-first protocols are surprisingly powerful. This makes our results far less trivial than they may seem. For further details, we refer the reviewer to our response to Reviewer StyH regarding their comment: “The results of the paper, in the context of recent works, are not surprising but useful to know”.\n\n**Just a comment: Huang 202a and Huang 202b are the same paper.**\n\nThank you for catching this! We will correct the references in the updated manuscript.\n\n**Definitions 2.2 and 3.1 are identical (in particular, Equations 2 and 7).**\n\nWhile Definitions 2.2 and 3.1 share similarities, they serve different purposes. Definition 2.2 is a general formulation of the learning problem without specifying a particular distribution, while Definition 3.1 introduces the distribution \\pi_x(f) that exhibits the separation between measure-first and fully quantum protocols. \n\n**However, the authors did not elaborate on what is meant by \"we can introduce various levels of learning\"—what types of learning would actually be considered real or meaningful learning tasks?**\n\nBy \"real/more of a learning task,\" we refer to scenarios where the value of x (that is hidden in the dataset) cannot be directly extracted from a single datapoint but instead requires a learning algorithm that processes multiple datapoints to infer x. Specific examples of such learning tasks are detailed in Appendix A.\n\n**I would suggest exploring how quantum machine learning could fundamentally reshape this problem rather than viewing it as a straightforward extension of prior work. Is quantum machine learning genuinely useful for this problem? Could the problem be reformulated in a different representation, or could additional information change the findings?**\n\nThank you for the thoughtful suggestion! Our primary motivation is not to explore how machine learning changes this problem but rather to highlight how machine learning itself is affected by the nature of the data it receives. Our work underscores the crucial role of processing unmeasured quantum data in learning tasks, presenting a scenario where quantum advantages naturally arise. In particular, our results suggest that certain learning problems inherently require the \"exponential capacity\" of quantum states, a feature distinct from classical data representations.\n\n**How would the approach change if the states were generated from a distribution rather than given as copies from an ensemble?**\n\nWe must admit that we do not fully understand the reviewer’s question. In our work, the quantum states are indeed \"drawn/generated\" from a distribution—specifically, the uniform distribution over multiple copies of pseudorandom phase states. \n\nIf your question is whether the separation still holds when receiving only a single copy at a time, the answer is yes. The fully quantum protocol can already learn the problem with just a single copy at a time, whereas providing multiple copies simultaneously can only benefit the measure-first protocol. In other words, by giving multiple copies at once, we are actually favoring the measure-first protocol, making our separation result even stronger.", "claims_and_evidence": "The paper support the claims by proper evidence. The proofs are correct up to my understanding", "methods_and_evaluation_criteria": "The authors suport their claims on a set of previously proven results in particular on the results of the Hiddem Matching problem that states that given a quantum state it is not possible to reconstruct it in polynomial time efficiently. Based on this proof the authors claim that the measure first protocol is also not a learnable function.", "theoretical_claims": "Yes the proofs seems to be correct", "experimental_designs_or_analyses": "My main concern in this work is that of concrete advancement. Considering that a) quantum computing performs unitary transforms up to the measurement, b) the HM problem has been proven and c) the definition of the learning problem in Def 2.2 and 2.5, is the novelty in this paper not an direct extension of the previous results by throwing it into a slightly different context? As such is the novelty defensible?", "relation_to_broader_scientific_literature": "The paper discusses the main papers supporting the work. Just  comment Huang 202a and Huang 202b are the two same papers. Perhaps the authors were considering the work Huan 2022, Learning quantum states from their classical shadows, Nature", "essential_references_not_discussed": "I believe authors mentioned most relevant literature to their work", "other_strengths_and_weaknesses": "- The paper is clear enough but I had trouble to understand it as in my opinions the definitions and flow would benefit from a clearer description.\n- Definitions 2.2 and 3.1 are identical (in particular equations 2 and 7)\n- The fact that the fully quantum protocol can learn the mapping $\\pi_x \\rightarrow \\vert \\psi_f\\rangle\\rightarrow \\mathcal{U}_x\\vert\\psi_f\\rangle\\rightarrow \\mathcal{M} \\rightarrow y\\in\\mathcal{U}(\\mathcal{R}_f(x))$ is under the described conditions without any difficulties on the learning mechanism (implementation not considering). However the authors did not elaborate as quote \"we can introduce various levels of learning\" what types of learning would be actually considered real or more of a learning tasks.", "other_comments_or_suggestions": "I would suggest to determine that instead of looking at the proposed problem as a simple extension of the previous work on how ML can actually change this problem. Is truly quantum machine learning applied to this problem helpful? Can the problem e restated in different representation or can additional information be helpful to change the findings?", "questions_for_authors": "How would the approach change if I have distribution of states from a generator and a copy of the same state from an ensemble?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E0gAOeqKl8", "reviewer": "Reviewer_StyH", "summary": "The paper compares two quantum learning paradigms: (i) the measure first protocols where the learner uses a priorly determined measurements to obtain some classical information about the training samples (shadow tomography), (ii) a fully quantum learner that is allowed to make measurements that depend on the outcomes of previously seen states. The authors show the existence of a setup where measure-first approach is provably worse than the full quantum protocols.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We naturally find it disappointing that our work was evaluated with 1 out of 5. We are hopeful that the majority of this evaluation stems from misunderstandings, probably caused by our wording, which we can dispel and clarify. We will do our best to address the reviewer’s concerns and demonstrate why we believe our paper is deserving of publication at ICML.\n\n**Some recent key works in shadow tomography were not cited**\n\nThank you for pointing out these references! We added these papers as references exhibiting the advantages that have been identified when measure-first protocols are allowed coherent measurements of multiple copies of a given quantum state (as discussed in the introduction in the manuscript). These references thus further elucidate the inherent power of measure-first protocols and further motivate the question of whether advantages are possible for fully-quantum protocols.\n\n**The results of the paper, in the context of recent works, are not surprising but useful to know.**\n\nIn discussions with experts, we often encounter two opposing intuitions: some expect a distinction between fully quantum and measure-first schemes, while others—citing the success of shadow tomography—believe no such difference exists. The reviewer appears to align with the first view. To illustrate why some believe no such separation exists, we offer additional context.\n\nA significant body of evidence suggests measure-first protocols can be surprisingly powerful, making our result less obvious than it may seem. For instance, a recent milestone [2] demonstrated that a measure-first protocol (classical shadows of ground states [1]) could accurately predict many observables of gapped Hamiltonians. Similarly, a study by field experts [3] showed that for many quantum learning tasks, classical CNNs using classical shadows performed comparably to quantum neural networks. Notably, the authors questioned whether any task could conclusively separate classical and quantum approaches. The works cited by the reviewer further support the surprising strength of measure-first protocols.\n\nIn the quantum ML setting, if labels corresponded to expectation values of local observables rather than measurement outcomes, measure-first and fully quantum protocols would be equivalent due to classical shadows' provable guarantees [1]. Given this, demonstrating a clear separation is nontrivial and far from obvious.\n\nOf course, the reviewer may still find the result unsurprising, but even so, we believe rigorously proving it remains a valuable contribution. Moreover, the proof is nontrivial, and we see no simpler way to establish this fact.\n\nWe hope this clarifies our perspective and underscores the broader significance of our work.\n\n[1] Huang et al. \"Provably Eff. ML for Quantum Many-Body Problems.\" Science \n\n[2] Huang, et al. \"Quantum Adv. in Learning from Experiments.\" Science\n\n[3] Bermejo, Pablo, et al. arXiv:2408.12739.\n\n**Can you justify the proposed model of QML? Isn't it more natural to consider post-measured quantum states with the measurement labels?**\n\nWe appreciate the reviewer’s concern. From their comments, we understand that “QML model” refers to supervised learning with quantum states as data and classical labels.\n\nThis model is well-established in the literature as a natural generalization of classical supervised learning. The study of learning with quantum data dates back to the early 2000s [1,2], with subsequent works generalizing the framework [3,4]. More broadly, learning from quantum states is a central theme in quantum information, akin to classical supervised learning, where the goal is to learn a labeling function. Fundamental results [5] have shown exponential advantages using quantum memory, while classical shadows further motivate our approach.\n\nA key practical motivation is its relevance to experimental quantum systems. An experimenter can repeatedly prepare a quantum state ρ, measure different observables, and obtain datasets consisting of copies of ρ alongside measurement outcomes. This setup aligns with standard approaches in quantum state and shadow tomography [1,2] and formal frameworks for learning with quantum datasets [4].\n\nFinally, if the dataset were modified to include post-measurement states with their labels, it would precisely correspond to the information accessible to a measure-first protocol, which receives the same data generated by a quantum state’s measurement process, along with the classical label.\n\nThus, we believe our model is well-motivated and widely accepted in quantum machine learning.\n\n[1] Aaronson \"The learnability of quantum states.\"\n\n[2] Huang, et al.. \"Predicting many prop. of a quantum system from very few measurements.\" Nature Physics\n\n[3] Gambs, S. arXiv:0809.0444 \n\n[4] Guță, M., et al. \"Quantum learning: asymptotically optimal classification of qubit states.\" New Journal of Physics\n\n[5] Chen, Sitan, et al. \"Exp. separations between learning with and without quantum memory.\" FOCS", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I looked at the results and it makes sense but I did not check the detailed proof arguments.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "The findings are broad to the areas at the intersection of shadow tomography and quantum machine learning.", "essential_references_not_discussed": "Some recent key works in shadow tomography were not cited: \n- Triply efficient shadow tomography, Robbie King, David Gosset, Robin Kothari, Ryan Babbush\n- Optimal tradeoffs for estimating Pauli observables, Sitan Chen, Weiyuan Gong, Qi Ye\n- Adaptivity can help exponentially for shadow tomography, Sitan Chen, Weiyuan Gong, Zhihan Zhang\n\nEspecially the last paper seems to be very much related to the findings of this work.", "other_strengths_and_weaknesses": "The results of the paper, in the context of recent works, are not surprising but useful to know. The paper is well written and rigorous. \n\nHowever, I did not find the QML model confining! The training samples in the model are the quantum states with the post-measurement outcomes. This is a model rather artificial. Because of the state collapse of the quantum measurements, it is not typically feasible to have a quantum state before the measurement and the measurement outcome after that.  Unless I am missing some parts of the paper/concept. I am not sure if the presented model makes sense.", "other_comments_or_suggestions": "no", "questions_for_authors": "Can you justify the proposed model of QML?\nIsn't it more natural to consider post-measured quantum states with the measurement labels?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6KXkbnr8KT", "reviewer": "Reviewer_G1ds", "summary": "This paper establishes a theoretical framework contrasting two quantum machine learning approaches: \"fully-quantum\" protocols that adaptively measure quantum data versus \"measure-first\" protocols restricted to fixed initial measurements. The authors prove that certain learning problems can be efficiently solved using fully-quantum methods but remain impossible for measure-first approaches, even when limited to efficiently preparable quantum states. This separation demonstrates that some learning tasks fundamentally require processing unmeasured quantum data, necessitating the exponential nature of quantum states. The work suggests ground states of complex local Hamiltonians as promising candidates for demonstrating this separation, with potential alternative constructions using computationally indistinguishable states. The work highlights the importance of fully quantum machine learning processing.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The description of the task could be more accessible for the machine learning community.**\n\nWe regret that the reviewer finds the description insufficiently accessible to the ML audience and take their criticism to heart. We have made a concerted effort to present a clear explanation in Section 1.1, but the interdisciplinary nature of our work and the page limits of ICML make further simplification challenging without introducing excessive quantum computing jargon. Given these constraints, we believe we have provided the most accessible presentation possible.\n\n**It needs more discussion about the practical relevance of the main results to machine learning.**\n\nWhile our work is primarily theoretical, we have discussed its practical relevance in the conclusion section of the paper. To summarize, our findings underscore the importance of processing unmeasured quantum data in machine learning, revealing scenarios where quantum advantages naturally arise. Specifically, we identify learning tasks that fundamentally require the exponential capacity of quantum states. While our proof relies on separations in one-way communication complexity and pseudorandom states, it suggests broader implications: quantum advice states that cannot be classically simulated with polynomial overhead -- such as the ground states of sufficiently complex local Hamiltonians -- could also demonstrate similar separations. Additionally, complexity-theoretic constructions like computationally indistinguishable states provide alternative routes to exhibiting gaps between measure-first and fully quantum protocols.\n\n**It would be better to have discussions on implementation for demonstrating this separation.**\n\nWe appreciate the suggestion. We are actively collaborating with an experimental team to explore potential implementations. However, demonstrating this separation in practice poses significant challenges, even in idealized simulations. A key difficulty is determining the optimal measure-first protocol for the given task -- essential for rigorously establishing a separation. While we have ideas on tackling this, a full exploration requires a dedicated project and thus is beyond the goals we had for this work. Nevertheless, we emphasize that our proof of separation results for efficiently preparable quantum states brings our work closer to practical experimental realization.\n\n**Describe the classical analog of the machine learning problem considered in this paper and provide the relevant literature.**\n\nThe problem we study is inherently quantum, making a direct classical analog difficult to define. Instead, classical analogs emerge in the learning strategies rather than the problem itself, giving rise to our distinction between measure-first and fully quantum protocols.\nIn principle, the closest classical counterpart would be supervised learning with noisy or probabilistic labels, where the labeling function does not assign a deterministic label y to an input x. but instead samples y from a probability distribution p(y∣x). However, in our case, the crucial distinction is that the data x consists of quantum states. This fundamental difference -- i.e., how quantum data is processed -- underpins the separation between measure-first and fully quantum protocols, making standard results from supervised learning with noisy or probabilistic labels not directly applicable to our setting.\n\n**Are there other learning problems (more operational) that would exhibit similar performance gaps between fully quantum and measure-first approaches?**\n\nThank you for the insightful question! Our results suggest that learning problems linked to hard problems in (F)BQP/qpoly are prime candidates for requiring fully quantum protocols. A key result by Aaronson and Drucker [1] shows that any problem solvable with polynomial-sized quantum state advice can also be solved using the ground state of a local Hamiltonian as advice. This implies that learning problems involving the ground states of sufficiently complex local Hamiltonians could also exhibit a separation between measure-first and fully quantum protocols. While rigorously proving such separations remains a challenge, studying the learning properties of these quantum states is a promising avenue for future research. We discuss this in the Conclusion section of the paper.\n\n[1] Scott Aaronson and Andrew Drucker. \"A full characterization of quantum advice.\" Proceedings of the Forty-Second ACM Symposium on Theory of Computing.", "claims_and_evidence": "The claims and evidence are mainly from the theoretical perspective and are basically fine.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are reasonable for a theory paper.", "theoretical_claims": "Via a rough check of the proofs, they look correct to me.", "experimental_designs_or_analyses": "The experimental design is not needed since this is a pure theory paper.", "relation_to_broader_scientific_literature": "Reasonable literature review.", "essential_references_not_discussed": "The reference is reasonable in this paper.", "other_strengths_and_weaknesses": "The strengths:\n1. Rigorous proof of the case when fully quantum learners are more powerful than measure-and-learn protocols. \n2. The work delivers insights for other topics such as ground states of complex Hamiltonians and computationally indistinguishable states.\n\nThe weaknesses: \n1. The description of the task could be more accessible for the machine learning community. \n2. It needs more discussion about the practical relevance of the main results to machine learning. \n3. It would be better to have discussions on implementation for demonstrating this separation.", "other_comments_or_suggestions": "1. Describe the classical analog of the machine learning problem consider in this paper and provide the literature.\n2. Make task descriptions more accessible to ML researchers.\n3. Elaborate on practical ML applications of the findings.\n4. Include implementation strategies to demonstrate the separation.", "questions_for_authors": "1. Could you revise the description of your learning task to make it more accessible to researchers from the machine learning community?\n2. How do your theoretical results on quantum-classical separation translate to practical applications in machine learning?\n3. Are there other learning problems (more operational) that would exhibit similar performance gaps between fully-quantum and measure-first approaches?\n4. What implementation strategies would you suggest for experimentally demonstrating the separation between fully-quantum and measure-first protocols?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PyOCxz8pgO", "reviewer": "Reviewer_8rQu", "summary": "This work is motivated by randomized measurement protocols to analyze the separation in quantum machine learning when processing quantum data using fully quantum operations versus measuring the input data and utilizing classical information. It highlights the limitations of measure-first protocols and provides examples demonstrating learning separations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The paper discusses the impact of noise on the task but lacks numerical validation. Why do you not provide numerical validations?**\n\nWe appreciate the reviewer’s suggestion regarding numerical simulations and experimental validation. We would like to mention that we are already collaborating with an experimental team on this front. However, there are significant challenges in conducting such experiments, even in ideal simulations. Moreover, we would like to clarify that this is a theoretical paper, where we provide rigorous guarantees on the robustness of our results to noise. While exploring the effects of various noise models on our protocols is certainly an interesting direction, we believe it falls outside the scope of this work. Our primary focus is on establishing a fundamental separation between MF and fully quantum protocols, rather than on noise analysis itself. Investigating additional aspects would introduce a different set of challenges and convey a different message, which is beyond the intended scope of this paper.\n\nAdditionally, we would like to refer to our response to a similar comment from Reviewer G1ds: “It would be better to have discussions on implementation for demonstrating this separation.” In that response, we discuss the practical challenges involved in demonstrating or validating our separation, particularly the difficulties in demonstrating/validating that no single measure-first protocol can match the performance of the fully quantum protocol. Given these challenges, we believe that a comprehensive exploration of this issue would require a dedicated project, which falls beyond the scope of the current work.\n\n**It would be highly valuable if the authors could provide further insights into selecting between the fully quantum approach and the measurement-first approach for different applications. Currently, many methods employ classical shadow techniques combined with machine learning to infer properties such as expectation values with respect to observables, i.e., Tr[Oρ]. These methods have demonstrated promising results, achieving relatively high accuracy. It would be beneficial for the authors to comment on such cases and offer explanations on when to choose specific approaches beyond the Hamiltonian model (HM) discussed in this work.**\n\nWe appreciate the reviewer’s insightful question. Our results provide a useful indicator of when MF protocols may be insufficient, particularly concerning the complexity of the quantum state family and the nature of the learning task. Specifically, our findings suggest that machine learning problems related to hard problems in (F)BQP/qpoly inherently require fully quantum protocols.\n\nAn important result in quantum complexity theory [1] shows that any problem solvable with polynomial-sized quantum state advice can also be addressed using the ground state of a local Hamiltonian. This suggests that learning problems where the input consists of sufficiently complex local Hamiltonian ground states could exhibit a separation between MF and fully quantum protocols. While rigorously proving such separations remains a challenging open problem, this connection points to a promising research direction for understanding the limitations of MF protocols in physically relevant settings.\n\nThe reviewer also raises an interesting point about classical shadow techniques, which have proven effective in estimating expectation values. While these methods can achieve high accuracy for specific tasks, they rely on structured measurement strategies and focus on extracting partial information from quantum states. In contrast, our results suggest that when the underlying learning problem fundamentally relies on the exponential storage capacity of quantum states, classical shadow techniques and other MF approaches may be insufficient.\n\nOverall, while MF methods, including classical shadows, are useful in many practical scenarios, our work identifies cases where a fully quantum approach is necessary. Investigating these cases further—particularly in the context of learning with local Hamiltonian ground states—is an exciting avenue for future research that likely requires a dedicated study.\n\n[1] Scott Aaronson and Andrew Drucker. A full characterization of quantum advice. Proceedings of the forty-second ACM Symposium on Theory of Computing.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes, it make sense.", "theoretical_claims": "The proofs are rigorous and address a fundamental question in machine learning.", "experimental_designs_or_analyses": "There is no experimental designs or analyses.", "relation_to_broader_scientific_literature": "It contributes to the field of machine learning by providing guidance on using classical shadows to learn specific properties of quantum systems.", "essential_references_not_discussed": "I think all related works are cited.", "other_strengths_and_weaknesses": "Strengths:\n1. I believe the authors address a fundamental problem in quantum machine learning by comparing two main approaches: the measurement-first method and the fully quantum approach. While it is intuitively expected that the fully quantum approach would perform better, the authors provide a rigorous proof to support this claim.\n\nWeakness:\n1. The paper discusses the impact of noise on the task but lacks numerical validation.\n2. It would be highly valuable if the authors could provide further insights into selecting between the fully quantum approach and the measurement-first approach for different applications. Currently, many methods employ classical shadow techniques combined with machine learning to infer properties such as expectation values with respect to observables, i.e.Tr[Oρ]. These methods have demonstrated promising results, achieving relatively high accuracy. It would be beneficial for the authors to comment on such cases and offer explanations on when to choose specific approaches beyond the HM discussed in this work.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1. Why you do not provide numerical validations?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper establishes a theoretical framework contrasting two quantum machine learning approaches: "fully-quantum" protocols that adaptively measure quantum data versus "measure-first" protocols restricted to fixed initial measurements. The theory is solid and the conceptual message is important, although the authors could use extra efforts in motivation and describing the two settings to avoid confusion.  We hope the authors could take their rebuttals to other comments also into the revision.
Decision: Accept (poster)