  Quantum technologies rely on the ability to coherently manipulate, process
and transfer information, encoded in quantum states, along quantum channels.
Decoherence induced by the environment introduces errors, thus setting limits
on the efficiency of any quantum-enhanced protocol or device. A fundamental
bound on the ability of a noisy quantum channel to transmit quantum (classical)
information is given by its quantum (classical) capacity. Generally, the longer
is a quantum channel the more are the introduced errors, and hence the worse is
its capacity. In this Letter we show that for non-Markovian quantum channels
this is not always true: surprisingly the capacity of a longer channel can be
greater than the one of a shorter channel. We introduce a general theoretical
framework linking non-Markovianity to the capacities of quantum channels, and
demonstrate in full generality how harnessing non-Markovianity may improve the
efficiency of quantum information processing and communication.
