Probably approximately correct quantum source coding
  Information-theoretic lower bounds are often encountered in several branches
of computer science, including learning theory and cryptography. In the quantum
setting, Holevo's and Nayak's bounds give an estimate of the amount of
classical information that can be stored in a quantum state. Previous works
have shown how to combine information-theoretic tools with a counting argument
to lower bound the sample complexity of distribution-free quantum probably
approximately correct (PAC) learning. In our work, we establish the notion of
Probably Approximately Correct Source Coding and we show two novel applications
in quantum learning theory and delegated quantum computation with a purely
classical client. In particular, we provide a lower bound of the sample
complexity of a quantum learner for arbitrary functions under the Zipf
distribution, and we improve the security guarantees of a classically-driven
delegation protocol for measurement-based quantum computation (MBQC).
