In recent years, deep learning has had a profound impact on machine learning and artificial intelligence. Here we investigate if quantum algorithms for deep learning lead to an advantage over existing classical deep learning algorithms. We develop two quantum machine learning algorithms that reduce the time required to train a deep Boltzmann machine and allow richer classes of models, namely multilayer, fully connected networks, to be efficiently trained without the use of contrastive divergence or similar approximations. Our algorithms may be used to efficiently train either full or restricted Boltzmann machines. By using quantum state preparation methods, we avoid the use of contrastive divergence approximation and obtain improved maximization of the underlying objective function.