During this talk I will present a selection of results at the intersection of quantum information, quantum computation, and machine learning. First, I will introduce the PAC model, a mathematical framework for rigorously formulating learning problems from both a statistical and computational perspective. I will discuss a quantum formulation of this model and present a learning problem where quantum resources can give a quasi-exponential speedup. Second, I will discuss a way to model quantum many body states with variational autoencoders, a state of the art generative model based on artificial neural networks. In particular, I will show how depth influences the learnability of quantum states of varying degree of hardness. Finally, I will talk about the Nyström method, a technique from randomised linear algebra that has recently found applications in machine learning, and discuss how it can be used to approximate quantum Hamiltonian evolutions.