  Quantum computing is a new computational paradigm that promises applications
in several fields, including machine learning. In the last decade, deep
learning, and in particular Convolutional neural networks (CNN), have become
essential for applications in signal processing and image recognition. Quantum
deep learning, however remains a challenging problem, as it is difficult to
implement non linearities with quantum unitaries. In this paper we propose a
quantum algorithm for applying and training deep convolutional neural networks
with a potential speedup. The quantum CNN (QCNN) is a shallow circuit,
reproducing completely the classical CNN, by allowing non linearities and
pooling operations. The QCNN is particularly interesting for deep networks and
could allow new frontiers in image recognition, by using more or larger
convolution kernels, larger or deeper inputs. We introduce a new quantum
tomography algorithm with $\ell_{\infty}$ norm guarantees, and new applications
of probabilistic sampling in the context of information processing. We also
present numerical simulations for the classification of the MNIST dataset to
provide practical evidence for the efficiency of the QCNN.
