Limitations of measure-first protocols in quantum machine learning

Authors: Casper Gyurik, Riccardo Molteni, Vedran Dunjko
Primary area: learning theory
Keywords: quantum machine learning, machine learning, learning separation

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 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.

Decision: reject
Reviewer scores: 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1730088066883

thread_type:
official_review

<thread_object>
creator: reviewer_n6yc

<content>
summary:
In the paper entitled "Limitations of Measure-First Protocols in Quantum Machine Learning," the authors constructed a learning task based on quantum phase states, which provides a separation between the full quantum protocol and classical-shadow-based protocols in terms of sample complexity. From my understanding, the construction is fundamentally based on the fact that $FBQP/qpoly\neq FBQP/poly$, while the authors claimed that they successfully achieved the worst-to-average case reduction. In summary, this work theoretically studied the differences between two popular quantum machine learning paradigms, which advances our understanding of quantum models to some extent.

strengths:
1. This paper clearly demonstrates its main results and the comparison to related work.
2. The authors rigorously proved the separation of sample and running time by implementing a polynomial reduction to the Hidden Matching problem, which provides new insights in the field of quantum machine learning.

weaknesses:
Here are some weaknesses and questions on this paper.
1. Is the proved separation just an instance of $FBQP/qpoly \neq FBQP/poly$ [S. Aaronson et al., 2023], where $FBQP/poly$ represents classical shadow-based algorithms (including measure multiple states by Bell measurement).
2. 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 $FBQP/qpoly \neq FBQP/poly$.
3. 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.

questions:
1. It would be helpful to provide the explicit construction of U_x (also the learned measurement operator).
2. 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).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619829365

thread_type:
official_review

<thread_object>
creator: reviewer_mm3w

<content>
summary:
This paper investigates a fundamental question in quantum machine learning (QML): whether quantum advantages can persist when quantum data is first measured and converted to classical information before processing. The authors establish a formal separation between two types of QML protocols:

1. "Measure-first" protocols: Those that first measure quantum states using a fixed measurement strategy (though possibly complex and coherent) before processing

2. "Fully-quantum" protocols: Those that can process quantum states coherently and maintain quantum data throughout the entire learning & deployment process

The main contribution is proving that there exists a learning task involving quantum measurements where measure-first protocols provably require exponentially more data than fully-quantum protocols, even when restricted to efficiently preparable quantum states. This is shown by constructing a specific learning problem based on the Hidden Matching problem and quantum pseudorandom states.

strengths:
- The paper addresses a fundamental question about the nature of quantum advantages in machine learning and provides concrete evidence that some quantum tasks inherently require maintaining quantum states throughout processing.

- The proofs are rigorous and combine multiple techniques from quantum computing, cryptography, and communication complexity.

- Unlike previous work, the separation holds even for average-case performance (not just worst-case), efficiently preparable quantum states (not just arbitrary states), and scenarios with experimental noise and errors.

weaknesses:
- While the paper discusses robustness to noise theoretically, no numerical simulations or experimental results are provided to demonstrate the practicality of the proposed protocols.

- While the separation is proven rigorously, it relies on a somewhat artificial learning task constructed specifically to demonstrate the separation. It would be valuable to understand if similar separations exist for more natural learning problems.

- The paper focuses on a specific type of quantum learning problem involving Hidden Matching. It remains unclear how broadly these limitations of measure-first protocols apply to other quantum learning scenarios.

questions:
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.

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 lead to the separation between "measurement-first" vs "fully quantum" methods?

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730773762556

thread_type:
official_review

<thread_object>
creator: reviewer_ryau

<content>
summary:
The authors design a quantum machine learning task that exhibits a sample and time complexity separation between two classes of quantum algorithms acting on input training data consisting of quantum data and classical labels with the goal of producing a classical description of a quantum circuit that can then be deployed on unseen quantum data to produce samples from a distribution related to the training data. The main difference between the two classes of quantum algorithms is that the more powerful class is allowed to process the input quantum-classical training data in "one go", while the weaker class is hamstrung to first turn the quantum data into classical data, one training data-point at a time, without looking at the classical labels before being allowed to process this now-classical data together with the classical labels through a quantum algorithm to produce a classical description of the deployment quantum circuit. At deployment time, the weaker class is then further forced to measure the unseen quantum data before feeding it into the quantum circuit produced at the end of the training phase.

Unsurprisingly, there is a complexity separation between the fully quantum algorithm and the hamstrung quantum algorithm which seems to essentially be a restatement of the intractability of the Hidden Matching Communication problem. Finally, the authors claim to extend the complexity separation to efficiently preparable training data sets by using pseudo-random functions.

strengths:
Originality: The authors venture to create a quantum machine learning task with average-case complexity separations between measurement-first and fully-quantum quantum algorithms.
Quality: The authors seem to know the techniques of the sub-field well (including those related to POVMs, HM problem, Yao's principle, QPRFs, ...), as well as other related work (including classical shadows, shadow tomography, ...)
Clarity: The authors do try to provide both diagrammatic, high-level and low-level explanations.
Significance: The authors do aim to produce a significant result by hoping to shed light on the role of information loss due to measurement when performing quantum machine learning in the average-case setting with realistic training data.

weaknesses:
Unfortunately, the high aims and strong potential of the "Strengths" section, seem not to be met. I believe this is mainly due to the overly restrictive setting of the weakened class of "measurement-first" quantum algorithms. The most confusing and vague constraint is: "that the measurement strategy cannot depend on the specific target concept". Looking at Definition 5 and 7 for clarity this seems to be the following constraint on the hamstrung class:

Training:
Quantum data + classical labels -----[Point-wise measurement]------> M(Quantum data) + classical labels = Classical data + classical labels ----[Quantum Algorithm]----> Classical description of Quantum circuit

Deployment:
Quantum data -----[Point-wise measurement]------> M(Quantum data) = Classical data ----[Quantum Algorithm given by circuit above]----> Sample

Therefore it seems that the main difference between the two classes is that the weaker one actually only operates on classical data during both training and deployment while the stronger one is allowed to operate on quantum data. This is a difference between data capacity and not really about a separation between interesting algorithmic classes.

Secondly, there does seem to be quite a few unclear statements or mistakes:

* Lines 157-159 is unclear
* 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.
* Line 229 introduces f', why the prime?
* \pi_x is not anywhere clearly connected to \Lamda_x
* z and x are used inconsistently/confusingly in multiple places
* Eq (3) and Eq (5): the training data should not include x, perhaps g_i(x) is somehow meant (however see below)?
* Eq (3) and Eq (5): (y, b) ~ \pi_x and not (x,y,b)
* Line 285: perhaps \Tilde{\pi}_x should be \Tilde{\pi}_{T_x} since the x dependence is surely only through T_x
* Eq (8): how can x appear as an unbound function variable on the LHS and as a bound variable on the RHS?
* 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
* Line 434: please remind me what non-uniform means in this context.
* Eq (9): the notation of dot and unfilled function brackets is not defined/explained.
* Lines 475-480: is unclear, especially given that there are supposed to be different random functions for each data-point.
* 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)
* Eq (29): \pi_x(f) -> \pi_x(f^{(k)})
* Line 787: is query access -> has query access

questions:
* 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."
* 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? Or if we must keep them blind of the labels, joint measurements across all data-points were allowed?
* Line 289: Why is the "more general" case not studied, when it is arguably much more interesting than the restrictions under consideration?
* Theorem 5: What are the assumptions of Yao's principle? Are they satisified?
* Line 810: How can Bob output 1 when y is in R_f(x) without knowledge of *f*?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733311095223

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
Dear reviewers, dear Area Chairs,

We sincerely appreciate the invaluable feedback provided by the reviewers. Their insightful comments have not only allowed us to clarify key aspects of our work but also to enhance it significantly in the final revised version.

In particular, we have made the following improvements to the manuscript:

1) We clarified how our results could, in principle, extend to a broader scenario where the advice states are ground states of local Hamiltonians rather than phase states. While we emphasize this point in the Conclusion, we also underscore here that our work represents the first rigorous separation between measure-first (MF) and fully-quantum (FQ) protocols in a supervised learning task.

2) To further illustrate the relevance of our findings, we connected them to existing literature highlighting the significant power of MF protocols. Additionally, we expanded the manuscript with Appendix D, which includes two illustrative examples of MF learning protocols. These examples showcase the strong capabilities enabled by the MF learning algorithm, and in discussing their limitations, we underline how our work significantly advances beyond the hidden matching (HM) problem and Aaronson’s results [1]. We respectfully believe that we have thoroughly expanded on the quality and significance of the machine learning task, the naturalness and capacities of the learning algorithms, and how the task highlights performance distinctions between them, both in our responses and the revised manuscript.

3) We made several adjustments throughout the manuscript to improve readability and enhance the clarity of the text.


We hope this summary effectively conveys our dedicated efforts to refine the manuscript in response to the reviewers' valuable feedback.  Once again, we are truly grateful to the reviewers for their input.


[1]: Aaronson et al., A Qubit, a Coin, and an Advice String Walk Into a Relational Problem, 2023
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studied limitations for quantum machine learning algorithms that use fixed measurement schemes on the input quantum states. This is motivated by both recent advances in randomized measurement protocols as well as machine learning for quantum states. In particular, the authors proved limitations of measure-first protocols in the average case, improving on the state-of-the-art which only focuses on worst-case scenarios.

There were adequate discussions during the rebuttal, in particular between the authors and the reviewer RYau. Technical contents were clarified and the paper was subsequently improved by the authors. However, the current results are more like extending the hidden matching problem and contributing to complexity theory (worse-case to average-case), with its nature being more as a quantum information problem than a machine learning problem. The paper is also purely theoretical, and other reviewer also agreed with its limited practical application. Considering all, the decision is to reject this paper at ICLR 2025.

For future versions of the paper, if the authors continue to submit to machine learning venues, more efforts are solicited for its connection to machine learning, in particular practical applications. Otherwise it might suit better to a quantum information/computation venue.