nathanwiebe
The first approach considered in the algorithm really doesn't need a quantum oracle. Since that algorithm only requires that you sequentially feed the input data you want to train the system with, you don't need any sophisticated quantum algorithm to provide an entangled mixture of the data used to train the system.
The second algorithm we consider does use a quantum oracle (meaning a quantum device that allows the quantum computer to prepare an entangled mixture of input training examples). In practice, if you have a database of training vectors (like MNIST handwriting images that you want to recognize) then you'd need to make a giant quantum computer that stores all of this and allows quantum access to this. This could be done using a QRAM (although not all quantum computer designs have efficient QRAM).
Alternatively, the quantum oracle could be any other quantum algorithm that you want to learn about. One idea that I'm a little obsessed with is the idea of using a quantum simulation subroutine as the quantum oracle. Then this approach allows you to train a deep Boltzmann machine to learn features of the system that the subroutine is simulating. Ideas like this could really accelerate drug testing and development by using AI and quantum simulation simultaneously to focus in on promising candidate drugs without requiring as much trial and error as current methods.