Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.12618

Limitations of measure-first protocols in quantum machine learning

Casper Gyurik, Riccardo Molteni, Vedran Dunjko

Published Nov 21, 2023• 14 citations
arXivHTMLPDF

Abstract

In recent works, much progress has been made with regards to so-called randomized measurement strategies, which include the famous methods of classical shadows and shadow tomography. In such strategies, unknown quantum states are first measured (or ``learned''), to obtain classical data that can be used to later infer (or ``predict'') some desired properties of the quantum states. Even if the used measurement procedure is fixed, surprisingly, estimations of an exponential number of vastly different quantities can be obtained from a polynomial amount of measurement data. This raises the question of just how powerful ``measure-first'' strategies are, and in particular, if all quantum machine learning problems can be solved with a measure-first, analyze-later scheme. This paper explores the potential and limitations of these measure-first protocols in learning from quantum data. We study a natural supervised learning setting where quantum states constitute data points, and the labels stem from an unknown measurement. We examine two types of machine learning protocols: ``measure-first'' protocols, where all the quantum data is first measured using a fixed measurement strategy, and ``fully-quantum'' protocols where the measurements are adapted during the training process. Our main result is a proof of separation. We prove that there exist learning problems that can be efficiently learned by fully-quantum protocols but which require exponential resources for measure-first protocols. Moreover, we show that this separation persists even for quantum data that can be prepared by a polynomial-time quantum process, such as a polynomially-sized quantum circuit. Our proofs combine methods from one-way communication complexity and pseudorandom quantum states. Our result underscores the role of quantum data processing in machine learning and highlights scenarios where quantum advantages appear.

DOI
10.48550/arxiv.2311.12618

Related papers

Evidence of Quantum Machine Learning Advantage with Tens of Noisy Qubits

Onur Danaci, Yash J. Patel, Riccardo Molteni +3 more

Learning problems involving quantum data are natural candidates for demonstrating an advantage in quantum machine learning. Recent results indicate that, for certain tasks and under noiseless conditions, coherent processing of quantum data outperforms fixed-measurement schemes followed by classical processing. It remained uncertain whether this performance gap persists at a finite scale, and in the presence of noise that is unavoidable with current quantum devices. In this work, we present simulations and analysis of the performance of existing hardware on a learning problem known to exhibit asymptotic advantage, now subjected to noisy quantum data. Comparing coherent quantum processing directly against fixed-measurement schemes, our results demonstrate a clear performance separation at a scale of just 30 to 40 noisy qubits. Already at this scale, the fundamental bottleneck is no longer classical computation but data acquisition; matching the noisy coherent protocol with measure-first strategies would still require months or even years of measurements. By systematically evaluating hardware constraints such as state preparation, gate errors, readout errors, connectivity, and coherence times, we provide evidence that a demonstration of such a strong learning advantage is accessible on near-term devices.

quant-pharXiv:2605.21346•May 21, 2026•2 citations

Advantage of Entangled Learning Rules in Quantum Measurement Class Learning

Arka Prabha Das, Abram Magner

Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).

quant-pharXiv:2610.07328•Oct 7, 2026•0 citations

Exponential quantum advantages in learning quantum observables from classical data

Riccardo Molteni, Casper Gyurik, Vedran Dunjko

Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that $$BQP$$ B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.

arXiv:2405.02027•npj Quantum Information•Jan 10, 2026•38 citations

Quantum machine learning for state tomography using classical data

S. Jabeen, Dmytro Kurdydyk, Aadi Palnitkar +3 more

Reconstructing quantum states from measurement data represents a formidable challenge in quantum information science, especially as system sizes grow beyond the reach of traditional tomography methods. While recent studies have explored quantum machine learning (QML) for quantum state tomography (QST), nearly all rely on idealized assumptions, such as direct access to the unknown quantum state as quantum data input, which are incompatible with current hardware constraints. In this work, we present a QML-based tomography protocol that operates entirely on classical measurement data and is fully executable on noisy intermediate-scale quantum (NISQ) devices. Our approach employs a variational quantum circuit trained to reconstruct quantum states based solely on measurement outcomes. We test the method in simulation, achieving high-fidelity reconstructions of diverse quantum states, including GHZ states, spin chain ground states, and states generated by random circuits. The protocol is then validated on quantum hardware from IBM and IonQ. Additionally, we demonstrate accurate tomography is possible using incomplete measurement bases, a crucial step towards scaling up our protocol. Our results in various scenarios illustrate successful state reconstruction with fidelity reaching 90% or higher. To our knowledge, this is the first QML-based tomography scheme that has been implemented on real quantum processors using exclusively classical measurements. This work establishes the feasibility of QML-based tomography on current quantum platforms and offers a scalable pathway for practical quantum state reconstruction.

arXiv:2507.01246•Quantum Machine Intelligence•Apr 2, 2026•1 citation

Exponential speedup in measurement property learning with post-measurement states

Zhenhuan Liu, Qi Ye, Zhenyu Cai +1 more

Learning properties of quantum states and channels is known to benefit from resources such as entangled operations, auxiliary qubits, and adaptivity, whereas the resource structure of measurement learning, namely, learning properties of quantum measurement operators, remains poorly understood. In this work, we identify a measurement learning task for which access limited to classical measurement outcomes leads to an exponential lower bound on the query complexity, established via a distinguishing task between a genuine quantum projective measurement and a purely classical random number generator. Remarkably, this hardness persists even when arbitrary entangled operations, auxiliary systems, and fully adaptive strategies are allowed, indicating that conventional resources for state and channel learning are ineffective in this task. In contrast, when access to the post-measurement quantum state is available, the same task can be solved with constant query complexity using a simple measuring-twice protocol, without requiring resources that are useful for state and channel learning. Our results reveal post-measurement states as a qualitatively new and decisive resource for measurement learning, suggesting potential implications for the design of practical quantum certification protocols.

quant-pharXiv:2602.22126•Feb 26, 2026•1 citation

Few measurement shots challenge generalization in learning to classify entanglement

Leonardo Banchi, Jason L. Pereira, Marco Zamboni

The ability to extract general laws from a few known examples depends on the complexity of the problem and on the amount of training data. In the quantum setting, the learner's generalization performance is further challenged by the destructive nature of quantum measurements that, together with the no-cloning theorem, limits the amount of information that can be extracted from each training sample. In this paper we focus on hybrid quantum learning techniques where classical machine-learning methods are paired with quantum algorithms and show that, in some settings, the uncertainty coming from a few measurement shots can be the dominant source of errors. We identify an instance of this possibly general issue by focusing on the classification of maximally entangled vs. separable states, showing that this toy problem becomes challenging for learners unaware of entanglement theory. Finally, we introduce an estimator based on classical shadows that performs better in the big data, few copy regime. Our results show that the naive application of classical machine-learning methods to the quantum setting is problematic, and that a better theoretical foundation of quantum learning is required.

arXiv:2411.06600•Nov 10, 2024•2 citations
In recent works, much progress has been made with regards to so-called randomized measurement strategies, which include the famous methods of classical shadows and shadow tomography. In such strategies, unknown quantum states are first measured (or learned''), to obtain classical data that can be used to later infer (or predict'') some desired properties of the quantum states. Even if the used measurement procedure is fixed, surprisingly, estimations of an exponential number of vastly different quantities can be obtained from a polynomial amount of measurement data. This raises the question of just how powerful measure-first'' strategies are, and in particular, if all quantum machine learning problems can be solved with a measure-first, analyze-later scheme. This paper explores the potential and limitations of these measure-first protocols in learning from quantum data. We study a natural supervised learning setting where quantum states constitute data points, and the labels stem from an unknown measurement. We examine two types of machine learning protocols: measure-first'' protocols, where all the quantum data is first measured using a fixed measurement strategy, and ``fully-quantum'' protocols where the measurements are adapted during the training process. Our main result is a proof of separation. We prove that there exist learning problems that can be efficiently learned by fully-quantum protocols but which require exponential resources for measure-first protocols. Moreover, we show that this separation persists even for quantum data that can be prepared by a polynomial-time quantum process, such as a polynomially-sized quantum circuit. Our proofs combine methods from one-way communication complexity and pseudorandom quantum states. Our result underscores the role of quantum data processing in machine learning and highlights scenarios where quantum advantages appear.
Learning problems involving quantum data are natural candidates for demonstrating an advantage in quantum machine learning. Recent results indicate that, for certain tasks and under noiseless conditions, coherent processing of quantum data outperforms fixed-measurement schemes followed by classical processing. It remained uncertain whether this performance gap persists at a finite scale, and in the presence of noise that is unavoidable with current quantum devices. In this work, we present simulations and analysis of the performance of existing hardware on a learning problem known to exhibit asymptotic advantage, now subjected to noisy quantum data. Comparing coherent quantum processing directly against fixed-measurement schemes, our results demonstrate a clear performance separation at a scale of just 30 to 40 noisy qubits. Already at this scale, the fundamental bottleneck is no longer classical computation but data acquisition; matching the noisy coherent protocol with measure-first strategies would still require months or even years of measurements. By systematically evaluating hardware constraints such as state preparation, gate errors, readout errors, connectivity, and coherence times, we provide evidence that a demonstration of such a strong learning advantage is accessible on near-term devices.
Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).
Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that BQPBQPBQP B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.
Reconstructing quantum states from measurement data represents a formidable challenge in quantum information science, especially as system sizes grow beyond the reach of traditional tomography methods. While recent studies have explored quantum machine learning (QML) for quantum state tomography (QST), nearly all rely on idealized assumptions, such as direct access to the unknown quantum state as quantum data input, which are incompatible with current hardware constraints. In this work, we present a QML-based tomography protocol that operates entirely on classical measurement data and is fully executable on noisy intermediate-scale quantum (NISQ) devices. Our approach employs a variational quantum circuit trained to reconstruct quantum states based solely on measurement outcomes. We test the method in simulation, achieving high-fidelity reconstructions of diverse quantum states, including GHZ states, spin chain ground states, and states generated by random circuits. The protocol is then validated on quantum hardware from IBM and IonQ. Additionally, we demonstrate accurate tomography is possible using incomplete measurement bases, a crucial step towards scaling up our protocol. Our results in various scenarios illustrate successful state reconstruction with fidelity reaching 90% or higher. To our knowledge, this is the first QML-based tomography scheme that has been implemented on real quantum processors using exclusively classical measurements. This work establishes the feasibility of QML-based tomography on current quantum platforms and offers a scalable pathway for practical quantum state reconstruction.
Learning properties of quantum states and channels is known to benefit from resources such as entangled operations, auxiliary qubits, and adaptivity, whereas the resource structure of measurement learning, namely, learning properties of quantum measurement operators, remains poorly understood. In this work, we identify a measurement learning task for which access limited to classical measurement outcomes leads to an exponential lower bound on the query complexity, established via a distinguishing task between a genuine quantum projective measurement and a purely classical random number generator. Remarkably, this hardness persists even when arbitrary entangled operations, auxiliary systems, and fully adaptive strategies are allowed, indicating that conventional resources for state and channel learning are ineffective in this task. In contrast, when access to the post-measurement quantum state is available, the same task can be solved with constant query complexity using a simple measuring-twice protocol, without requiring resources that are useful for state and channel learning. Our results reveal post-measurement states as a qualitatively new and decisive resource for measurement learning, suggesting potential implications for the design of practical quantum certification protocols.
The ability to extract general laws from a few known examples depends on the complexity of the problem and on the amount of training data. In the quantum setting, the learner's generalization performance is further challenged by the destructive nature of quantum measurements that, together with the no-cloning theorem, limits the amount of information that can be extracted from each training sample. In this paper we focus on hybrid quantum learning techniques where classical machine-learning methods are paired with quantum algorithms and show that, in some settings, the uncertainty coming from a few measurement shots can be the dominant source of errors. We identify an instance of this possibly general issue by focusing on the classification of maximally entangled vs. separable states, showing that this toy problem becomes challenging for learners unaware of entanglement theory. Finally, we introduce an estimator based on classical shadows that performs better in the big data, few copy regime. Our results show that the naive application of classical machine-learning methods to the quantum setting is problematic, and that a better theoretical foundation of quantum learning is required.