Research map / Learning theory and algorithms / Prediction and decision losses

Limitations of measure-first protocols in quantum machine learning

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Adaptive testing and experiments · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that quantum learners which measure input quantum states with a fixed, data-independent measurement scheme ("measure-first") need exponentially many samples for a learning task that fully-quantum protocols solve efficiently, even for efficiently preparable pseudorandom phase states.

Problem

Whether quantum machine learning on quantum data needs fully coherent processing, or whether a fixed measure-first scheme (such as classical shadows) producing classical descriptions of the states is sufficient, particularly in the average-case and for physically realizable states.

Approach

Constructs a learning-a-measurement concept class over phase states, using the Hidden Matching one-way communication lower bound (via Yao's principle) to show measure-first protocols fail on average, then uses quantum-secure pseudorandom functions and a distinguisher argument to extend the separation to efficiently preparable states.

Key results

• Theorem 3.3: the concept class of learning a measurement over phase states is not measure-first learnable for (1-ϵ)(1-δ) > 7/8, while it is (0,0,1)-fully-quantum learnable (Proposition 3.2).
• Theorem 3.6: the separation persists when inputs are restricted to pseudorandom phase states, which are efficiently preparable, under quantum-secure PRFs.

Measured effects reported in the paper

Surprising findings

• Measure-first protocols fail even with inefficient algorithms or exponentially many training points, since the communication lower bound holds regardless of computational resources.

Limitations

• Separation relies on a specific constructed concept class rather than a natural ML task.
• Proof of the efficiently preparable case depends on the existence of quantum-secure pseudorandom functions (complexity assumption).
• Lower bound holds for the specific learning problem; general measure-first limitations are not characterized beyond it.

Experimental setup

Baselines: Grier et al. 2024 worst-case lower bounds Cheng et al. 2016 learning POVMs Gong & Aaronson 2023 shadow tomography for K-outcome POVMs Jerbi et al. 2023 incoherent learning

Builds on: classical shadows Hidden Matching communication complexity Aaronson et al. 2024 relational problems separation pseudorandom phase states (Brakerski & Shmueli) PAC learning

Closest papers by meaning

• Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm (NeurIPS 2026 · similarity 0.87)
• Understanding Generalization in Quantum Machine Learning with Margins (ICML 2025 · similarity 0.87)
• On the Relation between Trainability and Dequantization of Variational Quantum Learning Models (ICLR 2025 · similarity 0.86)
• Purest Quantum State Identification (NeurIPS 2025 · similarity 0.85)
• Exploring channel distinguishability in local neighborhoods of the model space in quantum neural networks (ICLR 2025 · similarity 0.85)
• Exponential Quantum Communication Advantage in Distributed Inference and Learning (NeurIPS 2024 · similarity 0.85)