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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 105 references that are in the map.
- First posted on arXiv 12 May 2024.

## Builds on (most cited first, 30 of 46)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [Deep High-Resolution Representation Learning for Visual Recognition](https://mlsanity.com/paper/1908.07919/) (2019)
- [A Comprehensive Survey on Transfer Learning](https://mlsanity.com/paper/1911.02685/) (2019)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Generative Adversarial Networks: An Overview](https://mlsanity.com/paper/1710.07035/) (2017)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Transfer Learning in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2009.07888/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Demystifying Contrastive Self-Supervised Learning: Invariances, Augmentations and Dataset Biases](https://mlsanity.com/paper/2007.13916/) (2020)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Equivariant Contrastive Learning](https://mlsanity.com/paper/2111.00899/) (2021)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Towards understanding the power of quantum kernels in the NISQ era](https://mlsanity.com/paper/2103.16774/) (2021)
- [Recent Advances for Quantum Neural Networks in Generative Learning](https://mlsanity.com/paper/2206.03066/) (2022)
- [Recent advances for quantum classifiers](https://mlsanity.com/paper/2108.13421/) (2021)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)

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

- [No-Free-Lunch Theories for Tensor-Network Machine Learning Models](https://mlsanity.com/paper/2412.05674/) (2024)

## Abstract (arXiv)

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.