# Private learning implies quantum stability

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 62 references that are in the map.
- First posted on arXiv 14 Feb 2021.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [Characterizing the Sample Complexity of Private Learners](https://mlsanity.com/paper/1402.2224/) (2014)
- [Quantum Differentially Private Sparse Regression Learning](https://mlsanity.com/paper/2007.11921/) (2020)
- [Closure Properties for Private Classification and Online Prediction](https://mlsanity.com/paper/2003.04509/) (2020)
- [On the Equivalence between Online and Private Learnability beyond Binary Classification](https://mlsanity.com/paper/2006.01980/) (2020)
- [Private Learning Implies Online Learning: An Efficient Reduction](https://mlsanity.com/paper/1905.11311/) (2019)
- [Online Learning via the Differential Privacy Lens](https://mlsanity.com/paper/1711.10019/) (2017)
- [A Computational Separation between Private Learning and Online Learning](https://mlsanity.com/paper/2007.05665/) (2020)
- [Improved Quantum Boosting](https://mlsanity.com/paper/2009.08360/) (2020)
- [Synthetic Data Generators: Sequential and Private](https://mlsanity.com/paper/1902.03468/) (2019)

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

- [Quantum Differential Privacy: An Information Theory Perspective](https://mlsanity.com/paper/2202.10717/) (2022)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems](https://mlsanity.com/paper/2306.13054/) (2023)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [A learning theory for quantum photonic processors and beyond](https://mlsanity.com/paper/2209.03075/) (2022)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNP](https://mlsanity.com/paper/2204.06638/) (2022)

## Abstract (arXiv)

Learning an unknown n-qubit quantum state ρ is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in n many copies of ρ to estimate it up to trace distance. Motivated by computational learning theory, Aaronson et al. introduced many (weaker) learning models: the PAC model of learning states (Proceedings of Royal Society A'07), shadow tomography (STOC'18) for learning "shadows" of a state, a model that also requires learners to be differentially private (STOC'19) and the online model of learning states (NeurIPS'18). In these models it was shown that an unknown state can be learned "approximately" using linear-in-n many copies of rho. But is there any relationship between these models? In this paper we prove a sequence of (information-theoretic) implications from differentially-private PAC learning, to communication complexity, to online learning and then to quantum stability. Our main result generalizes the recent work of Bun, Livni and Moran (Journal of the ACM'21) who showed that finite Littlestone dimension (of Boolean-valued concept classes) implies PAC learnability in the (approximate) differentially private (DP) setting. We first consider their work in the real-valued setting and further extend their techniques to the setting of learning quantum states. Key to our results is our generic quantum online learner, Robust Standard Optimal Algorithm (RSOA), which is robust to adversarial imprecision. We then show information-theoretic implications between DP learning quantum states in the PAC model, learnability of quantum states in the one-way communication model, online learning of quantum states, quantum stability (which is our conceptual contribution), various combinatorial parameters and give further applications to gentle shadow tomography and noisy quantum state learning.