Private learning implies quantum stability

Learning an unknown n-qubit quantum state ρ is a fundamental challenge in quantum computing. Information-theoretically, it is well-known that tomography requires exponential in n many copies of an unknown state ρ in order to estimate it up to small trace distance. Motivated by computational learning theory, Aaronson and others introduced several (weaker) learning models: the PAC model of learning quantum states (Proc. of Royal Society A'07), shadow tomography (STOC'18) for learning "shadows" of a quantum state, a learning model that additionally requires learners to be differentially private (STOC'19), and the online model of learning quantum states (NeurIPS'18). In these models it was shown that an unknown quantum state can be learned "approximately well" using linear in n many copies of ρ. But is there any relationship between these learning models? In this paper we prove a sequence of (information-theoretic) implications from differentially-private PAC learning to online learning and then to quantum stability. Our main result generalizes the recent work of Bun, Livni and Moran (Journal of the ACM, 2021) 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 to their techniques to the setting of learning quantum states. Key to many of our results is our construction of a 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 new conceptual contribution) and various combinatorial parameters. As an application, we also improve gentle shadow tomography (for classes of quantum states) and show connections between noisy quantum state learning and channel capacity, which might be relevant to physically-motivated learning scenarios.