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:2405.07226

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

Xinbiao Wang, Yuxuan Du, Kecheng Liu, Luo, Yong, Bo Du, Dacheng Tao

Published May 12, 2024• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2405.07226

Related papers

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

Kunal Sharma, Marco Cerezo, Zoë Holmes +3 more

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.

arXiv:2007.04900•Physical Review Letters•Feb 18, 2022•74 citations

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

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

Quantum Circuit-Based Learning Models: Bridging Quantum Computing and Machine Learning

Fan Fan, Yilei Shi, Mihai Datcu +5 more

Machine Learning (ML) has been widely applied across numerous domains due to its ability to automatically identify informative patterns from data for various tasks. The availability of large-scale data and advanced computational power enables the development of sophisticated models and training strategies, leading to state-of-the-art performance, but it also introduces substantial challenges. Quantum Computing (QC), which exploits quantum mechanisms for computation, has attracted growing attention and significant global investment as it may address these challenges. Consequently, Quantum Machine Learning (QML), the integration of these two fields, has received increasing interest, with a notable rise in related studies in recent years. We are motivated to review these existing contributions regarding quantum circuit-based learning models for classical data analysis and highlight the identified potentials and challenges of this technique. Specifically, we focus not only on QML models, both kernel-based and neural network-based, but also on recent explorations of their integration with classical machine learning layers within hybrid frameworks. Moreover, we examine both theoretical analysis and empirical findings to better understand their capabilities, and we also discuss the efforts on noise-resilient and hardware-efficient QML that could enhance its practicality under current hardware limitations. In addition, we cover several emerging paradigms for advanced quantum circuit design and highlight the adaptability of QML across representative application domains. This study aims to provide an overview of the contributions made to bridge quantum computing and machine learning, offering insights and guidance to support its future development and pave the way for broader adoption in the coming years.

quant-pharXiv:2602.00048•Artificial Intelligence Review•Jan 20, 2026•2 citations
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.
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-
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.
Machine Learning (ML) has been widely applied across numerous domains due to its ability to automatically identify informative patterns from data for various tasks. The availability of large-scale data and advanced computational power enables the development of sophisticated models and training strategies, leading to state-of-the-art performance, but it also introduces substantial challenges. Quantum Computing (QC), which exploits quantum mechanisms for computation, has attracted growing attention and significant global investment as it may address these challenges. Consequently, Quantum Machine Learning (QML), the integration of these two fields, has received increasing interest, with a notable rise in related studies in recent years. We are motivated to review these existing contributions regarding quantum circuit-based learning models for classical data analysis and highlight the identified potentials and challenges of this technique. Specifically, we focus not only on QML models, both kernel-based and neural network-based, but also on recent explorations of their integration with classical machine learning layers within hybrid frameworks. Moreover, we examine both theoretical analysis and empirical findings to better understand their capabilities, and we also discuss the efforts on noise-resilient and hardware-efficient QML that could enhance its practicality under current hardware limitations. In addition, we cover several emerging paradigms for advanced quantum circuit design and highlight the adaptability of QML across representative application domains. This study aims to provide an overview of the contributions made to bridge quantum computing and machine learning, offering insights and guidance to support its future development and pave the way for broader adoption in the coming years.