  Quantum neural networks (QNNs) have generated excitement around the
possibility of efficiently analyzing quantum data. But this excitement has been
tempered by the existence of exponentially vanishing gradients, known as barren
plateau landscapes, for many QNN architectures. Recently, Quantum Convolutional
Neural Networks (QCNNs) have been proposed, involving a sequence of
convolutional and pooling layers that reduce the number of qubits while
preserving information about relevant data features. In this work we rigorously
analyze the gradient scaling for the parameters in the QCNN architecture. We
find that the variance of the gradient vanishes no faster than polynomially,
implying that QCNNs do not exhibit barren plateaus. This provides an analytical
guarantee for the trainability of randomly initialized QCNNs, which highlights
QCNNs as being trainable under random initialization unlike many other QNN
architectures. To derive our results we introduce a novel graph-based method to
analyze expectation values over Haar-distributed unitaries, which will likely
be useful in other contexts. Finally, we perform numerical simulations to
verify our analytical results.
