There has been recent progress in extending artificial neural networks to the quantum domain. These quantum neural networks have been shown successful for a variety of tasks, encompassing compression of data, learning Simon’s algorithm, or recovering teleportation protocols. At the heart of every computation of a neural network is the calibration of the network parameters ? usually referred to as the training. Even though recent proposals of neural networks process data quantumly, the training subroutine has mainly remained classical and it is known that for sufficiently large networks the problem of training is NP-complete. In our work, we follow a different approach to training and suggest a fully quantum training routine for feedforward binary neural networks. For certain classes of problems, the training routine is shown to achieve a polynomial speedup compared to classical training algorithms.