Can small quantum systems learn?

We examine the question of whether quantum mechanics places limitations on the ability of small quantum devices to learn. We specifically examine the question in the context of Bayesian inference, wherein the prior and posterior distributions are encoded in the quantum state vector. We conclude based on lower bounds from Grover's search that an efficient blackbox method for updating the distribution is impossible. We then address this by providing a new adaptive form of approximate quantum Bayesian inference that is polynomially faster than its classical analogue and tractable if the quantum system is augmented with classical memory or if the low-order moments of the distribution are protected using a repetition code. This work suggests that there may be a connection between fault tolerance and the capacity of a quantum system to learn from its surroundings.