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:2007.04900 · Physical Review Letters

Reformulation of the No-Free-Lunch Theorem for Entangled Datasets

Kunal Sharma, Marco Cerezo, Zoë Holmes, Łukasz Cincio, Andrew T. Sornborger, Patrick J. Coles

Published Feb 18, 2022• 74 citations
arXivHTMLPDF

Abstract

The no-free-lunch (NFL) theorem is a celebrated result in learning theory that limits one's ability to learn a function with a training dataset. With the recent rise of quantum machine learning, it is natural to ask whether there is a quantum analog of the NFL theorem, which would restrict a quantum computer's ability to learn a unitary process with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this Letter, we show that entangled datasets lead to an apparent violation of the (classical) NFL theorem. This motivates a reformulation that accounts for the degree of entanglement in the training set. As our main result, we prove a quantum NFL theorem whereby the fundamental limit on the learnability of a unitary is reduced by entanglement. We employ Rigetti's quantum computer to test both the classical and quantum NFL theorems. Our Letter establishes that entanglement is a commodity in quantum machine learning.

DOI
10.1103/physrevlett.128.070501

Related papers

Transition role of entangled data in quantum machine learning

Xinbiao Wang, Yuxuan Du, Zhuozhuo Tu +3 more

Entanglement serves as the resource to empower quantum computing. Recent progress has highlighted its positive impact on learning quantum dynamics, wherein the integration of entanglement into quantum operations or measurements of quantum machine learning (QML) models leads to substantial reductions in training data size, surpassing a specified prediction error threshold. However, an analytical understanding of how the entanglement degree in data affects model performance remains elusive. In this study, we address this knowledge gap by establishing a quantum no-free-lunch (NFL) theorem for learning quantum dynamics using entangled data. Contrary to previous findings, we prove that the impact of entangled data on prediction error exhibits a dual effect, depending on the number of permitted measurements. With a sufficient number of measurements, increasing the entanglement of training data consistently reduces the prediction error or decreases the required size of the training data to achieve the same prediction error. Conversely, when few measurements are allowed, employing highly entangled data could lead to an increased prediction error. The achieved results provide critical guidance for designing advanced QML protocols, especially for those tailored for execution on early-stage quantum computers with limited access to quantum resources.

arXiv:2306.03481•Nature Communications•May 2, 2024•31 citations

No Free Lunch for Quantum Machine Learning

Kyle Poland, Kerstin Beer, Tobias J. Osborne

The ultimate limits for the quantum machine learning of quantum data are investigated by obtaining a generalisation of the celebrated No Free Lunch (NFL) theorem. We find a lower bound on the quantum risk (the probability that a trained hypothesis is incorrect when presented with a random input) of a quantum learning algorithm trained via pairs of input and output states when averaged over training pairs and unitaries. The bound is illustrated using a recently introduced QNN architecture.

arXiv:2003.14103•Mar 31, 2020•70 citations

Exploring the Power of Entangled Data in Quantum Machine Learning

Xinbiao Wang, Yuxuan DU, Zhuozhuo Tu +3 more

Quantum entanglement is a key resource for achieving superiority of quantum computing.Currently, scientists are extensively focusing on how to integrate quantum entanglement into various components of quantum machine learning (QML) models, aiming to surpass the performance of traditional machine learning models.Notable successes include the use of entangled measurements [1][2][3] and entangled channels [4] , which have been shown to reduce query complexity or improve the prediction precision for specified QML tasks.Quantum entangled data, capable of encoding more information compared to classical data of the same size, is recognized for its potential to achieve quantum advantages.Nevertheless, the impact of the entanglement degree in quantum data on model performance remains a challenging and unresolved research question.Recently, Wang and collaborators [5] (Nat Commun 2024, 15, 3716) rigorously analyzed the impact of the entanglement degree of quantum data, the number and type of measurements, and the size of training dataset on the prediction error of QML models by establishing the quantum no-free-lunch (NFL) theorem.They consider tasks of quantum dynamics learning with entangled data, which is fundamental to many advanced quantum algorithms, as illustrated in Fig. 1.While conventional understanding suggests that entanglement mainly confers benefits to QML in terms of sample complexity [6,7] , this study demonstrates that the effect of the degree of entanglement on prediction error exhibits a dual effect, that is, whether quantum entanglement improves performance depends on the number of measurements allowed.With a sufficient number of measurements, increasing the entanglement degree in quan-

Wuhan University Journal of Natural Sciences•Jun 1, 2024•2 citations

Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem

Xinbiao Wang, Yuxuan Du, Kecheng Liu +3 more

The No-Free-Lunch (NFL) theorem, which quantifies problem- and data-independent generalization errors regardless of the optimization process, provides a foundational framework for comprehending diverse learning protocols' potential. Despite its significance, the establishment of the NFL theorem for quantum machine learning models remains largely unexplored, thereby overlooking broader insights into the fundamental relationship between quantum and classical learning protocols. To address this gap, we categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable and establish their NFL theorem. The exploited protocols, namely Classical Learning Protocols (CLC-LPs), Restricted Quantum Learning Protocols (ReQu-LPs), and Quantum Learning Protocols (Qu-LPs), offer varying levels of access to quantum resources. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs, contingent upon the orthogonality of quantum states and the diagonality of observables. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states, a distinctive physical feature inherent in quantum mechanics. Our findings not only deepen our understanding of quantum learning protocols' capabilities but also provide practical insights for the development of advanced quantum learning algorithms.

arXiv:2405.07226•May 12, 2024•7 citations

No-Free-Lunch Theorems for Tensor Network Machine Learning Models

Jing-Chuan Wu, Qi Ye, Dong-Ling Deng +1 more

Tensor network machine learning models have shown remarkable versatility in tackling complex data-driven tasks. Despite their promising performance, a comprehensive understanding of the underlying assumptions and limitations of these models is still lacking. Here we focus on the rigorous formulation of their no-free-lunch theorem, which is essential yet notoriously challenging to formalize for specific tensor network learning models. In particular, we rigorously analyze the generalization risks of learning target output functions from input data encoded in tensor network states. We first prove a no-free-lunch theorem for machine learning models based on matrix product states. Then we circumvent the challenging issue of calculating the partition function for a two-dimensional Ising model, and prove the no-free-lunch theorem for the case of two-dimensional projected entangled-pair states, by introducing the combinatorial method associated to the "puzzle of polyominoes." In addition, we rigorously establish an adversarial theorem that emerges naturally as a practical consequence of our no-free-lunch theorem. Our findings reveal the intrinsic limitations of tensor-network-based learning models in a rigorous fashion, and open up an avenue for future analytical exploration of both the strengths and limitations of quantum-inspired machine learning frameworks.

arXiv:2412.05674•Physical Review Letters•Nov 12, 2025•3 citations

On reducing the amount of samples required for training of QNNs: constraints on the linear structure of the training data

Alexander Mandl, Johanna Barzen, Frank Leymann +1 more

Abstract Training classical neural networks generally requires a large number of training samples. Using entangled training samples, Quantum Neural Networks (QNNs) have the potential to significantly reduce the amount of training samples required in the training process. However, to minimize the number of incorrect predictions made by the resulting QNN, it is essential that the structure of the training samples meets certain requirements. On the one hand, the exact degree of entanglement must be fixed for the whole set of training samples. On the other hand, training samples must be linearly independent and non-orthogonal. However, how failing to meet these requirements affects the resulting QNN is not fully studied. To address this, we extend the proof of the Quantum No-Free-Lunch theorem to (i) provide a generalization of the theorem for varying degrees of entanglement. This generalization shows that the average degree of entanglement in the set of training samples can be used to predict the expected quality of the QNN. Furthermore, we (ii) introduce new estimates for the expected accuracy of QNNs for moderately entangled training samples that are linearly dependent or orthogonal. Our analytical results are (iii) experimentally validated by simulating QNN training and analyzing the quality of the QNN after training.

arXiv:2309.13711•Quantum Machine Intelligence•Nov 4, 2025•4 citations
The no-free-lunch (NFL) theorem is a celebrated result in learning theory that limits one's ability to learn a function with a training dataset. With the recent rise of quantum machine learning, it is natural to ask whether there is a quantum analog of the NFL theorem, which would restrict a quantum computer's ability to learn a unitary process with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this Letter, we show that entangled datasets lead to an apparent violation of the (classical) NFL theorem. This motivates a reformulation that accounts for the degree of entanglement in the training set. As our main result, we prove a quantum NFL theorem whereby the fundamental limit on the learnability of a unitary is reduced by entanglement. We employ Rigetti's quantum computer to test both the classical and quantum NFL theorems. Our Letter establishes that entanglement is a commodity in quantum machine learning.
Entanglement serves as the resource to empower quantum computing. Recent progress has highlighted its positive impact on learning quantum dynamics, wherein the integration of entanglement into quantum operations or measurements of quantum machine learning (QML) models leads to substantial reductions in training data size, surpassing a specified prediction error threshold. However, an analytical understanding of how the entanglement degree in data affects model performance remains elusive. In this study, we address this knowledge gap by establishing a quantum no-free-lunch (NFL) theorem for learning quantum dynamics using entangled data. Contrary to previous findings, we prove that the impact of entangled data on prediction error exhibits a dual effect, depending on the number of permitted measurements. With a sufficient number of measurements, increasing the entanglement of training data consistently reduces the prediction error or decreases the required size of the training data to achieve the same prediction error. Conversely, when few measurements are allowed, employing highly entangled data could lead to an increased prediction error. The achieved results provide critical guidance for designing advanced QML protocols, especially for those tailored for execution on early-stage quantum computers with limited access to quantum resources.
Quantum entanglement is a key resource for achieving superiority of quantum computing.Currently, scientists are extensively focusing on how to integrate quantum entanglement into various components of quantum machine learning (QML) models, aiming to surpass the performance of traditional machine learning models.Notable successes include the use of entangled measurements [1][2][3] and entangled channels [4] , which have been shown to reduce query complexity or improve the prediction precision for specified QML tasks.Quantum entangled data, capable of encoding more information compared to classical data of the same size, is recognized for its potential to achieve quantum advantages.Nevertheless, the impact of the entanglement degree in quantum data on model performance remains a challenging and unresolved research question.Recently, Wang and collaborators [5] (Nat Commun 2024, 15, 3716) rigorously analyzed the impact of the entanglement degree of quantum data, the number and type of measurements, and the size of training dataset on the prediction error of QML models by establishing the quantum no-free-lunch (NFL) theorem.They consider tasks of quantum dynamics learning with entangled data, which is fundamental to many advanced quantum algorithms, as illustrated in Fig. 1.While conventional understanding suggests that entanglement mainly confers benefits to QML in terms of sample complexity [6,7] , this study demonstrates that the effect of the degree of entanglement on prediction error exhibits a dual effect, that is, whether quantum entanglement improves performance depends on the number of measurements allowed.With a sufficient number of measurements, increasing the entanglement degree in quan-
The No-Free-Lunch (NFL) theorem, which quantifies problem- and data-independent generalization errors regardless of the optimization process, provides a foundational framework for comprehending diverse learning protocols' potential. Despite its significance, the establishment of the NFL theorem for quantum machine learning models remains largely unexplored, thereby overlooking broader insights into the fundamental relationship between quantum and classical learning protocols. To address this gap, we categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable and establish their NFL theorem. The exploited protocols, namely Classical Learning Protocols (CLC-LPs), Restricted Quantum Learning Protocols (ReQu-LPs), and Quantum Learning Protocols (Qu-LPs), offer varying levels of access to quantum resources. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs, contingent upon the orthogonality of quantum states and the diagonality of observables. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states, a distinctive physical feature inherent in quantum mechanics. Our findings not only deepen our understanding of quantum learning protocols' capabilities but also provide practical insights for the development of advanced quantum learning algorithms.
Tensor network machine learning models have shown remarkable versatility in tackling complex data-driven tasks. Despite their promising performance, a comprehensive understanding of the underlying assumptions and limitations of these models is still lacking. Here we focus on the rigorous formulation of their no-free-lunch theorem, which is essential yet notoriously challenging to formalize for specific tensor network learning models. In particular, we rigorously analyze the generalization risks of learning target output functions from input data encoded in tensor network states. We first prove a no-free-lunch theorem for machine learning models based on matrix product states. Then we circumvent the challenging issue of calculating the partition function for a two-dimensional Ising model, and prove the no-free-lunch theorem for the case of two-dimensional projected entangled-pair states, by introducing the combinatorial method associated to the "puzzle of polyominoes." In addition, we rigorously establish an adversarial theorem that emerges naturally as a practical consequence of our no-free-lunch theorem. Our findings reveal the intrinsic limitations of tensor-network-based learning models in a rigorous fashion, and open up an avenue for future analytical exploration of both the strengths and limitations of quantum-inspired machine learning frameworks.
Abstract Training classical neural networks generally requires a large number of training samples. Using entangled training samples, Quantum Neural Networks (QNNs) have the potential to significantly reduce the amount of training samples required in the training process. However, to minimize the number of incorrect predictions made by the resulting QNN, it is essential that the structure of the training samples meets certain requirements. On the one hand, the exact degree of entanglement must be fixed for the whole set of training samples. On the other hand, training samples must be linearly independent and non-orthogonal. However, how failing to meet these requirements affects the resulting QNN is not fully studied. To address this, we extend the proof of the Quantum No-Free-Lunch theorem to (i) provide a generalization of the theorem for varying degrees of entanglement. This generalization shows that the average degree of entanglement in the set of training samples can be used to predict the expected quality of the QNN. Furthermore, we (ii) introduce new estimates for the expected accuracy of QNNs for moderately entangled training samples that are linearly dependent or orthogonal. Our analytical results are (iii) experimentally validated by simulating QNN training and analyzing the quality of the QNN after training.