Private learning implies quantum stability
  Learning an unknown $n$-qubit quantum state $\rho$ is a fundamental challenge
in quantum computing. Information-theoretically, it is known that tomography
requires exponential in $n$ many copies of $\rho$ 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.
