Limitations of measure-first protocols in quantum machine learning

We thank the reviewer for their insightful comments and suggestions. In response, we have clarified the distinction between our work and Aaronson et al. (2023), emphasizing that our separation holds for efficiently preparable quantum states, which is relevant for practical quantum machine learning. We also expanded on the worst-to-average reduction, noting that our result is broader than Aaronson's and requires proof techniques such as Yao's lemma. Regarding the artificial nature of the problem, we have highlighted how our separation could extend to more physically relevant quantum states, like ground states of local Hamiltonians, though this requires new techniques beyond the scope of the current work.

We hope these revisions and clarifications address your concerns and improve the clarity of our arguments. We trust that these changes will help in reconsidering the evaluation of our work. Thank you again for your thoughtful feedback.

-Is the proved separation just an instance of [S. Aaronson et al., 2023], where FBQP/poly represents classical shadow-based algorithms (including measure multiple states by Bell measurement).

We thank the reviewer for this insightful question. While our results are related to those of Aaronson et al. (2023), we would like to emphasize that they are not merely an instance of their work. Aaronson's results rely heavily on the fact that quantum advice states require an exponentially large description. In contrast, a key aspect of our work is that the separation between measurement-first protocols and fully quantum protocols holds even for quantum states that can be efficiently prepared on a quantum device, which admits a polynomially-sized description in the form of the circuit preparing it. This distinction is crucial because, without it, the separation would lack relevance to real-world quantum machine learning applications. With this consideration, we provide compelling evidence that such separations can extend to a broader range of learning tasks, as long as the states involved are sufficiently "rich." Inspired by this question, we have added a brief explanation of this significant difference in the revised version of the manuscript.

Furthermore, to bring our separation closer to practical machine learning scenarios, we employ proof strategies involving Yao's principle to specialize our result to the average case, and we also account for potential noise in the data. We would also like to refer the reviewer to Part 2 of our general response to reviewer RYau for even more details.

- The worst-to-average reduction seems very natural; if my understanding is correct: the classical shadow methods may fail for every x (as shown in Eq.~7), due to the fact that FQBP/qpoly != FBQP/poly

We thank the reviewer for this comment. We would like to note that the result from Aaronson would imply that for every f there is at least one x on which classical methods (e.g., shadows) must fail. Critically, in our average case reduction we prove a broader result: for every x, there is at least a fraction of f’s for which a classical method must fail. We believe this is not straightforward per-se and requires proof-techniques relying on tools such as Yao's lemma.

- The main contribution of this paper relies on the Theorem~2. I know the proof idea is there, but the proof details in the Appendix B is not very easy to follow.

We apologize for any difficulties the reviewer may have encountered in following our proof. If possible, could you kindly highlight any specific points that were unclear, so we can provide further clarification or elaboration? Nonetheless, we would like to emphasize that we believe the claim is genuinely nontrivial and subtle, and as such, it is unlikely that a much more streamlined proof could be provided without sacrificing essential rigor or clarity.

- It would be helpful to provide the explicit construction of U_x (also the learned measurement operator).

We thank the reviewer for this comment. We provided the explicit construction in the revised version of the paper.

- The problem is quite artificial (alghough Y. Liu et al. Nat. Phy. 2021 is still an artifical construction); it would be perfect if the phase states can be substituted to other more practical quantum state (such as ground state or thermal state of a physical system).

We appreciate the reviewer’s insight and would like to clarify that although the proof in our current work is somewhat artificial, we strongly believe that the claim is much more broadly applicable. We conjecture that a formal proof of separation for a more general class of states, such as the ground state of a sufficiently complex local Hamiltonian, is achievable. However, this would require the development of new proof techniques, which goes beyond the scope of our current work.

In this regard, we refer the reviewer to Part 2 of our addressing of the Questions/Weaknesses in the review of Reviewer Mm3W. To briefly reiterate, building on the work of Aaronson et al. (2023), we speculate that phase states could be replaced by the ground states of sufficiently complex local Hamiltonians. This would allow us to extend our separation result between measurement-first protocols and fully quantum protocols to more physically relevant problems, such as predicting the ground state properties of local Hamiltonians. While this is indeed an exciting direction, it would require further investigation and would likely constitute a separate study.

Furthermore, we note that pseudo-random phase states have recently been demonstrated to be realizable as Hamiltonian phase states (see [arXiv:2410.08073]), which are states that can be prepared by time evolution under a sparse Ising Hamiltonian. This brings us closer to the physical realization of such states and reinforces the broader relevance of our separation result.

We thank the reviewer for the time spent on this review. We are particularly happy that they appreciate the soundness of our proofs and the relevance of our result within the field of quantum machine learning.

We sincerely thank the reviewer for their thoughtful comments and suggestions. In response, we have made several important clarifications that we believe strengthen our work. First, we have provided a more concrete description of the task leading to the separation between "measurement-first" and "fully quantum" methods, clarifying its connection to Theorem 1, and we have made cosmetic revisions to improve the clarity and readability of the presentation. Additionally, we have expanded the discussion regarding the relevance of our results to natural quantum learning problems. We elaborated on cases where fully-quantum protocols are essential, especially in learning problems related to (F)BQP\qpoly, and highlighted a promising avenue for future research: the potential for a separation in learning tasks involving the ground states of sufficiently complex local Hamiltonians. We hope that these clarifications, along with the more detailed conclusion, will give the reviewer a clearer understanding of the broader applicability of our results. With these revisions and clarifications, we hope the value and novelty of our work is now more apparent, and we hope the reviewer might reconsider their evaluation of our paper.

- Do the authors consider the separation to hold in many natural learning problems that people are actively working on? Could the authors comment on whether the community should consider most problems to be addressable using measurement-first protocols? If not, could the authors comment on what families of problems one should expect fully-quantum protocols to be much more powerful than measurement-first protocols? Providing a few concrete examples of widely-studied quantum machine learning problems where they expect their results might be relevant would also be useful in this context.

We thank the reviewer for this insightful question. Indeed, recent years have seen significant results where measurement-first protocols provide surprisingly strong theoretical guarantees in various physically-relevant tasks, such as learning phases of gapped Hamiltonians (e.g., see [1,2]). Our result, however, highlights that there are learning tasks where a fully quantum protocol is essential. In particular, our results indicate that ML problems related to the hard problems in (F)BQP\qpoly are the learning problems where fully-quantum protocols are required.

As a consequence of this, we would like to draw the reviewer’s attention to an interesting connection of our result with more physically relevant tasks. According to an important result by [3], any quantum computation that can be solved with polynomial-sized quantum state advice can also be solved using a different quantum circuit with advice derived from the ground state of a local Hamiltonian. Formally, this implies that any task in BQP\qpoly can be tackled within BQP using a quantum state from the ground state of a local Hamiltonian as advice. Based on this, we speculate that learning problems where the input data is the ground state of a sufficiently complex local Hamiltonian might exhibit a separation between measure-first and fully quantum protocols. Although we recognize the distinctions between relational and decisional problems, and we acknowledge that rigorously proving such learning separations involves significant complexities, we believe a promising direction for exploring the limitations of measure-first protocols in physically relevant tasks would be to investigate the learning properties of local Hamiltonian ground states. This is an intriguing avenue for future research, though it would likely require a dedicated, separate project

We already touched upon this in the previous version of the conclusion, but for completeness, we have expanded the conclusion section in the revised version to provide a more in-depth discussion on this matter.

[1] Huang, Hsin-Yuan, et al. "Provably efficient machine learning for quantum many-body problems." Science 377.6613 (2022).

[2] Huang, Hsin-Yuan, et al. "Quantum advantage in learning from experiments." Science 376.6598 (2022).

[3] Scott Aaronson and Andrew Drucker. "A full characterization of quantum advice". Proceedings of the forty-second ACM symposium on Theory of computing.

- While the paper discusses robustness to noise theoretically, no numerical simulations or experimental results are provided to demonstrate the practicality of the proposed protocols. Given the theoretical claims regarding noise robustness for the separations established in this work, could the authors add a numerical experiment showcasing the separation under noisy settings? For example, it would be beneficial to simulate your protocols with realistic noise models for near-term quantum devices. It would also be useful to see how the separation between measure-first and fully-quantum protocols changes as noise increases.

We appreciate the reviewer’s suggestions for 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 just in ideal simulations. For instance, demonstrating that the separation holds "for all" MF protocols requires identifying the optimal MF protocol for the given task, which is a complex problem. While we have some ideas on how to address this, it is a substantial undertaking that we believe warrants a separate, dedicated project. Moreover, we would like to clarify that this is a theoretical paper, where we provide rigorous theoretical guarantees on the robustness to noise. While investigating the effects of different noise models on our protocols is certainly an interesting direction, we believe it falls outside the scope of this work. In particular, since our primary focus is on establishing the theoretical separation between measure-first and fully-quantum protocols, rather than on noise analysis itself, we have chosen not to include numerical simulations. Investigating other aspects would present a completely different set of challenges and convey a different message, which is outside the scope of our current work.

- The main result (Theorem 1) is stated in terms of an existence statement. Could the author provide a more concrete description regarding the task that leads to the separation between "measurement-first" vs "fully quantum" methods?

We thank the reviewer for their comment, and we are glad to have the opportunity to improve the presentation of the task that leads to the separation. In the initial manuscript, the task that results in the separation between "measurement-first" and "fully quantum" methods is outlined in Section 3.1, with a high-level overview provided in Section 1.1. To enhance clarity, in the revised version of the paper, we explicitly state that the task referenced in Theorem 1 is the same as the one defined in Section 3.1, and we have made several cosmetic changes to improve readability.

We thank the reviewer for taking the time to provide their feedback. We are pleased that they recognize the relevance of our work within the field and acknowledge our use of diverse proof techniques, which distinguishes our results from previous works.

Dear Reviewer,

The authors have provided their rebuttal to your comments/questions. Given that we are not far from the end of author-reviewer discussions, it will be very helpful if you can take a look at their rebuttal and provide any further comments. Even if you do not have further comments, please also confirm that you have read the rebuttal. Thanks!

Best wishes, AC

I would like to thank the authors for their responses. Their responses have addressed my questions.

We sincerely thank the reviewer for their detailed comments and suggestions, which have greatly helped us to better articulate the significance of our work. In our reply, we have addressed several points of concern and clarified key aspects of our results. Specifically, we have provided a broader context for the "measure first, ask questions later" paradigm to demonstrate the nontrivial nature of our separation results. We have also explained why our reduction is both meaningful and distinct from a mere restatement of known results, particularly in the context of efficiently preparable states and real-world machine learning scenarios.

We hope that the explanations provided in our reply may lead the reviewer to a more favorable opinion of our work as we have clarified that: (i) while the result might initially appear unsurprising, the broader context of the power of MF protocols underscores that establishing such a separation is far from trivial, and (ii) we emphasize that our result is not merely a restatement of the classical intractability of the hidden matching problem but represents a significant contribution that bridges multiple foundational concepts in quantum machine learning. Thank you for your careful consideration, and we hope these clarifications will help in re-evaluating the merit of our work.

- Eq (8): how can x appear as an unbound function variable on the LHS and as a bound variable on the RHS?

We thank the reviewer for finding this notational error on our part. x should not appear on the RHS. We fixed it in the revised version of the paper.

- Line 370: the use of Aaronson et al. is the very heart of the whole paper, yet this is not reproduced anywhere in the paper

For completeness, we now include a description of Aaronson’s U_x in the Appendix.

- Line 434: please remind me what non-uniform means in this context.

Non-uniform here means there does not need to be an efficient Turing machine that on input n outputs the quantum circuit for instance size n.

- Eq (9): the notation of dot and unfilled function brackets is not defined/explained.

Thank you for the remark. We explained the notation below Eq. 9.

- Lines 475-480: is unclear, especially given that there are supposed to be different random functions for each data-point.

Each data point corresponds to a specific function. The distinguisher evaluates the performance of the MF protocols based on the given function. If the MF protocols were effective on pseudorandom states (PRS), there would be a noticeable difference in performance: poor performance when the functions are truly random and good performance when they are pseudorandom. Since such a difference cannot occur, the MF protocols will also fail on pseudorandom functions. We further clarify the point in the main text too.

- Eq (11): if g_i(x) is of size n+1, doesn't this change the learning problem in unclear-ways, not least because the dimensions no longer match (2n + 1 != 2n + 2)

This change only affects the length of the output bitstring: instead of $(x, y, b) \in \{0,1\}^{2n+1}$, it becomes $(g_i(x), y, b) \in \{0,1\}^{2n+2}$. This increase of the length of the bitstring by 1 has no further consequences for the learning problem. In particular, the $(y,b)$ variables still follow the same probability distribution determined by the POVM $\Lambda_x$, so the learning problem remains fundamentally the same.

- Eq (29): \pi_x(f) -> \pi_x(f^{(k)})

We thank the reviewer for finding this typo, we fixed it in the revised version.

- Line 787: is query access -> has query acces

We thank the reviewer for finding this error, we fixed it in the revised version

- Lines 157-159 is unclear

Currently is says:

”Directly applying these techniques to our learning setting that is focused on learning a $2^n$-outcome POVM by estimating the probability of each possible measurement outcome $j \in \{1,2,...,2^n\}$ requires exponential precision $\epsilon$, achievable only with an exponential amount of resources.”

To provide more clarity, we changed it to

“As we want to learn distribution associated to a $2^n$-outcome POVM with an $\epsilon$ error in TV, directly applying these techniques to estimate each of the $2^n$ outcomes would require an exponential precision for each. In their upper bound estimates, this results in the requirement of an exponential number of samples.

We hope this is clearer.

- Lines 205-210 claims a significant difference between this work and Jerbi et al.'s, but given the above characterization it is not clear that this is the case.

In Jerbi et al., the target is a quantum state $U|\psi\rangle$, and the goal is to learn the unitary U. Measurements are performed on the evolved state $U|\psi\rangle$, rather than on the initial state $|\psi\rangle$ alone. This distinction is critical and highlights a fundamental difference between the two works.

- Line 229 introduces f', why the prime?:

We thank the reviewer for noticing this typo, we removed the prime.

- \pi_x is not anywhere clearly connected to \Lamda_x

$\pi_x$ is a probability distribution over the bitstring $(x, y, b) \in \{0, 1\}^{2n+1}$. Specifically, the probability distribution for the $(y,b)$ variables corresponds directly to the outcome of applying the POVM $\Lambda_x$ on the input state $|\psi_f\rangle$. This establishes a clear link between $\pi_x$ and $\Lambda_x$ . We also highlight this in Section 3.1 below Definition 7.

- z and x are used inconsistently/confusingly in multiple places

This issue has been resolved by clarifying the notation. We now denote j as the orthonormal basis of the POVM, and $z$ as the label for the quantum states, specifically $z = (x, y, b)$.

- Eq (3) and Eq (5): the training data should not include x, perhaps g_i(x) is somehow meant (however see below)?

We highlight in Appendix A that there are multiple scenarios to consider. In particular, $g_i(x)$ can be any function of x that "leaks" information about $x$. One particularly simple to understand example is $g_i(x) = x$, which we have chosen to go with in the main text. We kindly refer to Appendix A for further details.

- Eq (3) and Eq (5): (y, b) ~ \pi_x and not (x,y,b)

For how it is defined $\pi_x$, the correct notation is indeed $(x,y,b)\sim\pi_x$. However, note that only $(y,b)$ follows the probability distribution given by the POVM $\Lambda_x$ on the input states $|\psi_f\rangle$

- Line 285: perhaps \Tilde{\pi}x should be \Tilde{\pi}{T_x} since the x dependence is surely only through T_x.

Of course the measure first protocol (and the fully quantum too) only receives information about $x$ through $T_x$. However we feel it would overcomplicate the notation to put $\Tilde{\pi}_{T_x}$ instead of $\Tilde{\pi}_x$.

- Theorem 5: What are the assumptions of Yao's principle? Are they satisified?

We refer to Yao principle as stated in, for example, https://nerva.cs.uni-bonn.de/lib/exe/fetch.php/teaching/ws1819/vl-aau/lecturenotes05.pdf. The assumptions are that the variables $\mathbb{A}$ and $\mathbb{X}$ are random variables following a probability distribution over the set $\mathcal{A}$ and $\mathcal{X}$ respectively. Our setting perfectly matches these conditions.

- Line 810: How can Bob output 1 when y is in R_f(x) without knowledge of f?

The reviewer appears to be referring to a step in the "distinguisher algorithm," whose goal is to differentiate between truly random and pseudorandom phase states. However, there seems to be a misunderstanding, as there is no "Bob" present in this context. We can understand the source of the confusion, as we do relate the performance of the distinguisher algorithm to the lower bounds of the Hidden Matching (HM) problem. Nevertheless, the distinguisher algorithm itself is not situated within the communication complexity setup of the HM problem.

Importantly, the use of pseudorandom states and distinguisher algorithms is a key distinction that sets our result apart from being essentially a restatement of the intractability of the HM problem. Finally, we note that the distinguisher is provided with knowledge of both f and x, and can thus efficiently check whether y is in $R_f(x)$.

- How can my following perceived weakness from above be remedied: "This is a difference between data and not really about a separation between interesting algorithmic classes."

We agree that our results can be interpreted as demonstrating a separation in solving a learning task based on the type of data provided (classical vs quantum). However, we do not view this as a weakness of our work. On the contrary, the converse claim -- that there is no separation in value -- is precisely at the core of the "measure first, ask questions later" approach, which we set out to investigate and challenge. Addressing this separation is a significant and timely question within the quantum machine learning (QML) community, as highlighted in our general response above. We believe our work contributes to this ongoing discussion by providing a rigorous framework and evidence for when and why such separations emerge. To properly investigate this, it is necessary to study two classes of algorithms: one that can access the full quantum states and another that only receives classical descriptions of these states. Importantly, the classical description cannot be tailored to the specific concept being learned; otherwise, the learning task could be effectively solved at the measurement stage, negating the need for further analysis. This constraint underscores the significance and the necessity to study the two "algorithmic classes" (i.e., measure-first vs fully-quantum) as defined in our paper.

- Is my understanding correct that the essence of the separation between the two classes boils down to the inability to compress the unseen quantum data during deployment time? What would happen if the measurement restriction during training were modified to allow the measurements to depend on the labels? What would happen if the measurement restriction during training were modified to allow the measurements to depend on the labels?

We agree with the reviewer’s observation that the separation result stems from the measurement restrictions during deployment. However, we do not view this as a significant limitation of our results. In fact, previous notable works [2,3] have shown that fixed measurement schemes during deployment can still yield highly powerful models, challenging the perceived necessity of quantum computation and information in quantum machine learning (QML). Our primary goal was to examine the limitations of common MF protocols found in the literature, and we demonstrate that a separation exists for these variants of MF protocols. While a very interesting related question lies beyond the scope of our work, exploring how far "quasi"-MF schemes can go is a natural next step. We have also given thought to this direction and have intuition that separations may also be established in more general cases -- e.g., when the deployment involves a fully quantum strategy (rather than a "measure first, ask later" scheme). However, proving such separations formally would require significant additional work and novel results, which fall outside the current scope of this paper. Lastly, we note that our separation result holds even when measurements are performed on multiple input states, and we have clarified this point in the revised version of the paper.

- Line 289: Why is the "more general" case not studied, when it is arguably much more interesting than the restrictions under consideration?

We believe that our current result already makes a significant contribution by demonstrating a learning separation between models that are of particular interest to the community. This addresses what we consider to be the principal and most fundamental question in this context. The more general cases are natural and obvious follow-ups, which we fully intend to explore in future work.

For different reasons, we must respectfully disagree with the assessment that our results are essentially a restatement of the intractability of the Hidden Matching (HM) problem. While we completely agree that we reduce the intractability of a learning problem to a lower bound in communication complexity to derive our result, we do not see this as a weakness per se, as the reduction itself is far from trivial. In fact, we would argue that reducing to a known separation is not inherently a limitation—after all, many foundational separations in quantum computing rely on reductions to established claims.

The reviewer’s statement appears to frame this as a shortcoming, and we interpret this to mean that the reduction is considered straightforward or uninteresting. On this point, we must respectfully disagree. Our results specifically address physical quantum states that are efficiently preparable on quantum hardware. It is important to note that the HM problem arises in the context of communication complexity, and its lower bounds do not directly apply in scenarios where states are efficiently preparable. In particular, if the quantum state can be efficiently prepared, the preparation circuit itself can be treated as a message in the communication protocol, thereby bypassing the standard lower bounds.

To address this challenge, we rigorously demonstrated that the learning problem remains classically intractable even for efficiently preparable states by leveraging pseudo-random states and imposing a time efficiency requirement on the learner—a standard consideration in machine learning contexts. This additional step is crucial because, without it, the separation would have no meaningful relevance to real-world cases. With it, however, we provide compelling evidence that such separations extend more broadly, as long as the states under consideration are sufficiently “rich”.

Furthermore, due to our focus on a machine learning scenario, there are additional key aspects that set our work apart from the traditional HM problem: our analysis emphasizes both average-case correctness and robustness to noise, which are critical considerations in practical learning tasks that are not considered in the HM problem. Covering all these common ML considerations in our result required us to apply all the various techniques of the sub-fields listed out by the reviewer in the “strenghts” section.

In summary, we believe that the reduction we employ is not only nontrivial but also highly relevant to practical contexts, offering insights beyond what a straightforward restatement of the HM problem would provide. We hope this explanation helps clarify our perspective.

We are also surprised by the score of 1 for soundness (which we understand as technical correctness and absence of mistakes), as we are not aware of any errors in our proofs, and the reviewer has not identified any specific issues (we find that the “unclear statements or mistakes” listed by the reviewer were mostly typos and things we could’ve explained more clearly).

We thank the reviewer for their thoughtful feedback and appreciate their acknowledgment of our understanding of the various techniques employed in our proof. While we are naturally disappointed that the reviewer finds our results "unsurprising," we believe we can understand how one might arrive at this opinion. At first glance, it may appear that we simply compare a stronger model with a weaker one and then demonstrate the expected result—that they differ. However, we respectfully argue that the situation is far more nuanced, and we would like to take this opportunity to clarify why we believe our results are more surprising than they may initially seem.

The primary critique seems to be that our measure-first (MF) protocol, as defined, is too “hamstrung” (which we take to mean deliberately weakened) in comparison to the fully-quantum (FQ) protocol. While we understand this perspective, we would like to emphasize that recent advancements in the field have demonstrated that establishing a clear separation between these two protocols is far more challenging than it might initially seem.

To illustrate, it is worth beginning with the remarkable successes in the literature on shadow tomography and classical shadows. These breakthroughs have led leading researchers in the field to suggest that, in many cases, one can “measure first, ask questions later.” Indeed, a statement of this nature made during a conference explicitly inspired us to investigate the matter further.

Reflecting on the general evidence supporting this sentiment, MF protocols have shown surprisingly strong capabilities in a range of physical learning tasks. For instance, in a recent milestone work on predicting properties of gapped Hamiltonians using a variant of an MF protocol [2], it was shown that an algorithm employing a fixed measurement procedure (i.e., classical shadows of ground states [1]) could accurately predict numerous observables on the ground states of Hamiltonians.

Similarly, we would like to draw the reviewer’s attention to another recent work by experts in the field [3]. This study demonstrated that for many quantum input data learning tasks, classical convolutional neural networks, provided with classical shadow representations of quantum states as input (i.e., a MF protocol), achieved performance levels comparable to quantum neural networks (i.e., a FQ protocol). In fact, the authors explicitly raised the question of whether any task could conclusively demonstrate a clear separation between classical and quantum approaches.

To further contextualize this, consider our setting in quantum machine learning. For example, if in our task the labels corresponded to expectation values of local observables, there would be no separation between MF and FQ protocols due to the provable guarantees of classical shadows [1]. Thus, in light of this substantial body of evidence, we argue that expecting a provable difference between MF and FQ protocols is not obvious. Moreover, the challenge of identifying a task that does exhibit such a difference is not straightforward.

We hope this clarification inspires the reviewer to appreciate our perspective and see further value in our work. Even if the final outcome aligns with what one might naively expect, it is important to note that recent (and often surprising) results in the field suggest otherwise.

References: [1] Huang, Hsin-Yuan, et al. "Provably efficient machine learning for quantum many-body problems." Science 377.6613 (2022).

[2] Huang, Hsin-Yuan, et al. "Quantum advantage in learning from experiments." Science 376.6598 (2022).

[3] Bermejo, Pablo, et al. "Quantum convolutional neural networks are (effectively) classically simulable." arXiv preprint arXiv:2408.12739 (2024).