# Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets

arXiv: https://arxiv.org/abs/2007.04900 · HTML: https://mlsanity.com/paper/2007.04900/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

## Built on by (most cited first, 28 of 28)

- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Connecting ansatz expressibility to gradient magnitudes and barren plateaus](https://mlsanity.com/paper/2101.02138/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Representation Theory for Geometric Quantum Machine Learning](https://mlsanity.com/paper/2210.07980/) (2022)
- [Recent advances for quantum classifiers](https://mlsanity.com/paper/2108.13421/) (2021)
- [Entangled Datasets for Quantum Machine Learning](https://mlsanity.com/paper/2109.03400/) (2021)
- [Universal Adversarial Examples and Perturbations for Quantum Classifiers](https://mlsanity.com/paper/2102.07788/) (2021)
- [Analytic theory for the dynamics of wide quantum neural networks](https://mlsanity.com/paper/2203.16711/) (2022)
- [Variational inference with a quantum computer](https://mlsanity.com/paper/2103.06720/) (2021)
- [Dynamical simulation via quantum machine learning with provable generalization](https://mlsanity.com/paper/2204.10269/) (2022)
- [Impossibility Results in AI: A Survey](https://mlsanity.com/paper/2109.00484/) (2021)
- [The power and limitations of learning quantum dynamics incoherently](https://mlsanity.com/paper/2303.12834/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric](https://mlsanity.com/paper/2303.13462/) (2023)
- [Overfitting in quantum machine learning and entangling dropout](https://mlsanity.com/paper/2205.11446/) (2022)
- [Long-time simulations with high fidelity on quantum hardware](https://mlsanity.com/paper/2102.04313/) (2021)
- [Variational Quantum Approximate Support Vector Machine with Inference Transfer](https://mlsanity.com/paper/2206.14507/) (2022)
- [Expressibility-induced Concentration of Quantum Neural Tangent Kernels](https://mlsanity.com/paper/2311.04965/) (2023)
- [Optimal quantum dataset for learning a unitary transformation](https://mlsanity.com/paper/2203.00546/) (2022)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [Architectural Vision for Quantum Computing in the Edge-Cloud Continuum](https://mlsanity.com/paper/2305.05238/) (2023)
- [Topological Learning in Multi-Class Data Sets](https://mlsanity.com/paper/2301.09734/) (2023)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [Eliminating Vendor Lock-In in Quantum Machine Learning via Framework-Agnostic Neural Networks](https://mlsanity.com/paper/2604.04414/) (2026)
- [Statistical Mechanics of Learning on Product Wasserstein Manifolds](https://mlsanity.com/paper/2608.01434/) (2026)

## Abstract (arXiv)

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 data set. 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 (the quantum analog of a function) with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this work, we show that entangled data sets 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 work establishes that entanglement is a commodity in quantum machine learning.