  We examine the complexity of learning the distributions produced by
finite-state quantum sources. We show how prior techniques for learning hidden
Markov models can be adapted to the quantum generator model to find that the
analogous state of affairs holds: information-theoretically, a polynomial
number of samples suffice to approximately identify the distribution, but
computationally, the problem is as hard as learning parities with noise, a
notorious open question in computational learning theory.
