# Information-Theoretic Limits of Quantum Learning via Data Compression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 13 Dec 2021.

## Builds on (most cited first, 15 of 15)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [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)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Noisy intermediate-scale quantum (NISQ) algorithms](https://mlsanity.com/paper/2101.08448/) (2021)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Quantum Learning Boolean Linear Functions w.r.t. Product Distributions](https://mlsanity.com/paper/1902.08753/) (2019)
- [Flow Ambiguity: A Path Towards Classically Driven Blind Quantum Computation](https://mlsanity.com/paper/1608.04633/) (2016)
- [QFactory: classically-instructed remote secret qubits preparation](https://mlsanity.com/paper/1904.06303/) (2019)
- [Computationally-secure and composable remote state preparation](https://mlsanity.com/paper/1904.06320/) (2019)

## Abstract (arXiv)

Understanding the power of quantum data in machine learning is central to many proposed applications of quantum technologies. While access to quantum data can offer exponential advantages for carefully designed learning tasks and often under strong assumptions on the data distribution, it remains an open question whether such advantages persist in less structured settings and under more realistic, naturally occurring distributions. Motivated by these practical concerns, we introduce a systematic framework based on quantum lossy data compression to bound the power of quantum data in the context of probably approximately correct (PAC) learning. Specifically, we provide lower bounds on the sample complexity of quantum learners for arbitrary functions when data is drawn from Zipf's distribution, a widely used model for the empirical distributions of real-world data. We also establish lower bounds on the size of quantum input data required to learn linear functions, thereby proving the optimality of previous positive results. Beyond learning theory, we show that our framework has applications in secure delegated quantum computation within the measurement-based quantum computation (MBQC) model. In particular, we constrain the amount of private information the server can infer, strengthening the security guarantees of the delegation protocol proposed in (Mantri et al., PRX, 2017).